SQL 의 Relational Algebra 요소

Algebra 란?

Relational Algebra 가 무엇인지 알아보기 이전, Algebra 의 의미에 대해 이해해보자. Algebra 는 수학의 대분류로서 Letters 로 Quantities 를 대채하여 표현한 수식을 기술하는 것을 말한다. 실제 계산된 값에 집중하기 보다는 대수적인 수식을 통해 값을 표현한다는 의미로 이해하였다.
$a^2 + 3b + 3 = 0$ 과 같은 2차 방정식이 좋은 예인데 해당 방정식을 만족하는 값을 찾는 산술과정을 변수에 일반화하여 적용하는 것이다.

Relational Algebra 는?

대수적인 관점을 Relation(atomic 한 데이터를 갖는 2차원의 테이블)과 연산자에 대해 적용한 수식 기술이라고 할 수 있다.

• 이산수학의 set 이론에 기반한 relation에 관한 연산을 뜻한다.
• Relations 를 Operands 로 사용하고 연산의 결과 또한 Relations 로 반환하는 표현식을 뜻한다.
  • Relational Operator 를 사용하기에 Procedural Query 언어라고 한다.
• Operator 와 Operand 를 문자로 대신 상뇽하여 주어진 Relation 으로 부터 원하는 결과를 기술하는 표현을 Relation Algrebra 라고 한다.

Relational Closure 성질

Relational Closure 란?

Relational Operation 의 입력과 결과 모두 Relation 이다.

Relational Closure 는 Nested Expressions 를 작성할 수 있도록 하는 성질이다.

Nested Expression

Operands 가 다시 Expressions 로 표현되는 것을 말함.

ex) $(S\ JOIN\ P)\ WHERE \ city='Athens'$

Nested Expression 이 가능하기에 괄호로 감싸진 S, P 의 Join 결과에 다시 Restriction 연산을 수행 할 수 있다.

연산자 우선 순위를 괄호로 표현하므로 Procedural 기술 이라고 한다.

Relational Closure 성질을 만족하기 위해서는 Relational Operands 모두 type-compatible 해야 한다.

Type-compatible

"work well together" 혹은 "exits together" 의 의미이다.

구체적으로는 두 Relations 의 attribute 가 같으면 type-compatible 이라고 한다.

UNION, INTERSECT, DIFFERENCE 의 3 연산자는 반드시 type-compatible Operands 를 사용해야 한다.

Relational Algebra Operators

UNION, INTERSECT, DIFFERENCE, PRODUCT

이산수학의 SET 이론에 기반한 그 느낌 그대로이다. 여기서 집합은 Relation 이고 집합의 원소는 Relation 의 tuple, record 이다.

• UNION $A \ UNION \ B$ 로 표현한다. Operands(Relations)의 각 tuple 을 집합의 원소로 처리하며 해당 집합간 합집합 연산을 수행한 결과와 동일.
  
• INTERSECT $A \ \ INTERSECT \ \ B$ 로 표현한다. Operands(Relations)의 각 tuple 을 집합의 원소로 처리하며 해당 집합간 교집합 연산을 수행한 결과와 동일. MySQL 에서 INTERSECT 를 직접적으로 지원하지는 않는다. 따라서 JOIN 을 사용해 동일한 결과를 내야한다.
  
• DIFFERENCE $A \ \ MINUS \ \ B$ 로 표현한다. Operands(Relations)의 각 tuple 을 집합의 원소로 처리하며 해당 집합간 차집합 연산을 수행한 결과와 동일. $A \cap B = A -(A-B)$ 임을 알 수 있음.
  
• PRODUCT $A \ TIMES \ B$ 혹은 $A \times B = \{ (a,b) | a \Subset A \ and \ b \Subset B \}$ Operands(Relations)의 각 tuple 을 집합의 원소로 처리하며 해당 집합간 Catesian Product 연산을 수행한 결과와 동일. MySQL 에서는 CROSS JOIN 을 사용해 동일한 결과를 도출 할 수 있다.

RESTRICTION, PROEJCTION

• RESTRICTION Relation A 에 대한 조건이 $\theta$일 때, $A \ WHERE \ X \ \theta \ Y$ 혹은 $A \ WHERE \ X \ \theta \ literal$ 로 표현이 가능하다. 만약 Restriction 조건절에서 AND, OR, NOT 이 포함된 경우는 각 하단과 같다.
  • $A \ WHERE C1 \ AND \ C2 =(A \ WHERE \ C1) \cap (A \ WHERE \ C2)$
    AND 연산이 위에서 설명한 INTERSECT 연산을 표현한 수식으로 Decopmose 될 수 있다.
  • $(A \ WHERE \ C1 \ OR \ C2)=(A \ WHERE \ C1) \cup (A \ WHERE \ C2)$
    OR 연산이 위에서 설명한 UNION 연산을 표현한 수식으로 Decopmose 될 수 있다.
  • $A \ WHERE \ NOT \ C=A \ MINUS \ (A \ WHERE \ C)$
• PROJECTION Relation A 에 대해 $X, Y,... , Z$ 를 결과로서 뽑아내는 표현식이다. $A[X, Y, ... , Z]$ 로 기술한다.
  Projection, 말그대로 투영하다는 의미이다. 2차원의 테이블을 상상해보자. 상상한 2차원의 테이블을 세로로 반을 쪼갠 뒤 왼쪽을 가져가면 테이블의 왼쪽 절반을 Projection 한 것이다.
  

JOIN

일반적인 natural JOIN 은 두 개의 Relation $A[X, Y] , B[Y, Z]$ 에 공통 attribute 로서 $Y$ 가 존재 할 때 $A \ JOIN \ B$ 혹은 $A \propto B$로 표기하며 결과는 $[X, Y, Z]$로 구성된다.

• 공통 원소가 없다면? 밑에서 언급하겠지만 Cartesian Product 즉, PRODUCT 연산과 결과가 같다.

Natural JOIN

• JOIN 연산자가 적용되는 공통 attributes 는 Relation A 는 Primary Key 이고 Relation B 는 Foreign Key 이다.
• JOIN 연산자는 교환 법칙과 결합 법칙이 적용 가능하다.

만약 Relation A, B 가 공통 attribute 가 없을 경우 JOIN 은 Catesian Product 결과와 같아지는데 이러한 조인을 Cartesian Product 라고 한다.

Cartesian Product, Cross JOIN

• 한 테이블의 각 row 에 대하여 다른 테이블에 있는 모든 row 에 대한 JOIN 을 만들어냄.
• 공통 attributes 가 있는 Cross JOIN 을 Inner JOIN이라고 한다.
  • 공통 attributes 가 없는 경우 where 절이 true 가 되므로 Cartesian Product 가 결과가 되는 것.

일반적인 JOIN 연산은 Cartesian Product + Restriction 으로 표현된다. 여기서 Restriction 의 조건으로 $\theta$가 부등호, 등호로 표현되므로 $\theta - JOIN$ 이라고 하며 하단의 식과 같다.

$(A \ TIMES \ B) \ WHERE \ X \theta Y$

만약 $\theta - JOIN$ 의 $\theta$가 등호라면, $equiJOIN$ 이라고 한다.

equiJOIN

• equiJOIN 의 결과는 두 개의 공통 attributes 를 포함한다.
  • Natural Join 은 두 개의 공통 attributes 중 하나만 결과에 포함시킴.
    • 따라서 Natural Join 은 projection of restriction of product 로 표현 할 수 있음

DIVIDE

Relation A, B 가 있고 공통 attribute $Y$가 있을 때 $A \ DIVIDE \ B$ 또는 $A \div B$ 로 표현한다. $A \div B$ 는 $B$의 모든 $Y$값에 대응되는 $A$의 레코드를 말한다.

Quantifier($\forall$)

• $A \div B$ 는 모든(all) 값에 대응되는 레코드를 찾기 때문에 Predicate Calculus 에 기반을 둔 Relational Calculus 의 Universal Quantifer($\forall$) 에 해당한다.
• 모든 ~ 에 대하여 를 나타낸다.

SQL 에 실제로 DIVIDE 를 구현하는 구문이 없기에

$A[X,Y] \div B[Y] = A[X] - ((A[X] \times B[Y])-A)[X]$ 로 표현할 수 있다.

A 에 X 에 대해 Projection 한 결과에서 A[X] 와 B[Y] 를 Cartesian Product 한 결과에서 A 를 MINUS 한 결과의 X 에 대한 Projection 한 결과를 MINUS 한 것 과 같다.