[Database Systems] Normalization

Normalization

Normal Forms: 바람직한 형태의 테이블

Normalization: 테이블을 더 작고 더 바람직한 나누는 것

Lossless Join Property: 나눠진 것을 Join했을 때, 나누기 전과 완전 동일한 속성

Dependency Preservation Property: 의존성이 보존되는 것

Prime Attribute: Candidate key에 속하는 attribute

 

First Normal Form (1NF)

1NF: Relation에 속한 모든 Domain이 Atomic value로만 되어있는 것. 즉, Relation의 모든 Attribute value가 Atomic value로만 되어있는 Normal form

Second Normal Form (2NF)

Full Functional Dependency: X->Y라는 FD가 있을 때, X에 있는 어떤 Attribute 집합을 제외했을 경우 FD가 유지되지 않는다면, X->Y는 Full Functional Dependency이다. 

Partial Functional Dependency: X->Y라는 FD가 있을 때, X에 있는 몇 Attribute 집합을 제외해도 FD가 유지된다면, X->Y는 Partial Functional Dependency이다. 

 

2NF: Relation이 1NF이면서, 모든 Nonprime attribute가 Candidate key에 Fully functional dependent한 Normal form

이 예시에서는 Tax_rate가 {County_name, Lot#}에 Fully FD하지 않다. Lot#를 Candidate key에서 제외해도 FD가 유지되기 때문이다.

따라서 다음과 같이 LOTS에서 Tex_rate를 제외한 Relation과, {County_name, Tax_rate}로 구성된 Relation 두개로 Normalization한다. 결과적으로 두 Relation은 모두 2NF가 된다.

Third Normal Form (3NF)

Transitive Dependency: A->B이고 B->C일 때, A->C를 만족하는 관계

3NF: Relation이 2NF이고, 모든 Nonprime attribute가 Candidate key에 Transitive Dependency를 만족하지 않는 Normal Form

이 예시에서는 Nonprime attribute가 Price이고, Candidate key가 {County_name, Lot#}인 상황에서,

{County_name, Lot#} -> Area 이고,

Area -> Price 이며,

{County_name, Lot#} -> Price인 Transitive Dependency가 존재한다. 

이 Transitive Dependency를 제거하기 위해서 LOTS1에서 Price를 제거하고, {Area, Price} 구성된 Relation 2개로 다음과 같이 나눈다. 결과적으로 두 Relation은 모두 3NF가 된다.

Boyce-Codd Normal Form (BCNF)

BCNF: Relation에서 Determinant(X->Y에서 X)가 모두 Candidate key인 normal form이다. 3NF에서 Candidate key가 여러 개 존재하고, 서로 중첩되는 경우에 적용하는, 강한 3NF라고도 한다. 모든 BCNF가 Dependency Preservation Property를 충족시키는 것은 아니다.

- BCNF의 제약조건

1. 모든 Nonprime attribute는 각 Key에 Fully functional dependent해야 한다.

2. 모든 Nonprime attribute는 그 자신이 부분적으로 들어가 있지 않은 모든 key에 대하여 fully functional dependent해야 한다.

3. 어떤 Attribute도 Nonprime attribute에 Fully functional dependent할 수 없다.

이 예시에서는 Area->County_name이라는 FD가 존재하는 데, Area는 Candidate key가 아니므로, 다음과 같이 LOTS1A에서 County_name을 제외한 Relation과, {Area, County_name}으로 구성된 두 Relation으로 나눈다. 결과적으로 두 Relation은 BCNF가 된다. 하지만 기존에 존재하던 FD2가 보존되지 않는다.

 

Fourth Normal Form (4NF)

Multivalued Dependency: A, B, C 3개의 Attribute를 가진 Relation에서 어떤 가상의 composite attribute {A, C}에 대응하는 B 값의 집합이 A 값에만 Dependent하고, C 값에는 무관하면, B는 A에 Multivalued dependent하다고 하고, A->>B로 표기한다.

4NF: Relation에 Multivalued Dependency A->>B가 성립하는 경우 Relation의 모든 속성이 A에 FD를 만족하는 Normal Form

이 예시에서는 {Ename, Dname}에 대응되는 Pname이 Ename에 Dependent하므로, Ename->>Pname이고,

{Ename, Pname}에 대응되는 Dname이 Ename에 Dependent하므로, Ename->>Dname이다.

그러므로 이러한 Multivalued Dependency을 없애기 위해 {Ename, Pname}, {Ename, Dname}로 relation은 다음과 같고, 결과적으로 모든 Relation이 4NF이 된다.

Fifth(Projection-Join) Normal Form (5NF)

Join Dependency: 어떤 Relation의 Attribute에 대한 부분 집합, A, B, ..., C가 있다고 하자. 이때 만일 Relation이 자신의 Projection A, B, ..., C를 모두 Join한 결과가 자신과 동일한 경우 Relation은 Join Dependency를 만족한다고 한다.

5NF: Relation의 모든 Join Dependency가 Candidate key를 통해서만 성립되는 Normal Form. Join에 의한 새로운 Dependency를 막기 위해 Normalization된 Normal Form이다.

이 예시에서의 Relation은 다음과 같은 Project R1, R2, R3를 모두 Join한 결과와 같다.

따라서 SUPPLY는 SUPPLY의 Projection인 R1, R2, R3에 대한 Join Dependency를 가지며, R1, R2, R3 각각은 5NF이다.