[#07] Normalization

학부 수업을 정리하기 위해 올리는 게시글으로, 잘못된 내용이 있을 시 지적해주시면 감사하겠습니다!

---

  여러가지 Schema 를 합쳐서 하나의 table 을 구축하는 경우 데이터의 불필요한 중복이 발생할 여지가 많다. 이러한 중복은 각각의 attribute 간의 functional dependency 에 의해 야기된다. (이하 FD라고 부름)

 

  Functional Dependency(FD)

특정 attribute 를 알고 있을 때, 다른 attribute 를 알 수 있는 dependent 한 관계를 FD 라고 한다.

●  K 가 R 의 super key 라면 K -> R 과 같은 FD 가 존재한다.

●  K 가 R 의 Candidate key 라면 K -> R 이지만, K 에 속한 임의의 attribute 를 a 라고 했을 때 K-a 는 R에 대한 FD 가 없다.

●  B 가 A의 subset 이면 A->B 는 trivial 하다.

●  A->B 이고 B->C 이면 A->C 임을 logically 하게 추론할 수 있는데(마치 삼단논법), 이러한 FD 들의 집합을 closure 이라고 한다. (FD 가 주어졌을 때, 해당 FD로부터 추론 가능한 모든 FD)

●  F의 closure 은 F+ 라고 표기한다.(notation)

 

  이러한 FD 는 다양한 연산 법칙이 존재한다.

●  Subset Property (Trivial)

:  만약 Y 가 X 의 subset 이면 X->Y 가 trivial 하다.

●  Augmentation

:  만약 X->Y 가 성립한다면 XZ->YZ 또한 성립한다.

●  Transitivity

:  만약 X->Y 가 성립하고 Y->Z 가 성립하면 X->Z 또한 성립한다.

●  Union

:  만약 X->Y 이고 X->Z 이면 X->YZ 가 성립한다.

●  Decomposition

:  만약 X->YZ 이면, X->Y 와 X->Z 가 성립한다.

●  Pseudo - transitivity

:  만약에 X->Y 가 성립하고 WY->Z 가 성립하면, WX->Z 또한 성립한다.

 

  예제를 통해서 살펴보자.

만약에 R = { A, B, C, G, H, I } 이고 F = { A->B,  A->C,  CG->H,  CG->I,  B->H  } 라고 주어졌다고 생각해보자.

● A->H 라는 FD 는성립하는가?

:  A->B 가 성립하고 B->H 가 성립하므로 Transitivity 에 의해 A->H 또한 이행적으로 성립한다.

● AG->I 라는 FD 가 성립하는가?

:  A->C 에서 augmentation 에 의해 AG->CG 가 성립함을 알 수 있다. 또한 CG->I 가 성립함을 이미 알고 있는데, transitivity 에 의해서 AG->I 가 성립함을 알 수 있다.

● CG->HI 라는 FD 는 성립하는가?

:  augmentation 에 의해서 CG->I 라는 FD 로부터 CG->CGI 가 성립함을 알 수 있다. 또한 CG->H 로 부터 CGI->HI 가 성립하는데, 이를 이용해서 CG->HI 가 성립함을 transitivity property 에 의해 알 수 있다.

 

 

  Lossy decomposition

Relation 을 decomposition 한 다음에 다시 원래대로 reconstruction 할 수 없는 경우를 Lossy decompositionb 이라고 한다. 우리는 Lossless join decomposition 에 주목해야 한다. Lossless join decomposition 은 Relation 을 decomposition 한 이후에 다시 reconstruct 하더라도 정보의 손실이 없는 것을 의미한다.

  Normalization 의 목표

데이터를 정규화한다는 것은 불필요하게 중복된 데이터를 허용하지 않음으로서 data integrity 를 유지할 수 있고, database 의 용량을 절약할 수 있다. 한마디로 말하면 정규화는 데이터 베이스에서 불필요한 중복된 요소를 제거해나가는 것으로, FD 들을 이용해서 Relation 을 decomposition 해서 다양한 이상현상이 발생하지 않도록 적용한다.

 

  First Normal Form [제 1 정규화]

First normal form 은 Relaton 의 Domain 의 모든 attribute 들이 atomic 하는 경우 성립한다. 예를 들어 dept_name 의 attribute 가 2 가지 이상 값을 가진다면 하나의 값만 가지도록 atomic 하게 분해해야 한다. course_name 과 dept_name 을 attribute 로 가지는 relation 이 있다고 했을 때, C programming 이라는 course_name 은 EE,CS 와 같이 dept_name  에 2개의 값이 존재할 수 있다. 이는 atomic 하지 않은 것으로 각각 C programming - EE,  C programming - CS 와 같이 atomic 하게 분해해야 한다.

 

  Second Normal Form [제 2 정규화]

First normal form 을 만족하는 table 에 대하여 Primary key 의 partial set 이 determinant 가 되어서는 안된다. PK 가 Composite Primary key 이면, 해당 Key 전체에 대하여 Dependent 해야 하는데 일부 subset 에 대해서만 Dependent 한 attribute 가 존재한 경우 이를 decompose 해야 한다. (partial functional dependency 가 존재하면 안된다.) 

예를 들어, takes 릴레이션은 takes_id, course_id, cource_name 을 attribute 로 가지고, ( takes_id, course_id ) 가 PK 인 상황을 생각해보자. 이 릴레이션을 관찰해보니 takes_id → course_id  이고, course_id → course_name 이다. 즉, Composite PK 의 일부인 partial set 에 대하여 dependency 가 존재하고 있으므로, Second Normal Form 을 만족하지 않아 분해해야 하는 것을 알 수 있다.

 

  Boyce-Codd Normal Form[BCNF]

X → Y 가 trival FD 이거나 혹은 X 가 R 의 Super key 인 릴레이션을 BCNF 를 만족한다고 한다. 이는 모든 determinant 가 key 여야 한다는 것이다.

예를 들어 위와 같이 주어진 Inst_dept 에서는 dept_name 이 key 가 아님에도 FD 가 존재하기 때문에 BCNF 를 만족하지 않는다. 그렇다면 BCNF 를 만족하도록 분해하기 위해서는 어떻게 해야할까? 이는 공식처럼, 아래의 절차를 따르면 된다.

 

1.  BCNF 를 위반하는 nontrivial FD 인 X → Y 를 찾는다.

2.  그리고 아래의 두 relation 으로 분해하면, BCNF 를 만족하도록 만들 수 있다.

     ● (X U Y)

     ● (R - (Y-X))

 

BCNF 는 너무 과하게 decompose 하는 측면이 있다. 예를 들어 AB → C, C→B  와 같은 FDs 가 있을 때, BCNF 로 만들면 (A,C), (B,C) 로 분해된다고 하자. 이러한 경우 원래 가지고 있던 FD 인 AB → C 는 보존되지 않는다.

     ● BCNF 와 dependency preservation 을 동시에 만족하는 것은 항상 가능하지 않다.

     ● Dependency preservation 을 만족시키고자 한다면 3NF 를 고려하는 것도 하나의 방법이다.

 

 

Third Normal Form [제 3 정규화]

  Third Normal Form 은 2NF 를 만족하는 테이블이 있을 때, determinant 외의 attribute 간 dependency 가 발생하면 안된다. dependency 가 발생하면 redundancy 가 생기기 때문에, trasient dependency 를 분해해야 한다. 이행적 함수 종속관계가 발생하면 안된다.

  예를 들어 takes_info 라는 릴레이션에는 takes_id(PK), semester, student_id, phone_num 과 같이 attribute 가 구성되어있다고 치자. 해당 릴레이션을 살펴보았더니 student_id 는 PK 가 아님에도 student_id 에 의해 Phone_num 이 결정되는 이행적 종속 관계가 있으므로, 3NF 를 만족하지 못한다. 고로 이를 분리해야 한다.

     ●  BCNF 는 Dependency 를 preserving 하지 않으며 Update 에 의한 FD violation 의 발생을 효과적으로 확인하는 것이 필요하다면 BCNF 보다 약한 정규형인 3NF 를 사용할 수 있다.

 

Goals of Normalizaton (Benefits of Normalization) 

이와 같이 정규화를 수행하는 목적을 정리하면 아래와 같다.

1. Less storage space

2. Quicker updates

3. Less data inconsistency

4. Clearer data relationships

5. Easier to add data

6. Flexibel Structure

 

Denormalization for Performance

간혹 정규화 되지 않은 스키마를 사용하는 것이 보다 좋은 성능을 보일 때가 있다. 이러한 경우, 그냥 정규화를 수행하지 않고 작업을 수행하거나 materialized view 를 사용할 수 있다.

 

 

 

---

References
●  Slides from Professor wookhee Kim (Konkuk. Univ)

●  Databasㅠ e System Concepts Seventh Edition

      - Avi Silberschatz Henry F. Korth S. Sudarshan