Extended Operators of Relational Algebra

Bags

What is Bags?

• 일반적으로, Database의 각종 Data들은 간단한 순수 집합 베이스의 tuple들이다.
  
• 가끔, Database system의 Relation은 Duplicate tuple(중복튜플)이 허용된다. 
  
  • (말인 즉슨 같은 tuple이 1회 이상 발생 허용) 
    
• 이 때, 그 set을 Bag 혹은 Multiset이라 부른다. 
  
  

여기서의 '중복'이란, tuple의 중복이다 ( component의 중복과 다름 )

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) (개) 
    

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 값을 반환한다. 
      

엄밀히 따지자면, Aggregation operator는
Relational Algebra는 아니다. 하지만
뒤에 나올 Grouping에서 사용하기 때문에
같이 학습하도록 한다.

Grouping

• 보통, 전체 Column을 가지고 Average같은 Aggregation 연산을 하지는 않는다.
  각각 Column 1개 전체의 연산 말고 좀 더 Column들을 묶어서 연산을 행한다.
  
  • 예를 들어, Studio마다 상영시간의 총합을 알고싶은 경우엔 어떻게 하나?
    → Studio마다 묶어서 상영시간의 총합 Group마다 독립적으로 계산한다.
    
• γL(R) [ :감마]로 표현하며, List L : Attribute 및 Aggregation으로 나타낸다. 
  이 때, 그룹화의 기준이 되는 Column을 Grouping attribute, 
  Aggregation 연산을 하는 Column(들)을 Aggregated attribute라 한다.
  
• γL(R)의 특징
  1. R의 일부를 Group화한다. 각 Group들은 Grouping attribute에 해당하는 1개의 값을 갖는 모든 tuple들로 구성된다.(중복은 제거) 
     즉 Grouping attribute에는 NULL값이 허용되지 않는다. 
     
  2. 만약 Grouping attribute가 없다면, Relation R은 1 Group이다. 
     
  3. L에는 Attribute, 연산, →(Renaming)등을 기재할 수 있다.
  4. L에 연산(Aggregation)이 들어가면, 각 Group당 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값의 의미는,
  
  1. Relation R의 Column.
     
  2. x→y 표현 : x와 y는 둘 다 Column name이고, x를 y로 Renaming한다. 결과 Schema 역시 y로 표기된다.
     
  3. E→z 표현 : E는 Expression(Column, 상수, 산수, 스트링 연산자 등)
     z는 그 E의 계산 결과를 Renaming한 Column name이다.
     

신기하게도, 중복이 생길 수 있다.

The Sorting Operator

질의의 결과 데이터를 저장해두고, 다음에 또 보고 싶을 때가 있다.
이를 위해 τL(R) [ :타우]을 사용해 정렬하는데, L은 Column의 list, R은 역시 Relation이다.
즉, τL(R)는

1. L이 하나의 Column : 이 Column의 값만을 기준으로 tuple을 정렬한다. (같다면 임의로 배치)
   
2. 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 값과 같이 표시한다)
  

마침.