본문 바로가기

Library/Database

종속성 유지 분해

종속성 유지 분해란, 새로운 튜플(tuple)을 삽입하거나 혹은 어떤 튜플을 수정하고자 할 때, 단지 단일 관계에 속한 인스턴들 자체만 조사하기만 하면, 모든 FD들이 만족되는지를 검증해 줄 수 있다는 것을 의미한다(여기서 튜플을 삭제하는 경우는 어떠한 FD의 위반을 유발하지 않는다).

어떤 관계 스키마 R이 속성(attribute)들의 집합인 X와 Y로 구성된 두 개의 스키마로 분해되고, 이 R에 정의된 FD들의 집합을 F라고 하자. X에 대한 F의 프로젝션은 X에 속하는 속성들만을 포함하는 폐포 F+(F만이 아님)에 속하는 FD들의 집합으로 정의된다. 여기서 편의상 X에 대한 F의 프로젝션을 Fx로 표기하기로 한다. 이제 F+에 속하는 어떤 종속성 U → V가 Fx에 속하기 위해서는, U와 V에 속하는 모든 속성들이 X에 속해야 한다.

FD들의 집합인 F를 갖는 관계 스키마 R을 속성들의 집합인 X와 Y로 구성된 두 개의 스키마로 분해할 때,  이 분해가 (Fx ∪ Fy)+ = F+를 만족할 경우, 이러한 분해를 종속성 유지 분해라고 한다. 즉 Fx와 Fy에 속하는 종속성들을 각각 얻은 후, 이들을 합집합한 결과의 폐포를 계산할 경우, F의 폐포에 속하는 모든 종속성들을 얻게 된다. 따라서 Fx와 Fy에 속한 종속성들만을 테스트하면 F+에 속한 모든 FD들도 역시 만족된다는 것을 보장할 수 있다. 여기서 Fx를 검증하기 위해서는 단지 관계 X(즉 삽입되는 그 릴레이션인)만 조사하면 된다. 이와 유사하게 Fy를 검증하기 위해서는 관계 Y만 조사하면 된다.

F의 프로젝션을 계산하는 과정에서 폐포(closure) F+를 왜 고려해야 되는 이유를 알기 위해 다음 예제를 살펴보자. 속성 ABC로 구성된 관계 R이 AB와 BC로 각각 구성된 두 개의 릴레이션으로 분해했다고 가정하자. R에 대한 FD들의 집합 F에는 A → B, B → C, C → A가 포함되었다고 하자. 이들 종속성들 중에서, A → B는 F(AB)에 포함되어 있으며, B → C는 F(BC)에 포함되어 있음을 알 수 있다. 여기서 이 분해는 과연 종속성을 유지할 수 있을까? 특히, C → A는 어떠한가? 직관적으로 보면 이 종속성은 F(AB)와 F(BC)에 열거된 종속성에 의해 유도 되지 않는다.

F의 폐포는 F 자체에 있는 모든 종속성들 외에 A → B, B → C, C → A를 포함하고 있다. 결과적으로 F(AB)는 역시 B → A를 포함하며, F(BC)는 C → B를 포함하고 있다. 따라서 F(AB) ∪ F(BC)는 A → B, B → C, B → A, C → B를 포함하게 된다. 이제 F(AB)와 F(BC)에 속한 종속성들의 폐포에는 C → A도 포함되게 된다(즉, C → B, B → A, 전이 법칙(transitive)에 의해 유도된다). 따라서 위의 분해는 종속성 C → A를 그대로 유지할 수 있다.