[DB] Ch05. 관계 대수와 관계 해석 (1)

관계 데이터 모델에서의 릴레이션을 조직하기 위한 연산에는 '관계 대수'와 '관계 해석'이라는 두 가지 타입의 정형어가 있음.
데이터 획득 절차에 대해 얼마나 자세히 명세해야 되느냐에 따라 '절차 언어'와 '비 절차 언어'로 구분할 수 있음. 이런 면에서 볼 때 관계 대수는 절차 언어이고, 관계 해석은 비 절차 언어임. 둘은 데이터 언어의 표현력이나 기능면에서 동등함.
데이터 언어가 있을 때 이 언어로써 관계 해석이 표현할 수 있는 모든 질의를 표현할 수 있을 때 그 언어를 '관계적 완전'하다고 함.

 

1. 관계 대수

릴레이션을 처리하기 위한 연산의 집합으로, 각 연산의 피연산자가 모두 릴레이션이고, 연산 결과 또한 릴레이션임. 관계 대수 연산은 두 그룹으로 나누어 설명 가능하며, 첫 번째 그룹은 일반 집합 연산, 두번째 그룹은 순수 관계 연산임.

 

1.1. 일반 집합 연산자

합집합, 교집합, 차집합, 카티션 프로덕트가 여기에 해당됨.
카티션 프로덕트를 제외하고는 피연산자로서의 두 릴레이션은 서로 합병 가능하여야 함. 합병 가능이란 두 릴레이션의 차수가 같고 대응 애트리뷰트 별로 도메인이 같은 것을 말함. 애트리뷰트 이름도 같아야 하는건 아님.

※아래부터 두 피연산자 릴레이션을 R과 S로 가정함.
1.1.1. 합집합(UNION, ∪)
R∪S는 릴레이션 R 또는 S에 속하는 튜플 t로 구성되는 릴레이션임.
$$ R\cup S = \{ t| t \in R \vee t \in S \} $$결과 카디널리티 $|R\cup S| \leq |R|+|S|$

1.1.2. 교집합(INTERSECT, ∩)
R∩S는 릴레이션 R과 S에 동시에 속해있는 튜플 t로 구성되는 릴레이션임.
$$ R\cap S = \{ t| t \in R  \wedge t \in S \} $$결과 카디널리티 $|R\cap S| \leq MIN\{ |R| , |S| \}$

1.1.3. 차집합(DIFFERENCE, $-$)
R$-$S는 R에는 있지만 S에는 없는 튜플 t로 구성되는 릴레이션임.
$$ R- S = \{ t| t \in R  \wedge t \notin S \} $$결과 카디널리티 $|R- S| \leq |R|$

1.1.4. 카티션 프로덕트(CARTESIAN PRODUCT, $\times$)
서로 합병 가능한 릴레이션일 필요는 없음.
R$\times$S는 R에 속한 각 튜플 r에 대해 릴레이션 S에 속한 각 튜플 s를 모두 접속(Concatenation, 기호는 · ) 시킨 튜플 r·s로 구성된 릴레이션임.

$$ R\times S = \{ r·s| r \in R  \wedge s \in S \} $$생성된 릴레이션의 차수는 릴레이션 R의 차수와 S의 차수의 합과 같고, 카디널리티는 두 릴레이션의 카디널리티를 곱한 것과 같음. 즉, $|R\times S| = |R|\times |S|$
차집합을 제외한 합집합, 교집합, 카티션 프로덕트는 결합적(Associative)임. (= 괄호가 의미 없음.)
또한 교환적임. (= 순서가 의미가 없음.)
이러한 결합적 성질이나 교환적 성질은 최적화할 때 이용할 수 있기 때문에 아주 중요함.

 

1.2. 순수 관계 연산자

1.2.0. 표기법 사전 정의

릴레이션 R의 애트리뷰트 집합 {A1,  A2, ..., An}을 X로 표현

>> X = {A1, A2, ..., An}

>> R(X) = R(A1, A2, ..., An)

r 이 릴레이션 R의 튜플이라면 r = <a1, a2, ..., an> 으로 표현, 이때 ai(i = 1,2, ..., n) 는 애트리뷰트 Ai의 값.

역으로 r에 대한 애트리뷰트 Ai의 값을 표현하려면 r[Ai] 또는 r.Ai로 표기하면 됨.

>> r.Ai = r[Ai] = ai

>> R(A1, A2, ..., An) 의 튜플 r에 대해, <r.A1, r.A2, ..., r.An> = <r[A1], r[A2], ..., r[An]> = r[A1, A2, ..., An]=r[X]가 모두 성립.

 

1.2.1. 실렉트(SELECT, $\sigma$ : sigma)

주어진 조건을 만족하는 튜플들을 선택하는 연산.

A와 B를 릴레이션 R의 애트립트, $\theta$는 비교 연산자, v는 상수라고 할 때, 다음과 같이 정의됨.

• $\sigma_{A\theta v}(R)=\{ r| r\in R  \wedge r.A\theta v\}$
• $\sigma_{A\theta B}(R)=\{ r| r\in R  \wedge r.A\theta r.B\}$

실렉트에 표현된 식 $r.A\theta v$나 $r.A\theta r.B$를 비교식, 조건식 또는 프레디킷(predicate)이라 하며, 실렉트는 이를 참으로 만드는 튜플을 선택함. 주어진 릴레이션을 수평적으로 절단하여 일부를 재구성한 것과 같으므로, 수평적 부분 집합을 생성한다고 볼 수 있음.

프레디킷은 단순 비교식을 불리언 연산자 $\wedge$(AND), $\vee$(OR), ¬(NOT) 으로 결합시켜 복잡하게 만들 수도 있으며, 그 기능은 마찬가지로 각 튜플에 적용하여 참인가 거짓인가를 결정함. 비교에 관련된 애트리뷰트들은 당연히 같은 도메인으로 정의되어야 함.

실렉트 연산은 일원 연산자(하나의 릴레이션만을 적용 대상으로 하는 연산자)이며, 그 릴레이션에 포함된 모든 튜플에 대해 각 튜플별로 적용됨.

선택 조건에 의해 선택되는 튜플과 릴레이션 전체 튜플의 비율을 선택 조건의 선택도라 하며, 같은 릴레이션에 선택 조건을 연속적으로 적용해야 한다면 선택도가 작은 것부터(많이 줄일 수 있는 것부터) 수행하는 것이 효율적임. 이는 실렉트 연산이 교환적이기에 가능함.

 

1.2.2. 프로젝트(PROJECT, $\Pi$ : pi)

프로젝트는 릴레이션의 애트리뷰트를 연산 대상으로 함. 

릴레이션 R(X)가 있다고 가정.

Y를 X의 애트리뷰트로 구성된 리스트 (B1, B2, ..., Bm)이라 할 때 릴레이션 R의 애트리뷰트 리스트 Y에 대한 프로젝트 $\Pi_{Y}(R)$은 다음과 같이 정의함.

• $\Pi _Y(R) = \{<r.B_1, r.B_2, ...,r.B_m> | r \in R\}$

결과 릴레이션은 프로젝트 연산에 명세된 애트리뷰트 값들만 선택하게 되고, 릴레이션의 수직적 부분 집합이라고 볼 수 있음.

프로젝트 연산 결과로 만들어진 릴레이션에 똑같은 튜플이 중복되게 포함되면 하나만 제외하고 전부 제거함.

 

1.2.3. 조인(JOIN, ⋈)

릴레이션 R과 S가 있다고 가정.

조인은 다음과 같이 정의함.

• $R⋈_{A\theta B}S = \{ r·s | r\in R \wedge s \in S \wedge (r.A\theta s.B)\}$

$\theta$는 조인 조건에 사용되는 비교 연산자이고, A와 B는 같은 도메인 위에 정의된 조인 애트리뷰트(비교 당하는 애트리뷰트)임.

조인 결과는 R의 튜플 r과 S의 튜플 s에 대해 조인 조건을 만족하는 모든 r과 s를 접속해 만들어진 튜플로 구성된 릴레이션이 됨. 결과 릴레이션의 차수는 R의 차수와 S의 차수를 합한 것과 같음. 결과 릴레이션에서 각 애트리뷰트의 유일성을 만족시키기 위해 원 소속 릴레이션의 이름을 애트리뷰트 앞에 한정어로 붙임.

$\theta$로 표현될 수 있는 조인을 세타 조인이라고 함. $\theta$가 "="인 조인을 '동일 조인'이라고 함.

조인 결과 같은 애트리뷰트(조인 애트리뷰트)가 중복되어 나타나는데, 이를 제거해주는 연산을 '자연 조인'이라고 하며, 연산 기호는 $⋈_N$임. 자연 조인은 조인 애트리뷰트가 둘 이상 되는 경우에도 적용할 수 있기 때문에 자연 조인의 정의를 다음과 같이 일반화 가능함.

조인할 릴레이션( R(X)와 S(Y) ) 의 조인 애트리뷰트를 Z라 가정.

$$ \begin{align*} R⋈_{N}S = \{ <r·s>[X\cup Y] | r \in R \wedge s \in S \wedge r[Z] = s[Z] \} \\ = \Pi _{X\cup Y}(\sigma _{Z=Z}(R\times S))\\ = \Pi _{X\cup Y}(R⋈_{Z=Z}S) \end{align*} $$

 

1.2.4. 디비전(DIVISION, $\div$)

두 릴레이션 R(X)와 S(Y)에 대해 Y$\subseteq$X이고 X-Y=D라고 가정.

>> R(X) = R(D,Y)

이때 R(D,Y)에 대한 S(Y)로의 디비전은 S(Y)의 모든 튜플에 연관되는 R[D]의 튜플을 선택하는 것임.

정의는 다음과 같다.

• $R\div S = \{ t | t \in \Pi_D(R) \wedge t·s\in R\space for\space all\space s\in S\}$

나누어지는 릴레이션(R)은 나누는 릴레이션(S)의 모든 애트리뷰트(Y)를 공통으로 포함하고 있음.

 

1.2.5. 개명 연산(RENAME, $\rho$)

관계 대수 연산의 결과로 만들어지는 릴레이션은 이름이 없음.

한번에 하나씩 실행하고 싶은 경우 중간 결과로 만들어진 릴레이션을 나타내는 이름이 필요하고, 이름을 붙여주는 연산을 '개명'이라 함. 다음과 같이 정의됨.

• $\rho_S(E)$
• $\rho_{S(B1, B2, ..., Bm)}(E)$

두 식중 위의 식은 E를 실행해 만들어지는 결과 릴레이션의 이름을 S로 지정하는 것이고, 아래 식은 결과 릴레이션의 이름을 S로 지정하면서 애트리뷰트 이름을 각각 B1, B2, ..., Bm으로 변경하는 것임.

관계 대수식 E 자리엔 릴레이션이 들어갈 수 있으며, 이름, 이름+애트리뷰트 이름, 애트리뷰트 이름을 변경하는 용도로 사용가능 함.

 

 

1.3. 기본 연산과 복합 연산

합집합, 차집합, 카티션 프로덕트, 실렉트, 프로젝트 연산을 '기본 연산'이라 하고, 조인, 교집합, 디비전 연산을 '복합 연산'이라 함. 기본 연산은 다른 연산으로 대체가 안되며, 복합 연산은 기본 연산을 이용해 대체 할 수 있는 점이 다름.

 

 

1.4. 관계 대수의 확장

1.4.1. 세미 조인과 외부 조인

자연 조인의 변형으로 '세미 조인(Semijoin, ⋉)'과 '외부 조인(Outerjoin, ⟗ 또는 $⋈^+$)'이 있음.

R에 대한 S의 세미조인(R⋉S)은 R과 S를 자연 조인한 결과에 R의 애트리뷰트로 프로젝트한 것과 같으며, 의미상으로 S와의 자연 조인에 참여할 수 있는 R의 튜플만 선택하는 것과 같음. 세미 조인은 순서가 중요함.

외부 조인은 보통의 조인(내부 조인)을 확장한 개념으로, 어떤 튜플이 조인할 상대 릴레이션에 대응되는 튜플이 없을 경우 제외시키지 않고 상대를 널 튜플로 만들어 결과 릴레이션에 포함 시킴. 결과적으로 두 릴레이션에 있는 튜플들이 전부 결과 릴레이션에 들어감.

'좌측 외부 조인(Left ~ , ⟕)'과 '우측 외부 조인(Right ~, ⟖)'은 각각 왼쪽, 오른쪽의 릴레이션만 다 보이게 하는 용도로 쓰임.

 

1.4.2. 외부 합집합(Outer-union, $\cup ^+$)

완전하게 합병 가능하지 않은 두 릴레이션을 합집합으로 만드는 것. 즉 부분 합병 가능한 두 릴레이션의 튜플들을 합집합 하는 것임. 확장된 애트리뷰트에 해당되는 값이 없는 튜플들은 널 값으로 채워짐.

 

1.4.3. 집계 연산

기본 관계 연산만으로 원하는 릴레이션을 쉽게 정의할 수 없어 추가로 요구되는 연산들로, 이 연산에는 수학적인 집계 함수(Aggregate Function)로서 SUM, AVG, MAX, MIN, COUNT 등이 있음. 집계 함수 외에 지정한 애트리뷰트 값에 따라 튜플들을 그룹 짓게 하는 그룹핑 함수 GROUP이 있음. 그룹핑 함수는 집계 함수와 함께 쓰여서 그룹지은 다음 평균을 구하는 식으로 사용 가능함. 일반적인 형식은 $G_AF_B(E)$. E는 관계 대수식이며 F는 집계 함수, B는 집계 함수 적용 대상 애트리뷰트, G는 그룹핑 함수, A는 그룹핑 애트리뷰트임.