[DB] Chap. 15 Relational Database Design Algorithms and Further Dependencies

Further Topics in Functional Dependencies: Inference Rules, Equivalence, and Minimal Cover

 

함수 의존성(Functional Dependency) X->Y

속성의 집합 X는 속성의 집합 Y를 functionally determines한다.

X의 값이 Y값을 유일하게 결정할 때

FD의 성질을 결정하는 것이 목적

 

두개의 튜플 t1, t2에 대해 r(R): 만약 t1[X]=t2[X]이면 t1[Y]=t2[Y]

relation R에서 함수 종속 F가 X->Y를 모든 legal relation 상태 r에서 hold함.

 

Armstrong's inference rules

IR1(Reflexive): Y가 X의 부분집합이면 X->Y

IR2(Augmentation): X->Y이면 XZ->YZ

IR3(Transitive): X->Y이고, Y->Z이면 X->Z

 

위의 법칙은 sound and complete set of inference rules

 

그외의 법칙

(Decomposition) X->YZ이면 X->Y이고 X->Z이다.

(Union): X->Y이고 X->Z이면 X->YZ이다.

(Psuedotransitivity): X->Y이고 WY->Z이고 WX->Z

 

Closure(폐소, 닫힘)

F에서 추론할 수 있는 함수 종속성 집합을 F+. closure라고 한다.

속성 X의 집합의 closure에서 X+가 R의 속성을 모두 결정할 수 있으면, X는 키이다.

 

Equivalence

두 FDs의 집합 F와 G는 equivalence하다.

-모든 F의 FD가 G로부터 추론될 수 있을 때.

-모든 G의 FD가 F로부터 추론될 수 있을 때.

-즉, F+ = G+일 떄 equivalent하다.

 

F는 G를 cover한다. if) 모든 G의 FD가 F로부터 추론될 수 있을 때.

 

F와 G의 Equivalence는 F cover G and G cover F

 

FD의 minimal

1. 오른쪽이 하나의 속성

2. 더이상의 삭제 불가능

3. F의 어떤 X->A형태도 부분집합인 Y->A로 대체 불가능