[데이터베이스] 함수적 종속성의 적용

함수적 종속성의 추론 규칙

주어진 함수적 종속성으로 추가적으로 성립하는 다른 함수적 종속성들을 추론할 수 있다. 

 

암스트롱의 추론 규칙들

가장 기본이 되는 규칙이다. 이 규칙들을 바탕으로 다른 모든 추론 규칙들을 추론해 낼 수 있다. 

 

A1. 재귀성의 규칙 

$Y \subseteq X이면, X \rightarrow Y이다.$

 

A2. 부가성의 규칙

$X \rightarrow Y이면, XZ \rightarrow YZ이다.$

 

A3. 이행성의 규칙

$X\rightarrow Y이고, Y \rightarrow Z이면, \rightarrow Z이다.$

 

위의 규칙들을 다음 릴레이션을 통해 설명해 보고자 한다. 

A	B	C
1	1	ㄱ
1	2	ㄴ
1	2	ㄹ
2	1	ㄴ
1	2	ㄹ

A1. 재귀성의 규칙은 어찌 보면 당연하다. AB($A \cup B$) $\rightarrow$ A에서 $t_{1}[AB] = t_{2}[AB]$라는 말 자체에 

$t_{1}[A] = t_{2}[A]$라는 의미가 내포되어 있다. 실제로 어떤 $t_{k}[AB]$를 골라도 $t_{1}[A] = t_{2}[A]$, $t_{1}[B] = t_{2}[B]$가 성립함을 확인해 볼 수 있다.

 

A2. 부가성의 규칙은 말 그대로 부가적인 정보가 추가된 것이다. 

$Z \rightarrow Z$인 것은 자명하기 때문에, $X \rightarrow Y$일 때,양 쪽에 Z를 추가한다고 해서 종속성이 달라지거나 하지 않는다. 

 

A3. 이행성의 규칙은 삼단 논법과 비교해 보면 쉽게 이해할 수 있다. 

 

추가적인 추론규칙들. (위의 A1~3추론 규칙들을 이용해 추론 가능하다.)

분해규칙: $X \rightarrow YZ$ 이면, $X \rightarrow Y$이고, $X \rightarrow Z$이다. 

이는 A1 재귀성의 규칙과 A3 이행성의 규칙을 이용하면 쉽게 증명 가능하다. 우선 재귀성의 규칙에 의해

$YZ \rightarrow Z$, $YZ \rightarrow Y$이고, 이행성의 규칙에 의해 $X \rightarrow Y$, $X \rightarrow Z$가 성립된다. 

 

합집합 규칙: $X \rightarrow Y$이고, $X \rightarrow Z$이면, $X \rightarrow YZ$이다.

이는 A2부가성의 규칙과 A3 이행성의 규칙으로 증명이 가능하다. 우선 $X \rightarrow Y$의 양 변에 X를 더해주고, $X \rightarrow Z$의 양 변에 Y를 더해주면, $X \rightarrow XY$, $XY \rightarrow ZY$가 되고, 이를 이행성의 규칙으로 연결하면, $X \rightarrow ZY$가 된다. 

 

의사 이행성 규칙: $X \rightarrow Y$이고, $WY \rightarrow Z$이면, $WX \rightarrow Z$이다.

이 역시 A2 부가성의 규칙과 A3 이행성의 규칙으로 설명이 가능하다. $X \rightarrow Y$에서 양 변에 W를 더해주면, $WX \rightarrow WY$가 되고 이 명제와 $WY \rightarrow Z$를 이행성의 규칙으로 연결시켜주면 된다. 

 

 

함수적 종속성 집합 F의 폐포(closure) $F^{+}$

-F로부터 추론 가능한 모든 함수적 종속성들의 집합

 

-sql문으로 함수적 종속성을 검사할 수 있다. (물론 많은 연산이 필요할 것이다.)

애트리뷰트 A와 B의 함수적 종속성을 검사하려면, A와 B를 프로젝션 시켜준 후, distinct로 중복을 제거해 주고, A로 groupby한다. 이 때 grouping된 값들이 모두 하나이면, B는 A에 대해 함수적 종속성을 가진다고 할 수 있다.

 

-보통 함수적 종속성은 문제에서 주어진다. 

 

 

F 하에서 속성(attribute) 집합 X의 폐포(closure of X under F): $X^{+}$

함수적 종속성 집합 F를 사용해 X에 의해 함수적으로 결정되는 모든 애트리뷰트들의 집합

 

폐포는 구하는 알고리즘이 따로 존재한다. 

함수적 종속성 집합 F가 주어졌다고 할 때, 

 

$X^{+}$ := $X$

do

   old$X^{+}$ := $X^{+}$

   for F 안에 있는 각 함수적 종속성 $Y \rightarrow Z$ 에 대하여

       if $Y \subseteq X^{+}$ then $X^{+} := X^{+} \cup Z$

while (old$X^{+}$ != $X^{+}$)

 

알고리즘 내에 이행성의 규칙이 녹아들어가 있음을 알 수 있다. 

 

예를 들어 F가 {A->B, AB->C}이고, A의 폐포를 구한다 하면,

1) 우선 $X^{+}$에는 {A}가 들어있다. 

2) 첫번째 loop에서 A->B가 있고, 현재 폐포에 A가 있으니 B가 추가된다. $X^{+}$ = {A, B}

3) 두번째 loop에서 AB->C가 있고, 현재 폐포에 A, B가 있으니 C가 추가된다. $X^{+}$ = {A, B, C}

4) 세번째 루프에선 아무 것도 추가되지 않는다. 따라서 old$X^{+}==X^{+}$가 되어 루프를 빠져나온다.