Discussion Session on
Normal Forms
Amin Javari
Q1
Consider the relation R(A, B, C, D, E) with the functional dependencies
FD={A → D, B → E, DE → C}. Let S(A, B, C) be a decomposed relation of
R. What are the FDs of S?
Q1 Solution
{A}+ = AD, but D is not in S, so A → D does not hold
{B}+ = BE, but E is not in S, so B → E does not hold
{C}+ = C, no new FD
{AB}+ = ABCDE, so AB → C holds for S ( since DE are not in S)
{BC}+ = BCE, no new FD
{AC}+ = ACD, no new FD
{ABC}+ = ABCDE, no new FD
AB → C is the only nontrivial FD for S
Q2
Consider the relation R(A,B,C,D,E,F) and the functional dependencies F
= { A → BC, C → EF, B → D , D → C}
Are the following decompositions lossless?
a) (ABC)(AEDF)
b) (ABCE)(AD)
c) (BC)(ABDEF)
Q2 Solution
Let’s assume we decompose R into R1 and R2.
The decomposition is lossless if:
1) The union of the attributes of R1 and R2 is equal to the
attributes of R.
2) The intersection of the attributes of R1 and R2 is not empty.
3) The intersection of the attributes of R1 and R2 is a key for at
least one of the relations R1/R2.
Q2 Solution
(a) Lossless decomposition because is the key for both ABC
and AEDF.
(b) Lossy because does not cover F
(c) Lossless because is the key for BC.
Q3
Consider the relation R=(A, B, C) and functional dependency FD={A –>
B, B –> C}.
Is the decomposition of R into R1( A, C) and R2(B, C) dependency
preserving?
Q3 Solution
• Find the closures of F1 and F2
• F1={A–> A, C–> C, A–> C, AC–> AC}
• F2= {B–> B, C–> C, B–> C, BC–> BC}
• is F’:= {B–>C, A–>C} which does not cover A->B
• The decomposition is not a dependency preserving decomposition.
Q4
Consider the relation R (A, B, C, D ) and functional dependency {AB –>
C, C –> D, D –> A}.
Is the decomposition of R into R1( A, B, C) and R2(C, D) dependency
preserving?
Q4 Solution
• Find the closures of F1 and F2
•
•
• does not cover D->A
• The decomposition is not a dependency preserving decomposition.
Q5
• Let R=(A, B, C, D) a relation and F ={AB -> C, C-> D, D -> A} a set of
dependencies for this relation.
• Decompose the relation into BCNF if necessary.
• Is R in 3NF, why?
Q5 Solution
(a)
• Three candidate keys are {AB}, {BC}, and {BD} .
• C->D and D->A violate BCNF.
• Decompose R based on C->D into (C,D) with F1={C-> D} and (A,B,C)
with F2={AB -> C, C->A}
• C->A violates BCNF
• Decompose (A,B,C) based on C->A into (C,A) with F3= {C-> A} and
(C,B) with F4={}
Q5 Solution
(b)
• Three candidate keys are {AB}, {BC}, and {BD}.
• A, D and C are prime attributes. Hence, R is in 3NF.
Q6
Consider the relation R = (A, B, C, D) with the FDs F = {AB →C, AB →D,
C →A, D →B}.
(a) Is R in 3NF, why? If it is not, decompose it into 3NF.
(b) Is R in BCNF, why? If it is not, decompose it into BCNF
Q6 Solution
(a)
• Find all the Candidate Keys: AB, BC, CD, AD.
• Check all FDs in F for 3NF condition.
• All of the attributes are prime attributes.
Q6 Solution
(b)
No. Because for C →A, C is not a superkey. Similar for D → B
Decompose it into R1 = {C, A} and {C,B,D}.
{C,B,D} is not in BCNF because D → B violates BCNF.
Decompose {C,B,D} into {C,D} and {D,B}
R1 = {C, D}, R2 = {A, C}, R3 = {B, D}
Q7
• Consider the relation R(A,B,C,D,E) with the functional dependencies
FD={A ->B, AB ->D, BD -> EC, A->E, B->E}
• Compute the minimal cover of FD.
• Decompose the relation into a collection of relations that are in 3NF.
Q7 solution
• Step 1: RHS of each functional dependency should have a single
attribute:
• A->B
• A->E
• B->E
• AB->D
• BD->E
• BD->C
Q7 solution
• Step2: Remove unnecessary attributes from LHS: B can be removed from
AB->D, D can be removed from BD->E
• A->B
• B->E
• A->E
• A->D
• B->E
• BD->C
Q7 solution
• Step 3: Remove unnecessary dependencies
• A->E can be removed as it can be entailed by A->B and B->E
• A->B
• B->E
• A->D
• BD->C
Q7 solution
(b)
Step 1: Create a relation for each FD in the minimal equivalent set.
(A,B), (B,E), (A,D), (B,D,C)
Step 2: If the key for the original relation does not occur in any of the
obtained relations, create a relation for the key.
A is the key for R.