🍙

Normalization for Relational DB - 3


General definitions of 2NF & 3NF

이전 글에서는 기본키에 대해서 일반형을 정의해봤다. 이번에는 일반화 해보자.

2NF의 일반적 정의

Relation RR모든 nonprime attribute AARR의 어느 키(기본키, 후보키)에 대해 'partially functional dependent'하지 않다면, RR은 2NF를 만족한다.

3NF의 일반적 정의

Nontrivial FD XAX\rarr A에서

  1. XX슈퍼 키 혹은,
  2. AAprime attribute

이면 relation은 3NF를 만족한다.

image

1번 조건은 두가지 위반 사항을 잡을 수 있다.

  • prime attribute가 nonprime 속성을 functionally 결정하는 경우: partial dependency를 잡아 2NF 위반을 잡을 수 있다.
  • nonprime attribute가 nonprime 속성을 functionally 결정하는 경우: transitive dependency막아 3NF 위반을 잡을 수 있다.

3NF를 다른 방식으로도 정의내릴 수 있다.

모든 nonprime attribute가 a)모든 키에 대해 FFD이고 b)모든 키에 대해 'non-transitively dependent'하다면 relation은 3NF이다.

여기서 b)는 3NF에서는 허용되지만 'Boyce-Codd Normal Form'에서는 허용되지 않는다. 즉, candidate key에 의해 발생하는 transitive property도 없앤다.

Boyce-Codd Normal Form

Relation RR모든 FD XAX\rarr A에서, XX가 슈퍼키이면 RR은 BCNF를 만족한다.

BCNF가 3NF보다 강력하기 때문에 3NF이면서 BCNF인 relation은 존재하지 않는다.

BCNF는 decomposition으로 달성할 수 있다. 분해했을 때 어떤 FD를 잃을 수도 있는데, 이것은 감내해야 하는 부분이다.

어떻게 분해해야할까? decomposition의 두 가지 특성중 하나를 보존하는 분해를 선택하면 된다.

  • non-additive(lossless) join property
  • functional dependency preservation property

정규화 과정에서 분해할 것을 고를 때 'Nonadditive Join Test for Binary Decomposition(NJB)'을 사용할 수 있다.

NJB(Nonadditive Join Test for Binary Decomposition)

RR의 decomposition D={R1,R2}D=\{R1, R2\}의 FD 집합 FF에 대해서,

  • FD ((R1R2))(R1R2))((R1\cap R2 ))\rarr(R1-R2))F+F^+에 있거나
  • ((R1R2))(R2R1))((R1\cap R2 ))\rarr(R2-R1))F+F^+에 있다면,

'non-additive join property'를 만족한다. (F+F^+FF가 함축하는 모든 FD를 포함)

아래 예시를 통해 한 번 해보자. IMG_F46EDE6DFD45-1

  • Case 1: R1(Student, Instructor) and R2(Student, Course)
    Student → Instructor 와 Student → Course, 둘 다 만족하지 못한다.

  • Case 2: R1(Course, Instructor) and R2(Course, Student)
    Course → Instructor 와 Course → Student, 둘 다 만족하지 못한다.

  • Case 3: R1(Instructor, Course) and R2(Instructor, Student)
    Instructor → Course 가 FD2와 같기 때문에 F+F^+에 속한다. NJB를 만족하므로 분해할 때 case 3을 선택하면 된다.

BCNF Decomposition 알고리즘

RR이 BCNF에 속하지 않은 relation이고 XRX\sube R일 때, XAX\rarr A가 BCNF 위반을 발생시키는 FD라고 하자.

이때 RR은 두 가지 relation으로 분해될 수 있다.

  • RAR-A
  • XA(=XA)XA(=X\cup A)

두 가지 경우 중 BCNF에 속하지 않는 것이 있다면, 그 경우에 대해 알고리즘을 반복한다. 둘 다 BCNF에 속하게 되면 알고리즘을 종료한다.

정리

Normal FormDescription
1NF도메인의 원자성
2NF부분 함수적 종속 제거
3NF이행 함수적 종속 제거
BCNF후보키가 아닌 결정자 제거