[Database Systems] Relational Database Design Algorithms

Relation Decomposition

relation schema은 database의 모든 attribute를 포함하고, 여기서 모든 attribute의 이름은 unique하다. 이 R을 D = {R_1, R_2, ..., R_m}으로 Decompose한다면, 각 R_i는 R의 subset을 포함한다. 그리고 R의 Attribute는 적어도 하나의 R_i에 포함된다. 각 R_i는 BCNF 또는 3NF가 되며, D는 R의 Decomposition이라고 불린다.

 

단 두개의 Attribute를 갖는 relation schema는 자동적으로 BCNF가 되지만, 문제점은 다른 Relation과 Join하였을 때 Spurious tuple이 발생할 수 있다는 것이다.

 

좋은 Relation database를 위한 추가적인 속성은 분해된 것을 Join해도 Spurious tuple이 생기지 않도록 하는 Lossless Join Property와 분해 해도 의존관계가 보존되도록 하는 Dependency Preservation Property이다.

 

Dependency Preservation

F를 R의 FD 집합이라고 하자.

R의 Decomposition을 D = {R_1, R_2, ..., R_m}라고 할 때,  F의 R_i Projection인 pi_(R_i)(F)들을 모두 Union 한 것의 Closure가 F의 Closure와 같다면, D는 Dependency-Preserving하다고 한다.

만약 Decomposition이 Dependency-Preserving하지 않다면, Relation들을 Join해야하는데, 실질적으로 비효율적인 방법이다.

 

Relational Decomposition into 3NF with Dependency Preservation

Minimal Cover: FD 집합 F와 의미상으로 동등한 FD 집합 G, G에서 어떠한 FD를 하나라도 제외시킨다면 F와 동등하지 않게 된다.

Minimal Cover G를 구하는 방법은 다음과 같다.

1. F에 있는 FD를 모두 Right-hand side에 하나의 Attribute만 존재하는 Canonical Form으로 만든다.

2. XY->A 형태의 FD들 중에서 F에서 XY->A를 제외하고 X->A를 포함시켜도 F와 동등하다면 XY->A를 X->A로 대체한다.

3. 나머지 X->A FD들 중 F에서 X->A를 제외해도 F와 동등하다면 X->A를 제외한다.

 

Dependency-Preserving하는 3NF로 Relation Decomposition하는 방법은 다음과 같다.

1. F에 대한 minimal cover G를 구한다.

2. 각 left-hand-side 에 대하여 X와 X의 right-hand-side들을 Union하여 하나의 relation schema로 만들고 X는 해당 Relation의 Key가 되도록 한다.

3. 만약 어느 relation에도 속하지 못한 attribute들이 있다면 그것들로 하나의 relation schema를 만든다.

Lossless Join Property

FD 집합 F를 따르는 Relation R의 한 State를 r이라고 하자.

R의 Decomposition을 D = {R_1, R_2, ..., R_m}라고 할 때, r의 R_i Projection인 pi_(R_i)(r)들을 모두 Join 한 것이 r과 같다면 D가 Lossless Join Property를 가진다고 한다.

 

Relational Decomposition into BCNF with Lossless Join Property

1. D를 R로 set

2. D에 BCNF가 아닌 relation schema 가 있다면 다음을 반복한다.

{

D에서 BCNF가 아닌 Q를 선택한다.;

Q에서 BCNF를 위반하는 FD X->Y를 찾는다.;

해당 X->Y를 (Q-Y) 와 (X합집합Y)의 두 relation schema로 대체한다.;

}

 

Decomposition D = {R_1, R_2}는 R의 FD 집합 F에 관하여 Lossless Join Property를 가진다는 것을 다음 특징과 일맥상통한다.

R_1와 R_2의 교집합에 존재하는 Attribute는 한 쪽에선 Key이자 다른 한 쪽에선 Foreign-key가 된다.

Lossless Join Property를 갖는 Decomposition D의 element R_i에 Lossless Join Property를 갖는 Decomposition을 적용한 것이 D_i라고 할 때, D에 있는 R_i를 D_i의 원소들로 대체한 D_2 또한 F에 대해  Lossless Join Property를 갖는다.

 

Dependency Preservation and Lossless Join Property

BCNF이면서, Dependency-Preserving하고, Lossless Join Property를 한꺼번에 만족하지 않는 사례도 존재한다. 그 예가 바로 위의 예이다.

Candidate Key를 {A, B}라고 하고, Nonprime attribute를 C라고 하자. 이는 3NF는 맞지만 BCNF는 아니다. BCNF를 만들려고 하면 BCNF와 Lossless Join Property는 만족하지만 FD1가 사라지기 때문에 Dependency-Preserving하지 않다. 이러한 경우에는 BCNF를 포기하고, Lossless Join Property와 Dependency Preservation Property를 만족하는 3NF가 되게 Decomposition을 수행하도록 할 수 있다. 그 알고리즘은 다음과 같다.

1. F에 대한 minimal cover G를 구한다.

2. 각 left-hand-side 에 대하여 X와 X의 right-hand-side들을 Union하여 하나의 relation schema로 만들고 X는 해당 Relation의 Key가 되도록 한다.

3. 만약 어느 relation에도 속하지 못한 Key들이 있다면 그것들로 하나의 relation schema를 만든다.

 

key를 찾는 알고리즘은 다음과 같다.

Key: 다른 attribute들을 함수적으로 결정하는 Attribute들의 집합

(K-A)+가 R에 있는 모든 attribute를 함수적으로 결정한다면, A가 없어도 모든 Attribute가 결정되는 것이므로, A는 Key에서 제외한다.

결과적으로 K는 Key의 집합이 된다.

 

Relational Decomposition into 4NF

1. D를 R로 set

2. D에 4NF가 아닌 relation schema 가 있다면 다음을 반복한다.

{

D에서 4NF가 아닌 Q를 선택한다.;

Q에서 4NF를 위반하는 의미적으로 중요하지 않은 MVD X->>Y를 찾는다.;

해당 X->Y를 (Q-Y) 와 (X합집합Y)의 두 relation schema로 대체한다.;

}