[데이터베이스] Relational Algebra

https://en.wikipedia.org/wiki/Relational_algebra 

Relational Model에서 Relation은 기본적으로 집합(set) 의 특성을 가지고 있다. 따라서 Relation에는 집합에 대한 성질 및 연산이 적용된다. 이로 인해 중복을 허용하지 않으며, 결합 법칙 및 교환 법칙 등이 성립한다.

• algebra operation :  relation 사이에 적용되는 연산. 연산의 결과로 새로운 relation을 반환한다.
• relation algebra expression : operation이 모여 표현식을 이루는 것.

---

Operations

• Unary Relational Operation
  • SELECT ( 𝝈 : sigma ) 
  • PROJECT ( 𝝅 : pi )
  • RENAME ( 𝝆 : rho )
• Relational Algebra Operations From Set Theory
  • UNION ( ⋃ )
  • INTERSECTION ( ⋂ )
  • DIFFERENCE ( - )
  • CARTESIAN PRODUCT ( x )
• Binary Relational Operations
  • JOIN ( ⋈, ⟕, ⟖, ⟗ )
  • DIVISION
• Additional Relational Operations
  • OUTER JOIN, OUTER UNION
  • AGGREGATE FUNCTIONS ( ex SUM, COUNT, AVG, MIN, MAX ) 

 

---

Unary Relational Operations

SELECT ( 𝝈 : sigma )

 튜플에 대한 selection condition을 명시하여 튜플들에 대한 subset을 얻는 방법. 선택 조건은 필터의 역할을 수행하며, 조건을 만족하는 튜플만을 얻고, 해당 조건에 대응되지 않는 튜플은 필터링된다. 

 집합 내에서 모든 튜플은 서로 독립적이므로, SELECT 에 의한 relation은 중복된 값을 튜플을 가질 일이 없다.

• 표기법 :  δ_<조건>(R) 
• 예시 : δ_{DNO = 4}(EMPLOYEE)  / δ_{score > 80}(STUDENT)
• horizontal partition : 조건에 따라 각 행(수평)을 선택한다.
• 교환 및 결합법칙 성립 : SELECT 끼리 중복되어 사용될 수 있으며, 순서도 중요하지 않다. 
  • δ_{DNO = 4} ( δ_{SEX = 4}( δ_{AGE > 23}(EMPLOYEE) ) )
  • δ_{SEX = 4} ( δ_{DNO = 4}( δ_{AGE > 23}(EMPLOYEE) ) )
  • δ_{SEX = 4 and DNO = 4 and AGE > 23}(EMPLOYEE)

SQL에서는 SELECT * FROM EMPLOYEE WHERE ~ 형태로 나타난다.

PROJECT ( 𝝅 : pi )

 relation에 대한 특정 attribute 을 기준으로 파티셔닝을 진행한다. 

• 표기법 :  𝝅_{<attribute list>}(R) 
• 예시 : 𝝅 _{SEX, DNO} (EMPLOYEE)
• vertical partition : 조건에 따라 각 열(수직) 을 선택한다.
• 교환법칙 성립 X
  : Projection에 의한 결과 relation은 원 relation인 R의 부분집합이므로, 순서가 변경되면 보통 성립 자체가 안된다.
  • 𝝅_SEX(𝝅_{SEX, DNO}(EMPLOYEE)) 에서 앞에 있는 𝝅(SEX) 의 결과는 이전 Projection인 𝝅(SEX, DNO) 의 부분 집합이므로, 이 둘의 위치가 변경되면 𝝅(SEX) 로부터 𝝅(SEX, DNO) 대응되는 부분 집합을 추출할 수 없다.

SQL에서는 SELECT 절에 column을 Projection 하는 행위에 대응된다.

RENAME ( 𝝆 : rho )

attribute 혹은 relation 의 이름을 변경하기 위한 오퍼레이터. 변경된 이름을 기술하는 방식으로 동작한다. JOIN 상황이나 쿼리가 다수의 operation을 요구할 때 효율적일 수 있다.

• 표기법 : attribute 및 relation을 변경하는 경우에 대해 3가지 표기법이 존재한다.
  • relation name만 변경 : 𝝆_S(R)
  • attribute name만 변경 : 𝝆_{(a1, a2, a3 ...)}(R)
  • 둘 다 변경 변경 : 𝝆_{S(a1, a2, a3 ...)}(R)

SQL에서는 AS를 통한 aliasing에 대응된다.

Relational Algebra의 2가지 표현법

relation을 중첩된 형태로 표현해도 상관 없지만, 각 단계를 알아보기 쉽도록 중간 relation을 지정하여 사용할 수도 있다.

• nested : δ_{DNO = 4} ( δ_{SEX = 4}( δ_{AGE > 23}(EMPLOYEE) ) )
• intermediate relation
  :
   UP_23_EMP ← δ_{AGE > 23}(EMPLOYEE)
   SEX_M_EMP ← δ_{SEX = 'male'}( UP_23_EMP ) 
   RESULT_EMP ← δ_{DNO = 4}( SEX_M_EMP )

---

Relational Algebra Operations From Set Theory

UNION ( ⋃ )

 두개의 relation을 결합하는 연산. 두 relation 에 속해있는 모든 튜플을 가져오되, 중복된 값은 한번만 가져온다.

• 교환법칙(commutative) 성립 : R ⋃ S = S ⋃ R
• 관계에 참여하는 두 relation은 type compatible 해야 한다.

Union Compatible ( Type Compatible )

연산에 참여하는 두 Relation R, S 가 아래 두 조건을 만족할 때 Type Compatible 하다고 한다.

1. R 및 S 는 반드시 동일한 수의 attribute을 가진다.
2. 두 relation에서 대응되는 각각의 attribute들은 동일하거나, 호환되는 도메인을 가져야 한다. 즉, attribute 쌍은 최소 동일한 연산이 가능해야 한다. (same or compatible domain)

위 조건은 UNION, INTERSECTION, DIFFERENCE 세가지 모두에 대해 적용된다.

DEP5_EMPS ← 𝝈_DNO=5(EMPLOYEE)
RESULT1 ← 𝝅_SSN(DEP5_EMPS)
RESULT2(SSN) ← 𝝅_SUPERSSN(DEP5_EMPS)
RESULT ← RESULT1 RESULT2

INTERSECTION ( ⋂ )

관계에 참여하는 두 relation에 공통적으로 포함된 tuple 만을 가져온다.

• 교환법칙(commutative) 성립 : R ⋂ S = S ⋂ R
•  두 relation은 Type Compatible 해야 한다.

DIFFERENCE ( - )

두 relation R 및 S 가 관계에 참여할 때, R - S 이면  R에는 포함되지만, S에는 포함되지 않는 tuple 만을 가져온다. 

• 교환법칙(commutative) 성립 X : R - S != S - R
  : 전자는 R에만 포함되는 튜플을, 후자는 S에만 포함되는 튜플을 의미한다.
•  두 relation은 Type Compatible 해야 한다.

CARTESIAN PRODUCT ( x )

관계에 참여하는 두 relation의 각 튜플을 전부 1대 1로 연결하는 것.

• 표기법 : R(A1, A2, . . ., An) x S(B1, B2, . . ., Bm)
• Q = R x S 는 n + m 개의 attribute을 가진다.
• n_Q = n_R* n_S  을 만족한다. 즉, Q가 가지는 튜플 개수는 R 및 S의 튜플 개수의 곱과 같다.
• 두 relation은 Type Compatible할 필요가 없다. 단순히 attribute을 1대 1로 붙이는 것이기 때문.

 CARTESIAN PRODUCT는 단독으로 사용되면 마땅한 의미를 도출하지 못한다. 대신 SELECT 을 이용하여 equal  join을 하게 되면 두 relation 사이의 관계를 이용하게 되므로, 의미 있는 연산이 된다.

EMP_DEPENDENTS ← EMPNAMES x DEPENDENT
ACTUAL_DEPS ← 𝝈 _SSN=ESSN(EMP_DEPENDENTS)

---

Binary Relational Operations

JOIN ( ⋈, ⟕, ⟖, ⟗ )

 관계된 두 relation을 조건에 따라 연결하여 새로운 relation을 만드는 연산. CARTESIAN PRODUCT에 대해 SELECT 을 수행한 것과 비슷한 결과가 나오지만, JOIN 연산은 두 relation에 대해 관계된 튜플을 조합한다는 의미가 더 크다.

•  Q = R ⋈ S 일때, Q의 attribute 는 R 및 S의 것을 합쳐 n + m 개가 된다.
• 조건에 의해 일부 값이 제거되므로, 튜플의 개수는 CARTESIAN PRODUCT ( n_R * n_S ) 결과 이하이다. 
• Q의 튜플에는 join condition을 만족하는 것만 나온다.

EQUI-JOIN

 equality ( = ) 을 통한 값의 비교를 통해 두 relation을 연결하는 JOIN 방식.

• 표기법 : R⋈_{<c1 = c2>}S

THETA-JOIN

equality를 포함하여 다양한 비교 연산을 이용하여 두 relation을 연결하는 JOIN 방식.

• 표기법 : R⋈_θS 
• θ 예시 
  • R.Ai<S.Bj AND (R.Ak=S.Bl OR R.Ap<S.Bq)
  • R.Ai=S.Bj AND R.Ak=S.Bl AND R.Ap=S.Bq

INNER JOIN

두 relation에서 조건을 만족하는 조합만을 연결하는 방식. 조건을 만족하지 못하는 좌측 및 우측의 튜플들은 JOIN에 의한 새로운 relation에 포함되지 않는다.