[데이터베이스] Relational Database Design

함수 종속(Functional Dependency)

relation 내의 attribute X와 Y에 대해 X가 Y의 값을 unique 하게 결정하여 X->Y가 성립되는 경우 함수 종속이라고 한다.

Armstrong's inference rules

 다음 추론 규칙들은 일종의 공리 처럼 여겨지며, sound / complete 한 추론 규칙들을 만드는데 사용된다. 따라서 모든 추론 규칙들은 아래 3개 규칙으로 구성되므로 어떤 규칙이든 아래 3개 규칙의 구조로 분해될 수 있다고 한다.

1. Reflective : if X ⊇ Y , then X -> Y
2. Augmentation : if X -> Y, then XZ -> YZ
3. Transitive : if X -> Y and Y->Z, then X->Z

쓸만한 추론 규칙들을 소개한다. 이들은 언급한 3개 추론 규칙에서 유도할 수 있다.

• Decomposition : if X->YZ, then X->Y and X->Z
• Union : if X->Y and X->Z, then X->YZ
• Pseudotransitivity : if X->Y and WY->Z, then WX->Z

이 규칙들을 정리하면 다음과 같다.

규칙명	조건	결과
Reflective	X ⊇ Y	X -> Y
Augmentation	X -> Y	XZ -> YZ
Transitive	X -> Y and Y->Z	X->Z
Decomposition	X->YZ	X->Z
Union	X->Y and X->Z	X->YZ
Pseudotransitivity	X->Y and WY->Z	WX->Z

Closure

클로저는 relation R에 대한 모든 함수 종속 관계 F로부터 추론될 수 있는 함수 종속 관계의 집합 F⁺을 의미한다.

Attribute 클로저 X⁺는 X로부터 함수 결정될 수 있는 모든 어트리뷰트를 의미한다.

다음 영상을 보면 클로저 개념이 명확히 이해된다. https://www.youtube.com/watch?v=TWAiz3BWHsw 

ex) R(A, B, C, D, E) & F { A->BC, CD->E, B->D, E->A }

1. A->A   B->B   C->C   D->D   E->E
2. A->B, A->C ( Decomposition )
3. A->D ( A->B(2) & B->D | Transitive )
4. A->CD (A->C(2) & A->D(3) | Union )
5. A->E (A->CD(4) & CD->E | Transitive)
6. A->ABCDE(A->A(1) & A->B & A->C(2) & A->D(3) & A->E(5) | Transitive ) : candidate key
7. E->ABCDE(E->A & (7) | Transitive ) : candidate key
8. CD->ABCDE ( CD->E & (8) | Transitive ) : candidate key
9. BC->CD ( B->D + C | Augmentation )
10. BC->ABCDE ( BC->CD{9} & (8) | Transitive ) : candidate key

Function Dependency의 동등성(Equivalence)

FD F 와 G에 대해 다음 조건을 만족하면 동등하다고 한다.

• F에 속하는 모든 함수 종속이 G로부터 추론될 수 있다. ( F⁺ ⊆ G⁺)
• G에 속하는 모든 함수 종속이 F로부터 추론될 수 있다. ( G⁺⊆ F⁺)

위 경우 F⁺ = G⁺가 성립하므로 두 함수 종속 집합 F와 G는 동등하다.

둘 중 하나의 관계만 성립하면 cover 한다고 한다. F가 G를 커버하고, G가 F를 커버하면 F = G가 된다.

Minimal Cover

 클로저는 최대 함수종속을 구하기 때문에 A->A 와 같은 다소 trivial 한 종속 관계도 포함한다. 따라서 전반적인 함수 종속의 크기가 커지기 때문에 이를 직접 이용하기는 문제가 있다. 따라서 실제로 함수 종속을 다룰 때는 Minimal Cover을 이용하여 다루게 된다.

Functional Dependency set F 및 F에 속하는 X->A 에 대해 X ⊇ Y 인 attribute Y 에 대해 F 가 논리적으로
( F - (X->A) U { (X - Y) -> A} ) 을 imply 하면 Y는 extranous 하다.

X = YZ 에 대해 F = { X->A, Z->A } 이면 YZ->A, Z->A 이므로 Y는 extranous attribute 이다.

Minimal Cover은 다음 조건을 만족한다.

1. F 내의 모든 함수 종속은 우측(RHS) 에 single attribute을 가진다. ( A->B 꼴 )
   • A->B, B->C, A->C 꼴로 나타난다.
2. X⊇Y 인 Y에 대해 X->A를 Y->A로 대체하더라도 F와 동등한 dependency 집합을 가지는 Y가 없다.
   • X = YZ에 대해 X->A 이고 일련의 추론 규칙에 의해 Z->A 라면 X->A는 Z->A로 치환될 수 있다.
3. F 내에서 어떤 dependency를 제거하는 경우, 기존의 F와 동등하지 않은 상태를 만족한다.
   • A->B, B->C, A->C에서 A->C는 나머지 둘에 의해 추론되므로 제거해도 된다.

 

ex) E : { B->A, D->A, AB->D }

셋 다 canonical form 이므로 첫번째 규칙을 만족한다.

B ->A에 대해 BB -> AB (Augmentation) 이므로 BB->AB & AB->D 로 B->D 가 성립. 따라서 AB->D는 B->D로 표현 할 수 있다. 이 경우 { B->A, D->A, B->D } 집합이 된다.

B->A는 B->D & D->A (Transitive) 에 의해 추론될 수 있으므로 제거해도 된다.

따라서 E에 대한 Minimal set은 { D->A, B->D } 가 된다.

 Bottom-Up Design 방식

모든 가능한 Function Dependency가 알려져 있다고 가정한다.

• minimal set 을 구한다.
• minimal set으로부터 3NF 혹은 BCNF을 생성한다.
• 경우에 따라 FD에 존재했던 함수 종속관계 중 일부가 소실될 수 있는데, 이를 다시 되살린다.

목표는 다음과 같다.

• Lossless Join : 기존 데이터에 대해 손실되거나 추가되는 데이터가 없어야 한다.
• Dependency preservation property : relation을 BCNF로 변경하는 과정에서 일부 dependency가 소실될 수 있는데, 이러한 함수 종속을 어플리케이션 수준에서라도 반드시 살려야 한다.
  
  • A#B->C# 에 대해 C#->B 의 종속 관계가 있었다면 BCNF에서는 A#->C#, C#->B의 형태로 분리된다. 분리된 두개의 함수 종속을 조합한다고 해도 원 종속 관계인 A#B->C#은 되살릴 수 없으므로 소실된다. 이러한 정보는 어플리케이션 수준에서 반드시 되살리도록 구현해야 한다.

---

Universal Relation Schema

 데이터베이스 내의 모든 attribute을 포함하는 relation schema. R = {A1, A2, A3 ... , An} 꼴로 나타난다. 원래 서로 다른 relation에 대해서는 attribute 이름의 중복이 가능한데, Universal Relation Schema에서는 하나의 relation에 대해 나타내야 하므로 이를 옮기는 과정에서 이름을 unique 하게 변경해줘야 한다.

Decomposition 

 Universal Relation Schema R을 D = {R1, R2, R3 ... , Rn} 꼴로 분해하는 과정으로, 함수 종속 관계에 의해 relational database schema 형태를 띄게 된다.

 R 내의 각각의 attribute들은 최소한 하나의 relation Ri 에 포함됨으로써 소실(lost)되지 않도록 해야한다. Decomposition의 목적은 R을 Ri로 나누어 각각을 3NF 혹은 BCNF로 나타내는 것이다. 이 과정에서 spurious tuple (원래 relation에는 존재하지 않는 튜플. 데이터 중복에 의해 발생) 이 생성되는 것을 방지해야 한다.

Dependency Preservation Property of a Decomposition

 주어진 relation R에 속하는 함수 종속 F에 대해 R의 projection Ri에 대한 함수 종속 F는 p_Ri(F) 로 나타낸다. p_Ri(F) 의 함수 종속 X->Y들은 F⁺에 속하며, X와 Y는 모두 Ri 내에 존재하는 attribute들이다. 

decomposition D = {R1, R2, R3 ..., Rn} 에 대해 각각의 Ri에 대한 F들을 union한 후 클로저를 구한 것과 그냥 F의 클로저를 구한 것이 동일한 경우, dependency-preserving하다고 한다. Decomposition 들이 3NF 형태를 취하고 있는 경우, dependency-preserving이 보장되는 것으로 알려져 있다 (Claim 1).

dependency-preserving : ((π_R1(F)) ∪ . . . ∪ (π_Rm(F)))⁺ = F⁺

Non-additive (Lossless) Join Property of Decomposition

 decomposition D = {R1, R2, R3 ..., Rn} 및 R에 대한 relation state r 에 대해 각각의 relation에 대한 projection 들을 natural join 했을 때 원래 relation state인 r이 나오면 Non-additive Join 이라고 한다. Lossless 라는 의미는 튜플을 잃는 다는 것이 아니라 정보를 잃는다는 것으로, 구체적으로 원 관계에는 없는 spurious tuple이 추가되는 것을 의미한다.

 Natural Join은 각 relation에 속해 있는 이름이 동일한 key attribute을 중심으로 조합하기 때문에 Non-additive join을 위해서는 Primary-Reference Key 기반으로 relation을 분리해야 한다.

Non-additive Join : * (π_R1(r), ..., π_Rm(r)) = r

 현재 relation state r 이 lossless join인지 아닌지를 판단할 때는 Matrix을 만들어서 체크한다. Ri에 속하는 값들을 순서대로 각 행에 채워넣은 후 각각의 열에 대해 일종의 join 동작을 수행하면서 모든 attribute의 값이 생긴 행이 발생하는지 여부를 검사한다. 만약 모든 attribute 값이 생기는 행이 생기면, natural join을 통해 모든 attribute을 얻을 수 있다는 것을 의미하므로, Non-additive Join이 된다.

ex )

R = {Ssn, Ename, Pnumber, Pname, Plocation, Hours}
R1 = EMP = {Ssn, Ename}
R2 = PROJ = {Pnumber, Pname, Plocation}
R3 = WORKS_ON {Ssn, Pnumber, Hours}

R	Ssn	Ename	Pnumber	Pname	Plocation	Hours
R1	o	o
R2			o	o	o
R3	o		o			o

R1과 R3을 join하면 R3의 Ename을 채울 수 있다.

R	Ssn	Ename	Pnumber	Pname	Plocation	Hours
R1	o	o
R2			o	o	o
R3	o	o	o			o

R2와 R3을 join 하면 Pname과 Plocation을 채울 수 있다.

R	Ssn	Ename	Pnumber	Pname	Plocation	Hours
R1	o	o
R2			o	o	o
R3	o	o	o	o	o	o

R3에 해당하는 행의 모든 attribute가 존재하므로, 현재 Decomposition의 Ri 들은 Non-additive Join을 만족한다.

---

Bottom-Up 방식의 Relational Database Schema Design

 위에서는 Universal Relation Schema 라는 거대한 Relation을 작은 단위로 쪼개는 방식으로 스키마를 구성했는데, 반대로 작은 단위에서 큰 단위로 조합하는 것도 가능은 하다.

1. F에 대한 Minimal Cover 을 구한다.
2. left hand side가 같은 함수 종속끼리 모아서 해당 종속에 속하는 attribute 들이 속한 relation schema로 만든다. 예를 들어 A->B, A->C, A->D 가 있다면, A->BCD (union) 이므로 Ri(A,B,C,D) 로 독립시킨다.
3. Ri를 만들고 보니까 어떤 Ri도 R의 key attribute을 포함하지 않고 있으면 key attribute을 가지고 relation schema를 더 만들어서 key attribute가 없어지지 않도록 Dependency preserving을 보장한다.
4. redundant relation 들을 모두 제거한다.

---

NULL Value 문제

 위에서 설명한 방식에서는 Null Value을 표현할 수 없다. 이를 표현하기 위해서는 Outer Join을 수행하여 자신이 원하는 쪽의 relation에 NULL을 표현할 수 있도록 만든다.