Formula Sheets: Database Design (Integrity Constraints, Normalization) | Database Management System (DBMS) - Computer Science Engineering (CSE) PDF Download

 Page 1


F unctional Dep endencies and Normalization
F unctional Dep endencies
Definition and Notation
• F unctional Dep endency: X ? Y , where X,Y are sets of attributes; if t
1
[X] = t
2
[X] , then t
1
[Y ] =
t
2
[Y ] .
• T rivial FD: X ?Y if Y ?X .
• Non-trivial F D: X ?Y if Y ??X .
Closure of A ttributes (X
+
)
• Compute X
+
: Set of attributes functionally determined b y X under a set of FDs F .
• Algorithm: I nitialize X
+
=X , iterativ ely add Y to X
+
if Z ?Y ?F and Z ?X
+
.
• Usage: C hec k if X ?Y holds (Y ?X
+
).
Canonical Co v er (F
c
)
• Prop ertie s: Eac h FD has single attribute on righ t, no redundan t FDs or attributes.
• Steps:
– Decomp ose FDs to single attribute: X ?Y
1
Y
2
?{X ?Y
1
,X ?Y
2
} .
– Remo v e redundan t attributes using closure.
– Remo v e redundan t FDs.
Equiv alence of F D Sets
• T w o sets F and G are equiv alen t if F
+
=G
+
.
• Chec k: F or eac h FD in F , v erify it holds in G
+
and vice v ersa.
Keys
Sup er Key
• Set of attributes K where K
+
=R (all attributes of relation R ).
• Num b er of sup e r k eys: 2
|R|-|K|
, where K is minimal k ey .
Candidate Key
• Minimal sup er k ey: No prop er subset is a sup er k ey .
Primary Ke y
• Chosen candida te k ey to uniquely iden tify tuples.
Normalization
First Norm al F orm (1NF)
• All attributes are a tomic (no m ulti-v alued or comp osite attributes).
Second Normal F orm (2NF)
• In 1NF and no partial dep endency: Non-prime attribute fully dep enden t on candidate k ey .
• P artial Dep endency: X ?Y , whe re X is prop er subset of candidate k ey , Y is non-prime.
Third Normal F o rm (3NF)
• In 2NF and no transitiv e dep endency: Non-prime attribute Y not determined b y another non-prime
attribute.
• T ransitiv e Dep endenc y: X ?Y , Y ?Z , where X is not a sup er k ey , Y,Z are non-pr ime.
1
Page 2


F unctional Dep endencies and Normalization
F unctional Dep endencies
Definition and Notation
• F unctional Dep endency: X ? Y , where X,Y are sets of attributes; if t
1
[X] = t
2
[X] , then t
1
[Y ] =
t
2
[Y ] .
• T rivial FD: X ?Y if Y ?X .
• Non-trivial F D: X ?Y if Y ??X .
Closure of A ttributes (X
+
)
• Compute X
+
: Set of attributes functionally determined b y X under a set of FDs F .
• Algorithm: I nitialize X
+
=X , iterativ ely add Y to X
+
if Z ?Y ?F and Z ?X
+
.
• Usage: C hec k if X ?Y holds (Y ?X
+
).
Canonical Co v er (F
c
)
• Prop ertie s: Eac h FD has single attribute on righ t, no redundan t FDs or attributes.
• Steps:
– Decomp ose FDs to single attribute: X ?Y
1
Y
2
?{X ?Y
1
,X ?Y
2
} .
– Remo v e redundan t attributes using closure.
– Remo v e redundan t FDs.
Equiv alence of F D Sets
• T w o sets F and G are equiv alen t if F
+
=G
+
.
• Chec k: F or eac h FD in F , v erify it holds in G
+
and vice v ersa.
Keys
Sup er Key
• Set of attributes K where K
+
=R (all attributes of relation R ).
• Num b er of sup e r k eys: 2
|R|-|K|
, where K is minimal k ey .
Candidate Key
• Minimal sup er k ey: No prop er subset is a sup er k ey .
Primary Ke y
• Chosen candida te k ey to uniquely iden tify tuples.
Normalization
First Norm al F orm (1NF)
• All attributes are a tomic (no m ulti-v alued or comp osite attributes).
Second Normal F orm (2NF)
• In 1NF and no partial dep endency: Non-prime attribute fully dep enden t on candidate k ey .
• P artial Dep endency: X ?Y , whe re X is prop er subset of candidate k ey , Y is non-prime.
Third Normal F o rm (3NF)
• In 2NF and no transitiv e dep endency: Non-prime attribute Y not determined b y another non-prime
attribute.
• T ransitiv e Dep endenc y: X ?Y , Y ?Z , where X is not a sup er k ey , Y,Z are non-pr ime.
1
Bo yce-Co dd Normal F orm (BCNF)
• F or e v ery FD X ?Y , X is a sup er k ey .
F ourth Normal F orm (4NF)
• In BCNF and no non-trivial m ulti-v alued dep endency (MVD): X?Y implies X is a sup er k ey .
• MVD: F or tuples t
1
,t
2
,t
3
, if t
1
[X] = t
2
[X] = t
3
[X] , then exists t
4
with t
4
[X] = t
1
[X] , t
4
[Y ] = t
1
[Y ] ,
t
4
[R- (X?Y )] =t
2
[R- (X?Y )] .
Fifth Norm al F orm (5NF)
• In 4NF and no join dep endency: Relation cannot b e decomp osed in to smaller relations without loss
of information unless decomp osition is trivial.
• Join Dep endenc y: R =??{R
1
,R
2
,...,R
n
} for pro jections R
i
.
Lossless Decomp osition
• F or decomp os ition R
1
,R
2
of R : R
1
??R
2
=R .
• Conditi on: R
1
nR
2
?R
1
or R
1
nR
2
?R
2
in F
+
.
Dep endency Preserv ation
• Decomp os ition R
1
,R
2
preserv es F if (F
R1
?F
R2
)
+
=F
+
.
2