[DB] Chap. 14 Basics of Functional Dependencies and Normalization for Relational Databases

11/2

 

Relational Databases의 Informal한 설계

-Relation 속성의 의미

-중복정보로 인한 update anomaly

-Null value

-과잉 튜플(Spurious Tuple): 원하지 않은 튜플

 

Functional Dependencies(FDs): X->Y이면, X가 정해지면 Y도 정해짐.

 

Normal Form Based on PK

-normalization은 중복성 제거가 목적. Update Anormality를 일어나지 않게 하기 위해.

-1NF/2NF/3NF --> FD

 

General Normal Form은 2NF, 3NF에서만 정의(다양한 후보키 candidate key에 의해)

BCNF: FD만 고려

Fourth Normal Form: multivalue dependency 고려(좀더 중복성이 제거됨)

Fifth Normal Form: FD+MD+JD(Join Dependency)

 

Informal Design Guidelines for Relation Schemas

RDB 설계: form "good" relation schemas

관계 스키마의 두가지 레벨

-User view

-Base Relation(물리적 데이터 저장) **이쪽에 초점.

 

BCNF는 3NF만족. 3NF는 2NF만족. 2NF는 1NF 만족

(보통 이 4가지를 다룸)

 

GUIDELINE 1: 테이블 설계시 relation을 잘 설명하게 배치하라.(foreign키를 떨어뜨리는 등)

 

Redundant Information의 문제

-저장공간 낭비

-갱신이상(update anomalies): 삽입/삭제/수정

 

GUIDELINE 2: Update Anomalist가 생기지 않게.

-생길경우 complexity가 상승=>개발속도 느려짐, 유지보수 어려움

 

GUIDELINE 3: NULL값을 최소로하는 테이블 구성

NULL값이 많다면 별도로 테이블을 만든다.

 

Spurious Tuple의 생성(과잉 튜플)

: T를 R과 S로 나누었는데, R과 S의 JOIN T'가 T와 같지 않으면 과잉이다.

-lossless join

 

GUIDELINE 4: lossless join condition을 만족하는 설계. 과잉튜플 안됨.

 

decomposition의 두가지 속성

-상응하는 JOIN의 non-additive or losslessness 

-FD 보존

두번째꺼는 포기하는 경우가 있으나, 첫번째 속성은 무조건 지켜져야함(cannot be sacrificed)

 

Functional Dependencies(FDs)

-관계적 설계의 "goodness"를 측정하는 formal한 지정

-key는 relation들의 normal form을 정의하는데에 사용됨.

-의미에서의 제약과 데이터 속성의 상호관계

 

X의 값에 따라 Y의 값이 유일하게 고정되면 속성의 집합 X는 속성의 집합 Y에 대해서 functionally determine이다.

-만약 X에서 같은 값을 가지는 두개의 튜플이 있으면 이들은 Y에서도 같은 값을 가짐.

-역은 X

-FDs는 실제세계 제약조건

 

Normal Forms Based on Primary Keys

Normalization: decomposition을 "bad" relation에 실행하여 더 작은 relation으로 나누는 것.

 

FD기반과 primary key들은

1) 낭비 최소화    2) anomalies 감소

 

Normal Form: 관계 스키마가 특정한 정상 형태인지를 인증하기 위해 관계의 key와 FD를 사용하는 조건

 

1NF: single atomic values

2NF, 3NF, BCNF: 관계 스키마의 key와 FDs에 기반

4NF: key와 multi-valued dependency에 기반(MVDs)

5NF: key와 join dependency(JDs)기반

 

높은 질과 바람직한 성질을 지닌 설계.

최고의 normal form을 위해 normalize할 필요는 없음.

 

Denormalization: 테이블 합침중복성은 높아지지만, 성능은 좋아진다.

 

superkey: 튜플을 구분할 수 있는 속성.Key: minimal superkey. 최소집합.candidate key: key가 하나가 아닐 때, 걔들. 이중 선택되면 primary keyprime attribute: candidate key에 속한 속성들.nonprime attribute이면 prime attribute가 아니고, candidate key의 멤버가 아니다.

 

1NF

허용하지 않는 것

-composite 속성

-다중 속성

-nested relation

ER에서 table을 생성하면 대부분은 1NF에 속함.

 

Normalization 1NF

- attribute Dlocation 제거.

- key를 확장하여 tuple을 분리

- 최대 갯수가 주어지면, 그만큼 attribute를 추가한다.

nested relation은 분리해야함.

 

2NF

FDs와 PK를 사용

정의

-Prime attribute, Full functional dependency(모든 값이 가능해야함. 오직 PK에만 종속)

모든 non-prime attribute가 PK에 fully functionally dependent해야함.

 

3NF

Transitive functional dependency: X->Y, Y->Z이면 X->Z

2NF를 만족하고, non-prime attributeA가 PK에 Transitively dependent하지 않아야한다.

 

General Definitions of Second and Third Normal Forms

이전엔 PK만 고려했으나, candidate key로 확장

복수의 candidate key에 대한 좀더 일반화한 정의.

candidate key에 속한 속성을 prime attribute라 하고 그렇지 않으면 non-prime attribute라 한다.

 

2NF의 일반화된 정의

관계 스키마 R에 대해 R 내의 모든 non-prime 속성 A가 R의 모든 key에 대해 fully functionally dependent하면 2NF

 

3NF의 일반화된 정의

관계 스키마 R은 FD X->A가 R에서 성립할 때(hold), (1) X가 R의 슈퍼키이거나 (2) A가 R의 prime attribute이면 3NF이다.

 

1)조건을 잘 보면

a)prime attribute의 non-prime attribute를 functionally determines함.(2NF)

b)non-prime attribute는 functionally determine한다 non-prime attribute를!(3NF violation. transitive dependency)

 

b)까지 분해해버리면 BCNF가 된다.

 

Boyce-Codd Normal Form(BCNF)

중복성을 제거하자.

3NF가FD: X->A에 대해  X가 superkey 이거나 A가 Prime-attribute인데
BCNF는 뒤의 조건이 없어짐.

lossless join-> NJB(non-additive join test for binary decompositions)

R-> R1, R2

FD ((R1 OR R2) -> (R1- R2)) is in F+ or

FD ((R1 OR R2)->(R2-R1)) is in F+

 

Multivalued Dependency and Fourth Normal Form

multivalued dependency(MVD) X->>Y

: X와 Y가 R의 부분집합인 relation R에서, 다음 제약조건을 R의 어떤 relation state r에서 만족한다.

-t1 t2가 r에서 t1[X] = t2[X]로 존재하고 t3와 t4가 r에서 다음 조건으로 존재하며, Z=R-(X U Y)인 Z에 대해

- t3[X] = t4[X] = t1[X]=t2[X]

- t3[Y] =t1[Y] 그리고 t4[Y] =t2[Y]

- t3[Z]=t2[Z] 그리고 t4[Z] = t1[Z]

X->>Y가 지켜지면 X multidetermines Y라고 한다.

-X->>Y가 R에서 지켜질 때, X->>Z도 마찬가지이며, X->>Y가 X->>Z를 의미한다.

그리고 이걸 X->>Y|Z로 나타낸다.

 

Y가 X의 부분집합이거나, X U Y = R일 때, MVD X->>Y in R은 trivial MVD라고 부른다.

 

Fourth Normal Form

모든 nontrivial multivalued dependency X->>Y in F+에 대해 X가 R의 superkey일 때, 의존의 집합 F에 대해 관계 스키마 R은 4NF이다.

**F+는 모든 의존관계의 (complete) 집합-F를 만족하는 R의 모든 relation state r

이것은 closure of F라고 한다.(F에 대해 닫힘/닫혀있음)

모든 F에 대해 추론할 수 있는 SET

 

Join Dependencies and Fifth Normal Form

Join Dependency(JD)
: JD(R1,R2...Rn)으로 나타내며, 관계 스키마 R에서 R의 상태 r에 대해 다음 제약조건을 만족

-제약 상태-R의 모든 legal state r이 non-additive join decompostion을 R1,R2...Rn에서 가짐.

==모든 r들이 pi_R1(r),pi_R2(r)...pi_Rn(r) = r

MVD는 JD에서 n이 2인 케이스

trivial JD-JD(R1,R2...Rn)의 한 관계 스키마 Ri가 R과 같음.

 

Fifth Normal Form

: functional/multivalued/join dependencies 집합 F에 대해 관계 스키마 R은 5NF이다.

만약 F+ 내의 모든 nontrivial join dependency JD(R1,R2...Rn)에서 모든 Ri가 R의 superkey일 때.