[DB][데이터베이스] 7-2. BCNF & 3NF & 4NF(MD)

• 1NF (First Normal Form)
• Features of Good Relational Design
• Functional Dependencies
• Decomposition Using Functional Dependencies
• BCNF (Boyce-Codd Normal Form)
• 3NF
• Multivalued Dependencies and 4NF
• Overall DB Design Process

 by Prof. Chang Hwan Lee

---

Boyce-Codd Normal Form (BNCF)

FD(Frequency Dependencies)의 집합 F에 대한 관계 R은 F+ 형식의 모든 FD에 대해 BCNF를 만족한다

a -> b

일 때,

a -> b 는 trivial 이거나(b는 a의 부분집합), a는 superkey이다

 

BCNF로 분해하기 위해서는 다음과 같이 나눈다

[Fig 1-1] BCNF 분해

[Fig 1-2] BCNF 분해

 

예를 들어, 다음과 같다

 

[Fig 1-3] example BCNF

 

이를 반복하여 다음과 같이 진행한다

 

[Fig 1-4] BCNF Decomposition Algorithm

 

이 때 Lossless Join은 만족하지만 Dependency Preserving은 보장하지 못한다

예를 들어 다음과 같다

 

[Fig 1-5] BCNF는 의존성 보존을 보장하지 못한다

 

마지막으로, BCNF의 분해 예시를 하나 더 살펴보고 넘어가자

 

class (course_id, title, dept_name, credits
  , sec_id, semester, year
  , building, room_number, capacity, time_slot_id)

course_id -> title, dept_name, credits
building, room_number -> capacity
course_id, sec_id, semester, year -> building, room_number, time_slot_id

후보 키 = {course_id, sec_id, semester, year}

1. course_id 는 수퍼 키가 아니다
   1. course (course_id, title, dept_name, credits)
   2. class-1 (course_id, sec_id, semester, year
        , building, room_number, capacity, time_slot_id)
2. {building, room_number} 는 class-1의 수퍼 키가 아니다
   1. classroom (building, room_number, capacity)
   2. section (course_id, sec_id, semester, year, building, room_number, time_slot_id)

course - classroom - section 은 BCNF 이다

 

---

3NF (Third Normal Form)

3NF는 BCNF에 비해 less normalize 하다 (polynomial time)

flexible하여 lossless-join 하고 dependency-preserving(<->BCNF) 하지만,

중복/null 값과 같은 문제점도 존재한다

 

이는

a -> b in F+

일 때,

a -> b 는 trivial 이거나(b는 a의 부분집합), a는 superkey이거나

(b-a)의 각 속성 A는 R의 후보키에 포함(<->BCNF)된다

 

예시는 다음과 같다

 

[Fig 2-1] 3NF example

 

하지만 다음과 같은 문제점이 있다

 

[Fig 2-2] Redundancy / null

 

L, K 관계의 반복이 일어나고,

L, K의 관계를 표현하기 위해 J에 null 값을 사용한다

또한, 3NF를 test 하기 위해 F+의 FD가 아닌 F의 FD만 체크하면 된다

 

- 1NF / 2NF / BCNF / 3NF

1NF는 모든 속성의 값이 원자성을 가지고,

2NF는 모든 속성이 primary key에 완전 함수 종속(Full FD)을 만족한다

 

[Fig 2-3] 1NF & 2NF

 

다음 예시를 보자

 

1)
advise-enroll (s-no, prof, dept, class-id, grade)

Primary key: {s-no, class-id}
FD: {{s-no, class-id} -> grade
  , s-no -> prof, s-no -> dept
  , prof -> dept}

--> BCNF X / 3NF X / 2NF X (partial FD이기 떄문에) / 1NF 0

2)
advise(s-no, prof, dept)

Prmiary key: {s-no}
FD: {s-no -> prof, s-no -> dept, prof -> dept}

--> BCNF X (prof를 나눠야 함) / 3NF X / 2NF O

 

---

Multivalued Dependencies and 4NF

- Multivalued Dependencies (MVD)

두 개의 독립된 애트리뷰트가 1:N 관계로 대응하는 관계로, ->-> 화살표로 종속성을 표시한다.

이는 모두 non-trivial FD가 없어, BCNF를 만족하는 상태여야 한다

 

[Fig 3-1] MVD example

 

MVD 에는 다음과 같은 성질이 있다

 

• (Y, Z, W) Y ->-> W 이면, Y ->-> Z 이다
• Y -> Z 이면, Y ->-> Z 이다

 

이를 두 Relation (trivial MVD) 으로 나누는 것이 4NF 이다

 

- 4NF (Forth Normal Form)

4NF는 a ->-> b 가 trivial (b가 a의 부분집합 or a와 b의 합집합이 R) 이거나, 

a가 schema R의 수퍼 키 이거나

non-trivial MVD가 없어야 한다

 

분해 알고리즘은 다음과 같다

 

[Fig 3-2] 4NF 분해 알고리즘

 

마지막으로 예시를 살펴보자

 

[Fig 3-3] 4NF Example

 

F의 세 조건 모두 4NF를 만족하지 않기 때문에 3번 분해를 진행한다

 

1. (A, B), (A, C, G, H, I)
   1. A ->-> B
2. (A, B), (C, G, H), (A, C, G, I)
   1. B ->-> HI
3. (A, B), (A, I), (A, C, G)
   1. CG ->-> H

 

---

Overall DB Design Process

[Fig 4] 정규화 단계

 

이 외에도 어렵고 잘 안 쓰이는 Join Dependencies의 Project-Join Normal Form (PJNF; 5NF) 도 있고,

이는 domian-key normal form에 따른다

 

하지만, 현실에서는 non-key 속성의 FD가 있을 수 있고, 대부분의 relationship은 binary 관계이다

 

또한, 떄때로는 정규화를 안 하는 것이 더 좋을 때도 있다

select, update 찾는 것이 훨씬 빠르고, 저장 공간이나 coding work에 장점이 있다

하지만 역시 중복 등의 문제도 있다

 

Model Temporal Data 시간