The Hong Kong

University of Science
and Technology

COMP231 Tutorial 5

Functional Dependencies, 3NF

 Review: Key

• Superkey
KR

• Candidate Key
KR
no K’  K, s.t. K’  R (minimal)

• Primary Key
The candidate key chosen to uniquely identify tuples in a relation

primary key

candidate key

superkey

HKUST 2 Database Management Systems

 Review: The Closure of FD

• For a set of functional dependencies F, we can get the closure, F+, by

applying Armstrong’s Axioms.
• Armstrong’s Axioms:
• Reflexivity
If X  Y, then X  Y
• Augmentation
If X Y, then XZ  YZ
• Transitivity
If X  Y, Y  Z, then X  Z
• Derived rules:
• Decomposition
If X  YZ, then X  Y and X  Z
• Union
If X  Y and X  Z, then X  YZ
• Pseudo-transitivity
If X  Y and WY  Z, then WX  Z

HKUST 3 Database Management Systems

 Review: The Closure of Attributes

Definition: Algorithm:
X, Y are attributes of a relation R: •X(0) := X
X  Y is in F+  Y  X+ •Repeat
X(i+1) := X(i)  Z,
where Z is the set of
attributes such that there
exists YZ in F, and Y  X(i)
•Until X(i+1) := X(i)
•Return X(i+1)

Example:
Given R = (loan_no, amount, branch_name, customer_name)
• If loan_no  amount
then loan_no+ = {loan_no, amount}
• If we also have loan_no  branch_name
then loan_no+ = {loan_no, amount, branch_name}
• If we also have loan_no  customer_name
then loan_no+ = {loan_no, amount, branch_name, customer_name}

HKUST 4 Database Management Systems

 Review: Canonical Cover of FD

Definition:

A canonical cover for F is a set of dependencies Fc such that

• F and Fc are equivalent
• Fc contains no redundancy

• Each left hand side of functional dependency in Fc is unique

HKUST 5 Database Management Systems

 Review: Normalization

• Decomposition of a relation R with the following goals

• Lossless (necessary)
Information lost?
• Dependency preservation (desirable)
(i Fi)+ = F+ ?
• Good form
1NF, 2NF, 3NF, BCNF
2NF: 3NF:
R is in 2NF if and only if R is in 3NF if and only if
for each FD: X  {A} in F+ for each FD: X  {A} in F+
Then Then
A  X (the FD is trivial), OR A  X (trivial FD), OR
X is not a proper subset of a X is a superkey for R, OR
candidate key for R, OR A is prime attribute for R
A is a prime attribute
•A primary attribute is an attribute that is part of a candidate key
HKUST 6 Database Management Systems
 Exercise 1: The Closure of Attributes
R = (A, B, C, D, E)
F = {ABC, CDE, BD, EA}

Compute A+ and B+:

A+ := {A}
:= {A, B, C} ABC and {A}  A+
:= {A, B, C, D} BD and {B}  A+
:= {A, B, C, D, E} CDE and {C, D}  A+
ends because A+ stops changing

B+ := {B}
:= {B, D} BD and {B}  B+
ends because B+ stops changing

HKUST 7 Database Management Systems

 Exercise 2: Candidate Keys
R = (A, B, C, D, E)
F = {ABC, CDE, BD, EA}
List all candidate keys of R.

• We have A+ = {A, B, C, D, E} in Exercise 1,

then AABCDE, it is a candidate key of R.
• Since EA,
then EABCDE. (transitivity)
• Since CDE,
then CDABCDE. (transitivity)
• Since BD,
then BCCD, then BCABCDE. (augmentation, transitivity)

So A, E, CD, BC are candidate keys of R.

HKUST 8 Database Management Systems

 Exercise 3: Compute Canonical Cover

R = (A, B, C, D, E)
F = {ACE, ACDB, CED, BE}
Find the canonical cover of F.

Algorithm:
Repeat
Union
X1Y1 and X1Y2 replaced with X1Y1Y2
Find an extraneous attribute

If an extraneous attribute is found in XY,

delete it from XY
Until F does not change

HKUST 9 Database Management Systems

 Exercise 3: Compute Canonical Cover (cont)

R = (A, B, C, D, E)
F = {ACE, ACDB, CED, BE}
Find the canonical cover of F.

First loop:
Union
Fc(1) = {ACE, ACDB, CED, BE}
Find an extraneous attribute
Consider ACDB:
D is extraneous because ACE and CED
Remove D in ACDB
Fc(1) = {ACE, ACB, CED, BE}

HKUST 10 Database Management Systems

 Exercise 3: Compute Canonical Cover (cont)

R = (A, B, C, D, E)
Fc(1) = {ACE, ACB, CED, BE}

Second loop:
Union
Fc(2) = {ACBE, CED, BE}
Find an extraneous attribute
Consider ACBE:
E is extraneous because BE
Remove E in ACBE
Fc(2) = {ACB, CED, BE}

HKUST 11 Database Management Systems

 Exercise 3: Compute Canonical Cover (cont)

R = (A, B, C, D, E)
Fc(2) = {ACB, CED, BE}

Third loop:
Union
Fc(3) = {ACB, CED, BE}
Find an extraneous attribute
No extraneous attributes found

Ends because Fc stops changing

Fc = {ACB, CED, BE}

HKUST 12 Database Management Systems

 Exercise 3: Compute Canonical Cover (cont)

• Different order of removing the extraneous attributes may result

in different FC
• Example:
R=(A, B, C, D)
FD = {AC, BCA, ABCD}

• In ABCD, A is extraneous or C is extraneous

• If we remove A first, we get Fc = {AC, BCAD}
• If we remove C first, we get Fc = {AC, BCA, ABD}

HKUST 13 Database Management Systems

 Exercise 4: Normal forms

• R=(A, B, C, D, E)
• FD = {ABC, CDE, BD, EA}

• Is R in 1NF?
• Yes. Relational tables are always in 1NF.
• Is R in 2NF?
• We found candidate keys: A, E, CD, BC.
ABC BC are prime attribute
CDE E is a prime attribute
BD D is a prime attribute What is 2NF?
EA A is a prime attribute For each FD: X->{A}
So R is in 2NF 1. A  X (FD is trivial)
2. X is NOT subset of candidate key
3. A is prime attribute
HKUST 14 Database Management Systems
 Exercise 4: Normal forms (cont)

• R=(A, B, C, D, E)
• FD = {ABC, CDE, BD, EA}

• Is R in 3NF?
• We found candidate keys: A, E, CD, BC.
ABC A is a candidate key
CDE CD is a candidate key
BD D is a prime attribute Different with 2NF
EA E is a candidate key
So R is in 3NF What is 3NF?
For each FD: X->{A}
1. A  X (FD is trivial)
2. X is super key
3. A is prime attribute
HKUST 15 Database Management Systems
 Exercise 4: Normal forms (cont)

• R=(A, B, C, D, E, F)
• FD = {AB, BCD, CE, BF}

• Is R in 2NF?
• Candidate key: AC.
AB A is a proper subset of candidate key
AND B is not a prime attribute
BCD BC is not a proper subset of
candidate key
CE C is a proper subset of candidate key
AND E is not a prime attribute
BF B is not a proper subset of candidate What is 2NF?
key
For each FD: X->{A}
AB or CE makes R not in 2NF
A  X (FD is trivial)
X is NOT subset of candidate key
A is prime attribute
HKUST 16 Database Management Systems
 Exercise 4: Normal forms (cont)

• R=(A, B, C, D, E, F)
• FD = {AB, BCD, CE, BF}

• Is R in 3NF?
• 3NF  2NF  1NF, R is not in 2NF, so R is not in 3NF either.
• Candidate key: AC.
AB A is not a super-key AND B is not a
prime attribute
BCD BC is not a super-key AND D is not a
prime attribute
CE C is not a super-key AND E is not a
prime attribute What is 3NF?
BF B is not a super-key AND F is not a For each FD: X->{A}
prime attribute
1. A  X (FD is trivial)
Either one of the FD makes R not in 3NF 2. X is super key
3. A is prime attribute
HKUST 17 Database Management Systems
 Exercise 5: Decomposition

R = (A, B, C, D, E, F, G, H)
F = {ACG, DEG, BCD, CGBD, ACDB, CEAG}

• A decomposition of R: R

• Table1: (A, B, C, D)
• Table2: (D, E, G) Table1Table3 Table2

• Table3: (A, C, D, F, H)
Table1 Table3

• Is it lossless?
Yes
A decomposition of R into R1 and R2 is lossless if and only if the common
attributes of R1 and R2 is a candidate key for R1 or R2
• (Table1  Table3)  Table2 = D (candidate key of Table2)
• Table1  Table3 = ACD (candidate key of Table1)

HKUST 18 Database Management Systems

 Exercise 5: Decomposition (cont)

R = (A, B, C, D, E, F, G, H)
F = {ACG, DEG, BCD, CGBD, ACDB, CEAG}

• A decomposition of R:
• Table1: (A, B, C, D)
• Table2: (D, E, G)
• Table3: (A, C, D, F, H)
• Is it dependency preserving?
• No (CGBD is lost)

HKUST 19 Database Management Systems

 Exercise 6: 3NF

R = (A, B, C, D, E, F, G, H)
F = {ACG, DEG, BCD, CGBD, ACDB, CEAG}
Decompose R into 3NF

• Algorithm:
Compute Fc of F
S := 
For each FD XY in Fc:
S := S  (X,Y)
If no scheme contains a candidate key for R:
Choose any candidate key CN
S := S  table with attributes in CN

HKUST 20 Database Management Systems

 Exercise 6: 3NF (cont)

R = (A, B, C, D, E, F, G, H)
F = {ACG, DEG, BCD, CGBD, ACDB, CEAG}

• In Exercise 3, we get
Fc = {ACB, DEG, BCD, CGD, CEA}
• For each FD, we generate a table:
Table1: (A, B, C)
Table2: (D, E, G)
Table3: (B, C, D)
Table4: (C, D, G)
Table5: (A, C, E)

HKUST 21 Database Management Systems

 Exercise 6: 3NF (cont)

R = (A, B, C, D, E, F, G, H)
Fc = {ACB, DEG, BCD, CGD, CEA}

• Any table in S contains a candidate key for R?

No
• ACFH is a candidate key:
Generate Table6: (A, C, F, H)
• So a possible 3NF decomposition of R is:
(A, B, C), (D, E, G), (B, C, D), (C, D, G), (A, C, E), (A, C, F, H)
• Lossless?
Yes R
ACFH ACE DGE
• Dependency preserving?
ACBDEG CEBDG BCDG
Yes
CDG BCD

HKUST 22 Database Management Systems