[DB] 함수 종속성과 정규화(1NF, 2NF, 3NF, BCNF, 4NF, 5NF)

함수 종속성
normal form은 함수 종속성을 토대로 만들어진다.

y = f(x)처럼 x에 대응되는 y값은 오직 하나인 것 처럼 relation에서 각 attribute간 함수의 성질을 만족하는 것이다.
x functionally determines y

X → Y iff, in every possible legal value of R, each X-value has associated with precisely one Y-value

X가 R의 candidate key이면 R의 모든 attribute들은 X에 대한 FD가 성립한다.

trival 종속성과 nontrivial 종속성은 2NF, 3NF을 구분하는데 중요하다.
X -> Y가 성립할 때, Y가 X의 subset이면 trivial FD라고 한다.

정규화
정규화란, 테이블의 decomposition
데이터의 중복을 제거하고, 데이터 종속이 논리적으로 표현 되도록하는 데이터 구조의 재구성 과정
Insertion Anomaly(dirty data), Modification Anomaly(data inconsistency), Deletion Anomaly(lost data)를 극복

unnormalized relations : relation의 every row-and-column에 repeating group을 갖는 경우
normalized relation : relation이 atomic한 값만 갖는 경우

정규화 단계
각 단계는 이전 단계들의 조건을 모두 만족한다

1NF(First Normal Form)
relation의 모든 attribute가 atomic하며 scalar 값이다.

모든 attribute의 값은 더 이상 나눠질 수 없어야하고 reduncancy를 제거하거나 최소화해야한다.

insert, delete, update anomaly가 발생

 

2NF(Second Normal Form)
모든 nonkey attribute가 primary key에 대하여 irreducibly dependent 해야 한다.

irreducibly dependent란,
X → Y에서 X의 어떠한 subset에서도 FD가 성립하지 않는 것 (no partial FD)
{x0, x1} → y에서, x0 → y 또는 x1 → y 성립x
subset element에 성립하면 쪼개야한다

2NF는 key가 composite key가 아니라면 2NF는 자동적으로 만족된다?
{} →  y일 때, 성립x 근데 y의 값이 절대 변하지 않는다면 denormalization 가능

insert, delete, update anomaly가 발생

3NF(Third Normal Form)
모든 nonkey attribute는 nontransitive dependent 해야 한다.

transitive dependent란, X → Y, Y → Z가 성립할 때 X → Z가 성립하는 것
이때, Y가 nonkey attribute라면 FD는 성립하지만 insert, delete, update anomaly의 원인이 된다.

Dependency Preservation
1) 원래 relation R 의 모든 FD는 R1과 R2의 FD들에 대한 logical consequence
2) R1과 R2의 공통 attribute는 R1 또는 R2의 어느 한쪽에서 candidate key이어야 한다
3) join 했을 때 원래 R이 나와야한다

BCNF(Boyce-Codd Normal Form)
모든 FD의 determinant는 candidate key여야 한다.
모든 유효한 non-trival FD X → Y는 X가 primary key여야 한다.

nonkey attribute가 determinant라면 redundant하기 때문에 쪼개야한다.

4NF(Fourth Normal Form)
4NF를 정의하기 위해선 MVD(Multivalued Dependency)를 사용한다.

MVD란,
FD를 generalization한 것이다.
FD에서는 X에 의해 Y의 값이 결정되었다면 MVD에서는 X에 의해 다수의 Y 값이 결정된다.

아래에 FD가 없고 BCNF를 만족하는 테이블 ctx(course, teacher, text)가 있다.

 

course	teacher	describtion
Physics	Prof. Green	Basic Mechanics
Physics	Prof. Green	Principles of Optics
Physics	Prof. Brown	Basic Mechanics
Physics	Prof. Brown	Principles of Optics

 

이때, 새로운 Physics의 새로운 선생님들 추가하려면 2개의 튜플을 추가해야하는데

이러한 redundancy는 insert anormaly를 발생시킨다.

Physics  → {Basic Mechanics, Principles of Optics} 와 같이 X에 대응되는 Y 값이 여러개이다.

이러한 종속성을 X → → Y로 표현한다. 

 

R{A,B,C}에서 A → →B와 A → →C가 성립하면, A → →B | C로 표현한다.

A → →B | C가 만족할 때 {A,B}와 {B,C}의 join 결과는 R와 같다.

 

MVD는 두개로 분류된다.

R에서 MVD X → →Y일 때,

Y가 X의 subset이거나 X ∪ Y = R이면, trival MVD 아니면 nontrival MVD이다.

 

R에서 성립하는 모든 MVD: X → →Y가

Y ⊆ X or XY = R이거나 X가 Y를 제외한 나머지 attributes에 대해 super key라면

4NF를 만족한다고 한다.

 

ctx를 4NF에 만족하게 쪼개면, cd(course, describtion), ct(course, teacher)로 나타낼 수 있다.

 

course	describtion
Physics	Basic Mechanics
Physics	Principles of Optics

 

course	teacher
Physics	Prof. Green
Physics	Prof. Brown

 

 

5NF(Projection-join Normal Form)

5NF를 정의하기 위해선 JD(join dependency)를 사용한다.

 

JD란,

relarion R을 쪼갠 테이블들을 join하면 원래의 R과 같아야한다는 것을 말한다.

R(A, B, C, D)이 projection AB, BC, ... DA의 join과 같으면 JD * ( AB, BC, ... DA)를 만족한다고 한다.

 

5NF는 R에서 모든 join dependency가 R의 candidate key로 projection 된다면 쪼갠다.

 

projection이란,

R의 튜플에서 원하는 attribute 집합으로 새로운 R2를 만드는 것 (부분집합)

 

R을 쪼갤 때 R의 candidate key를 포함해서 쪼개야 한다는 말이다.

 

아래의 sn(sno, sname, status, city)에서 candidate key는 sno, sname이고, 

sno  → sname, 

sname  → sno,

sno → city,

sno → status가 성립한다.

 

sno	sname	city	status
s1	name1	city1	90
s2	name2	city1	100
s3	name3	city2	100

 

sn은 JD*({sno, sname}, {sno, city, status})를 만족하기 때문에 5NF이다.

이처럼 candidate key로 projection한 것은 nonloss-decompose가 가능하다.

JD*({sname, status, city}, {sname, sno})도 만족하긴한다.

sn은 atomic은 아니지만 5NF이다.

그러나 5NF를 만족한다고 해서 항상 decompose해야 하는 것은 아니다.

 

sno	sname
s1	name1
s2	name2
s3	name3

sno	city	status
s1	city1	90
s2	city1	100
s3	city2	100