Normalization Questions and Answers
Database Systems,CSCI4380-01
Sibel Adalı
October28,2002
Question1Suppose you are given a relation R=(A,B,C,D,E)with the following functional dependencies:{CE→D,D→B,C→A}.
a.Find all candidate keys.
b.Identify the best normal form that R satisfies(1NF,2NF,3NF,or BCNF).
c.If the relation is not in BCNF,decompose it until it becomes BCNF.At each step,identify a new relation,decompose and re-compute the keys and the normal forms they satisfy.
Answer.
a.The only key is{C,E}
b.The relation is in1NF
c.Decompose into R1=(A,C)and R2=(B,C,D,E).R1is in BCNF,R2is in2NF.Decompose R2 into,R21=(C,D,E)and R22=(B,D).Both relations are in BCNF.
Question2Suppose you are given a relation R=(A,B,C,D,E)with the following functional de-pendencies:{BC→ADE,D→B}.
a.Find all candidate keys.
b.Identify the best normal form that R satisfies(1NF,2NF,3NF,or BCNF).
c.If the relation is not in BCNF,decompose it until it becomes BCNF.At each step,identify a new relation,decompose and re-compute the keys and the normal forms they satisfy.
Answer.
a.The keys are{B,C}and{C,D}
b.The relation is in3NF
c.It cannot be put into BCNF,even if I remove D and put into a relation of the form(B,C,D)(I need C for the functional dependency),the resulting relation would not be in BCNF.
Question3Suppose you are given a relation R=(A,B,C,D,E)with the following functional de-pendencies:BD→E,A→C.
a.Show that the decomposition into R1=(A,B,C)and R2=(D,E)is lossy.You can show using any method.My suggestion is to show how spurious tuples result from this decomposition with respect to the table below:
A B C D E
12345
18344
1
b.Find a single dependency from a single attribute X to another attribute Y such that when you add the dependency X→Y to the above dependencies,the decomposition in part a is no longer lossy.
Answer.
a.If we were to decompose the relations into:
A B C 123 183D E 45 44
and then join the two(in this case with a cartesian product),we would get:
A B C D E
12345
18345
12344
18344
Tuples2and3are not in the original relation.Hence,this decomposition is lossy.
b.This decomposition cannot be made lossless.The problem is there is no longer a way to make sure
BD→E holds across two relations since they do not share any attributes.However,a lossy decomposition of the form(A,B,C),(C,D,E)can be made lossless by adding an FD B→C. Question4You are given the following set of functional dependencies for a relation R(A,B,C,D,E,F), F={AB→C,DC→AE,E→F}.
a.What are the keys of this relation?
b.Is this relation in BCNF?If not,explain why by showing one violation.
c.Is the decomposition(A,B,C,D)(B,C,D,E,F)a dependency preserving decomposition?If not, explain briefly.
Answer.
a.What are the keys of this relation?
{A,B,D}and{B,C,D}.
b.Is this relation in BCNF?If not,explain why by showing one violation.
minimal
No,all functional dependencies are actually violating this.No dependency contains a superkey on its left side.
c.Is the decomposition(A,B,C,D)(B,C,D,E,F)a dependency preserving decomposition?If not, explain briefly.
Yes,AB→C and DC→A are preserved in thefirst relation.DC→E and E→F are preserved in the second relation.
Question5You are given the below functional dependencies for relation R(A,B,C,D,E),F= {AB→C,AB→D,D→A,BC→D,BC→E}.
a.Is this relation is in BCNF?If not,show all dependencies that violate it.
b.Is this relation in3NF?If not,show all dependencies that violate it.
2
c.Is the following dependency implied by the above set of dependencies?If so,show how using the Amstrong’s Axioms given in the book(p.362-363):ABC→AE
Answer.
Keys for the relation:{A,B},{B,D},{B,C}.
a.Not in BCNF since D→A does have a superkey on the left hand side.
b.In3NF since in D→A,A is part of a key.
c.BC→E(given)
ABC→AE by the augmentation rule.
Question6You are given the table below for a relation R(A,B,C,D,E).You do not know the functional dependencies for this relation.This question is independent of Question2above.
A B C D E
’a’1221’s1’’a’
’e’2364’e2’’b’
’a’1991’b5’’c’
’b’2132’z8’’d’
Suppose this relation is decomposed into the following two tables:R1(A,B,C,D)and R2(A,C,E). Is this decomposition lossless?Explain your reasoning.
Answer.
R1
A B C D ’a’1221’s1’’e’2364’e2’’a’1991’b5’’b’2132’z8’R2
A C E
’a’1’a’
’e’4’b’
’a’1’c’
’b’2’d’
R1  R2
A B C D E
’a’1221’s1’’a’
’e’2364’e2’’b’
’a’1991’b5’’c’
’b’2132’z8’’d’
’a’1221’s1’’a’
’a’1991’b5’’c’
Since the last two rows are not in the original relation,then this decomposition is lossy.
Question7You are given the below set of functional dependencies for a relation R(A,B,C,D,E,F,G), F={AD→BF,CD→EGC,BD→F,E→D,F→C,D→F}.
a.Find the minimal cover for the above set of functional dependencies using the algorithm described in class.Give sufficient detail to show your reasoning,but be succinct.You do not have to list all the ca
ses you test/consider for the algorithm.Show all steps where you make changes to the above set in detail.
b.Using the functional dependencies that you computed in step a,find the keys for this relation. Is it in BCNF?Explain your reasoning.
c.Suppose we decompose the above relation into the following two relations:
R1(A,B,C,D,E)R2(A,D,F,G)
Use the functional dependencies in the minimal cover.For each relation,write down the functional dependencies that fall within that relation(you can decompose a dependency of the form AD→BF into AD→B and AD→F when computing this).
3
Using these functional dependencies,determine if this decomposition is lossless and/or dependency preserving.Explain your reasoning.
Answers.
a.
Step1.
{AD→B,AD→F,CD→E,CD→G,CD→C,BD→F,E→D,F→C,D→F}
{AD→B,CD→E,CD→G,F→C,D→F,E→D}
{AD→B,D→E,D→G,F→C,D→F,E→D}
Finally recombine
{AD→B,D→EGF,F→C,E→D}.
b.Keys:{A,D},{A,E}.Not in BCNF since the last three functional dependencies do not have a superkey on the left hand side.
c.R1(A,B,C,D,E)Dependencies:AD→B,D→E,E→D R2(A,D,F,G)Dependencies:D→GF.
Not functional dependency preserving,the dependency F→C is not preserved.
head(R1)∩head(R2)={A,D}
R1:AD→ABCDE is not true since C is not implied by A,D
R2:AD→ADF G is true since this is implied by D→GF as follows:
AD→AD inclusion rule,since D→GF,use set accumulation rule,AD→ADGF.Hence,this
is a lossless decomposition.
Question8You are given the following set F of functional dependencies for a relation R(A,B,C,D,E,F): F={ABC→D,ABD→E,CD→F,CDF→B,BF→D}.
a.Find all keys of R based on these functional dependencies.
b.Is this relation in Boyce-Codd Normal Form?Is it3NF?Explain your answers.
c.Can the set F be simplified(by removing functional dependencies or by removing attributes from the left hand side of functional dependencies)without changing the closure of F+)? Hint.Conside
r the steps of the minimal cover algorithm.Do any of them apply to this functional dependency?
Answer.
a.Keys:{A,B,C}and{A,C,D}
b.It is not in BCNF.Counterexample ABD→E and ABD is not a superkey.
It is not in3NF.Counterexample ABD→E,and ABD is not a superkey and E is not prime attribute(part of a key).
c.Let F’be obtained by replacing CDF→B with CD→B.
According to F and F’,CD+={C,D,B,F}.Hence,we can remove F from this functional dependency without changing the meaning of the system.
Question9Consider relation R(X,Y,Z).Relation R currently has three tuples:(6,4,2),(6,6, 8)and(6,4,8).Which of the following three functional dependencies can you infer do not hold
for relation R?Explain your answer.
Y→X
4
Z→Y
XY→Z
Answer.Thefirst functional dependency holds,but the rest do not hold.The second and third tuples both have8for Z but different values of Y.Thefirst and third tuples both have6and4for X and Y but different values for Z.
Question10Consider the relation R(V,W,X,Y,Z)with functional dependencies{Z→Y,Y→Z,X→Y,X→V,V W→X}.
a)List the possible keys for relation R based on the functional dependencies above.
b)Show the closure for attribute X given the functional dependencies above.
c)Suppose that relation R is decomposed into two relations,R1(V,W,X)and R2(X,Y,Z).Is this decomposition a lossless decomposition?Explain your answer.
Answer.
a.{V,W},{X,W}
b.X+={X,V,Y,Z}
c.Yes it is lossless.To be lossless the attributes in common between the two relations must functionally determine all the attributes in one of the two relations.The only attribute in common is X and it functionally determines all the attributes in R2.
Question11Given relation R(W,X,Y,Z)and set of functional dependencies F={X→W,W Z→XY,Y→W XZ}.Compute the minimal cover for F.
Answer.
Step1:X→W,W Z→X,W Z→Y,Y→W,Y→X,Y→Z
Step2:Don’t need W Z→X,since W Z→Y and Y→X
Don’t need Y→W,since Y→X and X→W
This leaves{X→W W Z→Y,Y→X,Y→Z}
Step3:Only need to consider W Z→Y.Can’t eliminate W or Z.So nothing is eliminated.
Step4:{X→W W Z→Y,Y→XZ}is the minimal cover
Question12Given relation R(W,X,Y,Z)and set of functional dependencies G={Z→W,Y→XZ,XW→Y},where G is a minimal cover:
a)Decompose R into a set of relations in Third Normal Form.
b)Is your decomposition in part a)also in Boyce Codd Normal Form?Explain your answer. Answer.
a.Possible keys:{Y},{X,Z},{W,X}
R1=(Z,W),R2=(X,Y,Z),R3=(X,Y,W)
b.Yes.In each of the three relations,the left side of the funcational dependencies that apply are superkeys for the relation.Hence,all three relations satisfy the definition of BCNF.
Question13Consider a relation named EMP DEPT with attributes:ENAME,SSN,BDATE, ADDRESS,
DNUMBER,DNAME,and DMGRSSN.Consider also the set G of functional depen-dencies for EMP DEPT:
5

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。