Extended Operators of Relational Algebra
Bags
What is Bags?
- 일반적으로, Database의 각종 Data들은 간단한 순수 집합 베이스의 tuple들이다.
- 가끔, Database system의 Relation은 Duplicate tuple(중복튜플)이 허용된다.
- (말인 즉슨 같은 tuple이 1회 이상 발생 허용)
- (말인 즉슨 같은 tuple이 1회 이상 발생 허용)
- 이 때, 그 set을 Bag 혹은 Multiset이라 부른다.
여기서의 '중복'이란, tuple의 중복이다 ( component의 중복과 다름 )
| Sets vs Bags | ||
|---|---|---|
| 종류 | 의미 | 중복 허용 여부 |
| Sets | Data들의 집합 | Ｘ |
| Bags | 마찬가지로, Data들의 집합 | Ｏ |
Set, Bag 둘 다 집합의 의미이며 tuple의 순서 역시 상관 없다.
Why Bags?
- 개념상으로는, 중복을 허용하지 않아 tuple 개수가 더 적은
Set이 Bag보다 Speed가 빠르고, 효율적인 Implementation에 유리한 것 처럼 보인다.
하지만 이전에 언급했듯이, Union 연산은 Bag이 더 빠르다.
또, Projection 연산은 작업을 각 튜플에 대해 독립적으로 할 수 있게 해준다. - Set으로 결과를 얻으면 연산 후 일일이 다 비교하여 중복이 있는지 체크해야한다.
반면 Bag으로 결과를 얻으면 비교 없이 작업이 종료된다.
이와 같이, 연산을 수행하고 곧바로 종료되는 Bag과 달리, 중복 튜플을 확인작업하는 Set이 더 느리다.
(단지 결과 Relation은 Set based가 크기가 작아서 빠르게 보이기만 할 뿐 사실상 훨씬 소요시간 ↑) - 또한, 평균 계산 등 아예 결과가 다른 경우도 있다. (그림 참조)
Union, Intersection, and Difference of Bags
- Relation R에 튜플 T가 n개, Relation S에 튜플 T가 m개 있을 경우,
- T의 개수 #T는
- #T in (R ∪ S) = n+m (개)
- #T in (R ∩ S) = MIN(n, m) (개)
- #T in (R - S) = MAX(0, n-m) (개)
- #T in (R ∪ S) = n+m (개)
Bag' operations on Sets
Relation R과 S가 set이라고 하자.
이때 방금 언급한 Intersection, Difference 연산은
Bag-rule로 실행해도 같은 결과를 보인다.
하지만 Union 연산의 경우, Bag-rule로 실행하면
결과 Relation에 중복이 생길 수도 있다.
그러므로 Union 연산은 조심하자!
Projection & Selection on Bags
- Bag에 Projection, Selection을 적용할 때,
각 tuple마다 독립적으로 수행(즉, 이와 같은 tuple이 있나 신경쓸 것 없이 자신만 신경쓰고)할 수 있다.
또한 Selection Condition 역시 각 tuple에 독립적으로 적용해야한다. - Set의 연산과 중복을 허용한다는 점만 빼면 별 다를 게 없어서 그림은 생략했다.
Algebraic Laws for Bags (연산법칙)
Algebra(대수)에는 많은 법칙들이 있다.
예를들어, Union 연산의 교환법칙 같은경우 Set이든 Bag이든 상관없이 성립한다.
하지만, (R ∪ S) - T = (R - T) ∪ (S - T)같은 분배법칙같은 경우, 성립하지 않음에 주의!
Product of Bags
- Set의 Product 연산과 같다.
R에 tuple T1이 n개,
S에 tuple T2가 m개 있을 때
Product R × S에 tuple T1T2가 nm회 나올 뿐이다.
Joins of Bags
- Join 연산 역시 별거 없다.
그냥 Set의 Join 연산처럼 각 tuple들에 대해
조건에 맞는지 비교하고 결과 tuple을 결정하기만 하면 된다.
또한 연산 중 중복을 제거하지 않는다.
즉, 각각 별개의 독립적인 tuple로 취급한다.
Extended Operators of Relational Algebra
- 지금까지 기본 Relational Algebra와 Set&Bag구별을 해 보았는데, 이들 모두 기초 질의어이다.
- SQL같은 언어는 실제 Application Processing에서 상당히 중요한 몇가지 다른 연산들도 더 가지고 있다.
- 추출 부분에 산술이 허용되는 등 기본 관계 대수 연산이 몇 가지 측면에서 확장되었다.
Duplicate Elimination
- 말 그대로 중복을 제거하는 연산이다.
- δ(R) [ :델타]로 표현하며, Bag인 R의 중복튜플들을 제거함으로써 Set으로 변환한다.
Aggregation Operators
- 결과를 특정 연산을 취함으로써 하나의 결과로 반환한다.
- SUM : Column의 SUM(합)값을 반환한다.
- AVG : Column의 Average(평균)값을 반환한다.
- COUNT : Column의 Count(개수)값을 반환한다. ( 이 때, 별다른 언급이 없으면 중복 포함 )
- MIN and MAX
- Numerical values : 각각 smallest, largest값을 반환한다.
- Character-String values : 각각
Lexicographically(Alphabetically: 사전순서대로)하게 first, last 값을 반환한다.
- SUM : Column의 SUM(합)값을 반환한다.
엄밀히 따지자면, Aggregation operator는
Relational Algebra는 아니다. 하지만
뒤에 나올 Grouping에서 사용하기 때문에
같이 학습하도록 한다.
Grouping
- 보통, 전체 Column을 가지고 Average같은 Aggregation 연산을 하지는 않는다.
각각 Column 1개 전체의 연산 말고 좀 더 Column들을 묶어서 연산을 행한다.- 예를 들어, Studio마다 상영시간의 총합을 알고싶은 경우엔 어떻게 하나?
→ Studio마다 묶어서 상영시간의 총합 Group마다 독립적으로 계산한다.
- 예를 들어, Studio마다 상영시간의 총합을 알고싶은 경우엔 어떻게 하나?
- γL(R) [ :감마]로 표현하며, List L : Attribute 및 Aggregation으로 나타낸다.
이 때, 그룹화의 기준이 되는 Column을 Grouping attribute,
Aggregation 연산을 하는 Column(들)을 Aggregated attribute라 한다. - γL(R)의 특징
- R의 일부를 Group화한다. 각 Group들은 Grouping attribute에 해당하는 1개의 값을 갖는 모든 tuple들로 구성된다.(중복은 제거)
즉 Grouping attribute에는 NULL값이 허용되지 않는다. - 만약 Grouping attribute가 없다면, Relation R은 1 Group이다.
- L에는 Attribute, 연산, →(Renaming)등을 기재할 수 있다.
- L에 연산(Aggregation)이 들어가면, 각 Group당 1개의 tuple만 존재하게 된다.
- R의 일부를 Group화한다. 각 Group들은 Grouping attribute에 해당하는 1개의 값을 갖는 모든 tuple들로 구성된다.(중복은 제거)
Grouping은 쉽게 말해, 공통점을 찾아 그룹화 하는 것이다.
δ is a special case of γ
델타(Duplicate Elimination)는 여러 개의 표현이 존재한다.
예를들어, R(A,B,C)에 대해 δ(R) = γA, B, C(R)이다.
즉, 델타는 Aggregation 없이 모든 Columns를 각각 그룹화 하는것과 같다.
그럼 각각의 Group들은 감마 연산자 자체가 중복을 제거하기 때문에 결국 같아진다.
하지만, 델타는 더 일반적이고 중요한 연산자라 Algebraic측면에선 더욱 고려할 필요가 있다.
혹자는 감마(Grouping)를 Set Projection의 확장(Extension)이라 여긴다.
즉, γA1A2..An(R) = πA1A2..An(R)이다. (물론 Set 한정, Bag이면 다름)
그러므로 감마는 종종 일반화된 추출(Generalized Projection)이라 불린다.
Extending the Projection Operator
- Extended Projection도 저번에 보았던 Projection과 거의 유사한데,
Attribute list L에 다음과 같은 요소들을 기재하여 좀 더 구체적인 추출이 가능하다. - πL(R) [ :파이]로 표현하며, 여기서 L값의 의미는,
- Relation R의 Column.
- x→y 표현 : x와 y는 둘 다 Column name이고, x를 y로 Renaming한다. 결과 Schema 역시 y로 표기된다.
- E→z 표현 : E는 Expression(Column, 상수, 산수, 스트링 연산자 등)
z는 그 E의 계산 결과를 Renaming한 Column name이다.
- Relation R의 Column.
신기하게도, 중복이 생길 수 있다.
The Sorting Operator
질의의 결과 데이터를 저장해두고, 다음에 또 보고 싶을 때가 있다.
이를 위해 τL(R) [ :타우]을 사용해 정렬하는데, L은 Column의 list, R은 역시 Relation이다.
즉, τL(R)는
- L이 하나의 Column : 이 Column의 값만을 기준으로 tuple을 정렬한다. (같다면 임의로 배치)
- L이 다수의 Column : 앞의 Column 기준으로 tuple을 정렬하고
만약 같은 tuple이 있다면 그 다음 Column 기준으로 정렬하고,
이런 방식으로 계속 정렬한다. ( L = A1,A2,...An에서 A1기준, A2기준,...An기준 )
이 때도, n개 의 Column 말고 다른 Column만 다른 tuple이 존재하고, n개의 Column 값이 전부
같으면, 임의로 배치한다. 즉, 기준Column이 아닌 다른 Column으로는 정렬상태를 알 수 없다.
τ는 Anomalous(변칙적, 가변적)이기 때문에, 결과가 Set(순서가 상관이 없는)이 아니라
List of tuples(순서가 상관이 있는)로 반환하는 유일한 연산이다.
그래서 Sorting은 Final Step 연산이다. 만약 τ 뒤에 또 다른 Operator가 나온다면,
정렬된 순서는 다시 섞이게 된다.
Outerjoins
Why?
- 조건에 부합하는 tuple만을 반환하는 Join연산을 지난번에 살펴보았다.
하지만, 결과 Relation에서는 흔적도 찾아볼 수 없는,
조건에 부합하지 않고 'dangling'되는 tuple(들)이 있어,
원래의 Relation을 완벽하게 표현할 수는 없다.
→ To avoid dangling tuple's loss - 이를 위해, Outerjoin 연산을 사용하며,
실제로 많은 상용 DB system에서 다양하게 쓰인다.
How to use it
- 기본 Join으로 연산을 하되, 부합하지 않아 삭제될 tuple들도
결과 Relation의 하위에 기재한다. 이 때, 빈 칸( NULL값 )은 ⊥로 표시한다. - Theta-join의 조건(Predicate, Condition) 역시 추가할 수 있다.
(이 때는 먼저 Condition에 만족하는 튜플들을 반환한 뒤
나머지 제거되는 튜플들을 NULL 값과 같이 표시한다)
마침.
'IT > Database Concepts' 카테고리의 다른 글
| [DB개념] :: Define on SQL about kinds of Relations (다양한 릴레이션에 대한 SQL) (0) | 2018.04.04 |
|---|---|
| [DB개념] :: SQL (Structured Query Language, 구조화 질의어) (0) | 2018.04.03 |
| [DB개념] :: Relational Algebra (관계대수) (0) | 2018.03.29 |
| [DB개념] :: The Relational Data Model (관계형 데이터 모델) (0) | 2018.03.26 |
| [DB개념] :: Overview of Database Management System (DBMS) (1) | 2018.03.21 |
차트
소소한 일상 C코드 DB 항상 행복하게^-^★
