본문 바로가기
데이터베이스

[관계형 데이터베이스] - 함수 종속성 (Functional Dependency)

by CHML 2016. 11. 13.
1. 함수 종속성

관계형 데이터베이스의 설계에서 중복된 데이터가 최소화되도록 데이터베이스의 구조를 결정하는 것을 정규화 (normalization)라고 한다. 정규화된 데이터베이스가 그렇지 않은 데이터베이스에 비하여 더욱 효율적으로 데이터에 대한 연산을 수행할 수 있는 것은 매우 당연한 것이다. 이러한 데이터베이스의 정규화 과정에서 함수 종속성이라는 개념은 매우 중요하게 이용된다.

함수 종속성은 수학에서의 함수와 같이 두 필드의 집합이 many-to-one 관계로 사상되는 것을 말한다. 즉, 함수와 같이 어떠한 값을 통해 종속 관계에 있는 다른 값을 유일하게 결정할 수 있다는 것이다. 데이터베이스에서의 함수 종속성을 더욱 명확하게 정의하면 다음과 같다.


어떤 테이블 $R$에 존재하는 필드들의 부분집합을 각각 $X$와 $Y$라고 할 때, $X$의 한 값이 $Y$에 속한 오직 하나의 값에만 사상될 경우에 "$Y$는 $X$에 함수 종속 ($Y$ is functionally dependent on $X$)"이라고 하며, $X$→$Y$라고 표기한다.


예를 들어, 테이블에 [생일]과 [나이]라는 필드가 존재할 경우에 [나이] 필드는 [생일] 필드에 함수 종속이다. 즉, 생일을 알고 있다면, 나이에 대한 필드를 참조하지 않거나, 아예 필드를 유지하지 않아도 나이를 결정할 수 있다. 데이터베이스 설계 단계에서 함수 종속 관계에 있는 필드를 찾는다면, 그 만큼 중복된 데이터를 줄일 수 있다. 그러므로, 데이터베이스 설계 단계에서 각 정보들 간의 함수 종속 관계를 찾는 것은 매우 중요하다.


2. 함수 종속의 성질

어떠한 테이블 $R$에 대해 $X, Y, Z$라는 필드의 집합이 있을 때, 함수 종속은 다음과 같은 성질을 만족하며, 이를 암스트롱의 공리 (Armstrong's axioms)라고 한다.


  • augmentation: 만약 $X→Y$이면, $XZ→YZ$이다.

  • transitivity: 만약 $X→Y$이고 $Y→Z$이면, $X→Z$이다.

  • reflexivity: 만약 $Y$가 $X$의 부분집합이면, $X→Y$이다.

  • self-determination: 자기 자신은 자신에 의해 함수 종속적이다. 즉, $X→X$이다.

  • union: 만약 $X→Y$이고 $X→Z$이면, $X→YZ$이다.

  • decomposition: 만약 $X→YZ$이면, $X→Y$이고 $X→Z$이다.


관계형 데이터베이스는 이산수학의 relation 및 function의 개념을 이용하여 정의되었기 때문에 그 성질 또한 이산수학의 개념과 유사한 것을 볼 수 있다.


3. Closure 개념을 이용한 Super key 판별

어떠한 테이블에서 주어진 필드의 집합이 해당 테이블의 super key인지를 판별하기 위해 closure라는 개념을 이용할 수 있다. 어떠한 테이블의 모든 필드가 주어진 필드의 집합 $S$에 대해 함수 종속이라면, 주어진 필드의 집합 $S$는 해당 테이블의 super key라고 할 수 있다. 따라서, 함수 종속성과 암스트롱의 공리, closure 개념을 이용하여 super key를 판별할 수 있다. 예를 들어, 어떠한 테이블 $R(A, B, C, D, E, F)$에서는 다음과 같은 함수 종속성이 존재한다.



위에 주어진 함수 종속성을 이용하여 주어진 테이블에서 $\{A, B\}$가 super key인지를 판별하는 알고리즘은 다음과 같다.


1) 필드의 집합 $CLOSURE = \{A, B\}$를 정의한다.

2) 위의 주어진 함수 종속성에서 (1)에 해당하는 함수 종속 관계를 통해 $A→C$임을 알 수 있다. 그러므로, 필드의 집합인 $CLOSURE$에 $C$를 추가한다.

3) 함수 종속 관계 (2)에 대해서는 해당하는 사항이 없다.

4) 함수 종속 관계 (3)에 의해 $B→E$라는 사실을 알 수 있다. 그러므로, $CLOSURE$에 $E$를 추가한다.

5) 함수 종속 관계 (4)에 대해서는 해당하는 사항이 없다.

6-1) $CLOSURE$에 변화가 있었으면, [과정 2]로 이동하여 현재 $CLOSURE$ 집합에 대해 알고리즘을 다시 실행한다.

6-2) $CLOSURE$에 변화가 없었으면, 알고리즘을 종료한다.


알고리즘을 끝낸 후의 $CLOSURE$는 주어진 테이블의 속성 중에서 $D$가 빠진 $\{A, B, C, E, F\}$와 같다. 따라서, 필드의 집합 $\{A, B\}$는 해당 테이블의 super key가 아니다.