[데이터베이스/Database] 함수 종속성과 폐포(암스트롱 공리)

함수 종속성(Functional Dependency : FD)

: 일종의 무결성 제약조건(IC, Integrity Constraints)이다.

릴레이션 스키마 R이 있고 X, Y는R에 속한 속성들의 집합이며 공집합이 아니라고 가정했을 때,

R의 인스턴스 r에서 r에 있는 모든 가능한 투플들의 쌍 t1과 t2에서

if t1.X = t2.X, then t1.Y = t2.Y 인 경우 'X가 Y를 함수적으로 결정한다'라고 말한다.

기호로는 X → Y라고 표기한다.

 

* 즉, X → Y인 경우, 투플끼리 X가 같으면 Y도 무조건 같아야 한다.

 

 

 

키, 기본키, 수퍼키와 함수 종속

K: 키 속성 집합, Y: 모든 속성들의 집합, S: 속성들의 집합

K → Y : 키는 스키마에 있는 모든 속성들을 함수종속함

S → Y : S는 수퍼키(유일성은 만족하지만 최소성은 만족하지 못하는 속성)

 

* 개념적 DB 설계에서 E-R 모델을 이용하여 ERD(Entity-Relationship Diagram) 작성. 

이 때 ERD에서는 기본키를 표기하기 위해 속성 이름에 밑줄을 긋지만, 함수 종속 관계는 ERD로 표현이 불가능함.

즉, 개념적 DB 설계 단계에서 (함수 종속 관계가 발생시키는) 중복성 문제를 파악할 수 없음.

설계상의 문제점 해결과 더 좋은 설계를 위해 정규화 기법 필요.

함수 종속 관계를 이용하여 주어진 스키마가 적정 수준의 정규형에 속하는지 판단할 필요가 있음.

 

 

 

추론

: 주어진 함수종속 관계를 이용하여 새로운 함수종속들을 계산하는 것.

스키마에 있는 모든 함수종속 관계로 제 몇 정규형인지 판단하기 위해 추론 과정을 거침.

 

ex)

Workers (ssn, name, did, lot, since)

S→SNDLC (C : since), D→L일 때,

S→D이고, D→L임을 이용해 S→L 를 추론함

 

 

F의 폐포(closure of F : F+)

: FD 집합 F 에 의해 추론될 수 있는 모든 FD들의 집합.

F 의 폐포 F+는 암스토롱의 공리 라고 하는 3가지 법칙을 반복 적용하여 계산 가능.

 

 

암스트롱의 공리(Armstrong’s Axiom : AA)

- 재귀규칙: X ⊇Y 이면, X →Y

- 부가규칙: X →Y 이면, X Z →Y Z

- 이행규칙: X →Y 이고 Y →Z 이면, X →Z

 

알아두면 편리한 추가 규칙

- 결합규칙 : X → Y 이고 X → Z 이면, X → Y Z

- 분해규칙 : X → Y Z 이면, X → Y 이고 X → Z

- 가이행 규칙 : X → Y 이고 Y Z → Ω 이면, X Z → Ω

 

* X, Y, Z : 릴레이션 스키마 R 에 속한 속성들의 집합, XY : X ∪Y

 

 

 

암스트롱의 공리는 sound(정당)하고 complete(완전)하다.

- Sound : FD 집합 F에 AA가 적용될 때에 F+에 있는 FD들만을 생성

- Complete : FD 집합 F에 AA 규칙들을 반복해서 적용하면, F+에 있는 모든 FD들을 생성

 

 

 

속성 X의 폐포(X+)

: X가 함수 종속하는 모든 속성들의 집합

함수 종속 X → Y 가 F + 에 속하는지를 알아보기 위해, F 에 대하여 속성 X 의 폐포 X + 를 계산하여 판단.

 

X+ 계산 Algorithm

 

   closure = X;

   repeat until (no change to closure) {

        if (U ⊆ closure and U → V ∈F )

            closure = closure ∪ V;

}