r의 임의의 두 튜플 t1과 t2가 a에서 동일한 값을 가지면 b에서도 동일한 값을 가져야 한다.
K is a superkey for R iif K -> R
K is a candidate key for R iif
K -> R
for no a ⊂ K, a -> R
a -> b is trivial if b ⊆ a
Lossy Decomposition
릴레이션을 분해할 때 정보의 손실이 발생
Lossless-join Decomposition
다음과 같을 때 R의 R1과 R2로의 decomposition이 lossless join하다.
R1 ∩ R2 -> R1 or
R1 ∩ R2 -> R2
Normal Forms
First Normal Form
Domain is atomic : elements are considered to be indivisible units
non-atomic domains: multi-valued attributes (set of names), composite attributes
A relation schema R is in first normal form : R의 모든 속성의 도메인이 원자값일 때
non-atomic values complicate storage ans encourage redundant storage of data
Closure of a Set of Functional Dependencies
함수적 종속적 집합 F가 주어졌을 때 논리적으로 F가 의미하는 다른 함수적 종속성들이 존재
ex. if A->B and B->C, then A->C
F가 논리적으로 의미하는 모든 함수적 종속성 집합을 F의 closure라고 한다.
the closure of F를 F+라고 한다.
F+ is a superset of F
Armstrong's Axioms를 적용해 모든 F+를 찾을 수 있다.
if b ⊆ a, then a -> b (reflexity)
if a->b, then ra -> rb (augmentation)
if a->b and b->r, then a-> (transitivity)
이러한 rules는
sound (generate only functional dependencies that actually hold) and
complete (generate all functional dependencies that hold)
To compute the closure of a set of functional dependencies F:
F+ = F
repeat
for each functional dependency f in F+
apply reflexivity and augmentation rules on f
add the resulting functional dependencies to F+
for each pair of functional dependencies f1 and f2 in F+
if f1 and f2 can be combined using transitivity
then add the resulting functional dependency to F+
until F+ does not change any further
예시
Second Normal Form
제1정규화된 스키마에 완전 함수 종속을 만족하도록 분해
기본키의 부분 집합이 결정자가 되어서는 안된다.
Third Normal Form
제2정규화된 스키마에 이행적 종속을 없애도록 분해
a -> b, b -> c 로 a -> c가 성립되는 경우 a -> b, b-> c로 분해한다.
Boyce-Codd Normal Form
함수적 종속성의 집합 F의 측면에서 a relation schema R is in BCNF:
F+에 속하는 모든 함수적 종속성이 다음을 만족해야 한다.
a -> b where a ⊆ R and b ⊆ R, at least one of the following holds:
a -> b is trivial (b ⊆ a)
a is a superkey for R
Decomposing a Schema into BCNF
A schema R이 있고 non-trivial한 종속성 a -> b가 BCNF 위반을 초래할 때 다음과 같이 분해한다.
(a ∪ b), (R - (b - a))
ER Model and Normalization
E-R diagram을 잘 설계하여 엔티티를 알맞게 식별하면 정규화가 필요없는 테이블을 만들 수 있다.
그러나 실제 설계에서는 키가 아닌 속성에서 다른 속성으로의 함수적 종속성이 존재할 수 있다.
