Relational Algebra

Relational Data Operation

What is Relational data Operation?

• 원하는 데이터를 얻기 위해 Relation에 필요한 Query를 수행하는 것으로,
  DB system의 구성 요소 중 데이터 언어의 역할을 한다.
  
• 관계 대수/관계 해석 으로 나눌 수 있다. (기능과 표현력 측면에서 능력은 동등하다)
  • 관계 대수(Relational Algebra) : 절차식 언어, 원하는 결과를 얻기 위해 데이터의 처리 과정을 순서대로 기술한다.
  • 관계 해석(Relational Calculus) : 비절차식 언어, 원하는 결과를 얻기 위해 처리를 원하는 데이터가 무엇인지만 기술한다.

Why do we use it?

• 원하고자 하는 데이터를 쉽고, 빠르고, 정확하게 얻고자 사용한다.
  
• 새로운 데이터 언어 제안 시, 해당 데이터 언어의 유용성을 검증하는 기준
  관계 대수나 해석으로, 기술할 수 있는 모든 query를 기술할 수 있으면
  데이터 언어를 관계적으로 완전(Relationally Complete)하다고 판단할 수 있다.
  
  

Relational Algebra

What is Relational Algebra?

• Relation을 다루는 연산으로, 검색 질의를 기술하는데 사용한다.
• 절차식 언어이다. (User가 원하는 결과를 위해 어떤 연산을 수행해야 할 지 system에 알려준다)
• 간단하며 명시적(Powerful) 표현을 사용한다.
• 폐쇄 특성(Closure Property)을 가진다.

->피연산자와 그 연산의 결과 역시 Relation이다.

• 대표 연산자는 8개로, 일반 집합 연산자 4개와 순수 관계 연산자 4개로 분류할 수 있다.
  
• 피연산자의 특성 두가지
  • Variables that stand for relations(relation을 나타내는(대표하는) 변수)
  • Constants which are finite relations(유한한 relation의 상수)
    
    

  연산 : By System     vs     언어 : By User

Normal Set Operator

일반 집합 연산자

• Relation이 tuples의 set이라는 개념을 이용하며, 수학의 집합 연산자를 차용한다.
• 조건 : 피연산자가 두 개이며, 합병가능(Union-compatible)이어야 한다.
• 합병가능 (Union-compatible)이란?

UNION

INTERSECTION

DIFFERENCE

Cardinality	차수	특징
│Ｒ－Ｓ│≤│Ｒ│	Ｒ과Ｓ의 차수와 같다	교환/결합법칙 불가

CARTESIAN PRODUCT

Cardinality	차수	특징
│Ｒ × Ｓ│＝│Ｒ│×│Ｓ│	Ｒ과Ｓ의 차수를 더한 값	교환/결합법칙 성립

Cartesian Product는 두 Relation의 구조가 달라도 가능하다.

Pure Relational Operator

순수 관계 연산자

• Relation의 구조와 특성을 이용하는 연산자이다.

SELECTION

PROJECTION

JOIN

DIVISION

RENAME

Bag vs Set

     초기 DBMS는 Bag을 이용한 data modeling을 하였다.
     Bag은 한마디로, 중복을 허용하는 집합 개념이다.
     그렇기 때문에 implementation 관점에서, 
     Set을 이용한 것보다 효율이 좋다.(두 Relation을 합칠 경우
     복사해서 붙여넣기만 하면 된다.)
     현재는 Data의 종류에 따라 저장 방법이 매우 다르므로
     이 두가지를 적절히 사용한다! ( All과 Distinct 개념 )

Combining Issues

Ordering

아무 조건(Predicate)이 없는 연산들은, 그 순서대로(괄호가 있다면 괄호부터) 행하면 되지만,
위에서 살펴본 Selection, Theta Join 등의 다양한 조건들을 갖는 연산들은
어떤 순서로 조건을 만족시키는 지 정하는 것이 좋다.

• 예를 들어, 두 릴레이션 R1, R2를 ∧(AND)가 포함된 Theta join을 한다고 가정하자. 이 때 AND 양옆의 조건들을
  먼저 행하고 합칠 것이냐, 아니면 Cartesian Product 등으로 먼저 합친 뒤 조건을 행할 것이냐
  하는 등의 issue를 말할 수 있겠다.
  

이러한 것들은 Optimizer가 다양한 비용, 공간, 시간 등을 고려해 '적절히' 정한다.

A Linear Notation for Algebraic Expressions

대수식의 선형 표현법

• Assignment : 복잡한 표현들 대신, 빈 relation을 만들어 순차적 assignment에 따라 표현한다.
  1. Relation 이름, 괄호안에 column 리스트를 입력한다. 보통 마지막 결과 relation 이름은 Answer로 칭한다.
  2. Assignment 기호는 :=를 사용한다.
  3. 대수 표현을 우변에 작성한다.
• 이와 같은 작업을 행하면, 마치 C++의 Pseudocode처럼, 우측 대수를 좌측 relation에 대입한다.
  
  

예)

     Movies relation에서, 

     상영시간이 90분을 넘고 Fox사 배급인 영화의 제목과 개봉 년도를 찾아라.

     R(t,y,l,i,s,p) := σlength>90(Movies)
     S(t,y,l,i,s,p) := σstudioName='Fox'(Movies)
     T(t,y,l,i,s,p) := R ∩ S
     Answer(title, year) := π t,i(T)