Exercise 3.2.1 Consider a relation with schema R(A,B,C,D)and FD' sAB→C,C→D and D→A a)What are all the nontrieval FD's that follow from the given FD's?you should restrict yourself to FD's with single attributes on the right side. b)What are all the keys of R? c)What are all the superkeys for R that are not keys? Solutions: a)Nontrivial FD's (Implied FD's) Given FD's:AB→C,C→D,D→A A+=A,B+=B,C+={C,D,A},D+={D,A} AB+=(A,B,C,D),AC+=(A,C,,D),AD+=(A,D), BC+=(B,C,D,A),BD+={B,D,A,C),CD+=(C,D,A) ABC+=ABD+=BCD+=(B,C,D,A}ACD+=(ACD) Answer is: C->A,AB->D,AC->D,BC->A,BC->D,BD->A,BD->C, CD->A,ABC->D,ABD->C,and BCD->A. b)AB,BC,and BD are keys c)ABC,ABD,BCD,and ABCD
Exercise 3.2.1 Consider a relation with schema R(A,B,C,D) and FD’ s ABC, CD and DA a) What are all the nontrieval FD’ s that follow from the given FD’ s? you should restrict yourself to FD’s with single attributes on the right side. b) What are all the keys of R? c) What are all the superkeys for R that are not keys? Solutions: a) Nontrivial FD’ s (Implied FD’ s) Given FD’ s: ABC, CD, DA A+=A, B+=B,C+={C,D,A},D+={D,A} AB+={A,B,C,D},AC+={A,C,,D},AD+={A,D}, BC+={B,C,D,A},BD+={B,D,A,C},CD+={C,D,A} ABC+= ABD+=BCD+={B,C,D,A} ACD+={ACD} Answer is: C->A, AB->D, AC->D, BC->A, BC->D, BD->A, BD->C, CD->A, ABC->D, ABD->C, and BCD->A. b) AB, BC, and BD are keys c) ABC, ABD, BCD, and ABCD
Exercises3.3.1(已作为课堂练习) a)R(A,B,C,D)with FD'sAB→C,C→D,D→A C)R(A,B,C,D)with FD'SAB→C,BC→D,CD→A, AD→B 1)Indicate all the BCNF violations. 2)Decompose the relations,as necessary into collections of relations that are in BCNE Solution a) 1)C->A,C->D,D->A,AC->D,CD->A 2)Key are AB,BC,and BD BCNF:R1(AC),R2(BC),R3(CD) Or R1(CD),R2(BC),R3(AD)or... Solution c) 1)indicate all the BCNF violations Consider the closures of all 15 nonempty subsets of (A,B,C,D). A+=A,B+=B,C+=C,and D+=D.Thus we get no new FD’S. AB+=BC+=CD+=AD+=ABCD,AC+=AC,and BD+=BD.Thus we get new nontrivial FD's:AB→D,BC→A,CD→B, AD→C
Exercises 3.3.1 （已作为课堂练习） a) R(A,B,C,D) with FD’ s ABC, CD, DA c) R(A,B,C,D) with FD’s ABC, BCD, CDA, ADB 1) Indicate all the BCNF violations. 2) Decompose the relations, as necessary into collections of relations that are in BCNF Solution a) 1) C->A, C->D, D->A, AC->D, CD->A 2) Key are AB, BC, and BD BCNF: R1(AC), R2(BC), R3(CD) Or R1(CD),R2(BC),R3(AD) or… Solution c) 1) indicate all the BCNF violations Consider the closures of all 15 nonempty subsets of {A,B,C,D}. A+=A, B+=B, C+=C, and D+=D. Thus we get no new FD’ s. AB+=BC+=CD+=AD+=ABCD, AC+=AC, and BD+=BD. Thus we get new nontrivial FD’ s: ABD, BCA, CDB, ADC
ABC+=ABD+=ACD+=BCD+=ABCD.Thus we get new nontrivial FD's:ABC→D,ABD→C,ACD→B,BCE→A. To sum up,we can deduce 8 new nontrivial FD' s from the given 4 FD's. From above,we find that AB,BC,CD and AD are keys,and that all the nontrivial FD's for R contain a key on the left side.Thus there' re no BCNF violations. 2)R(A,B,C,D)is already in BCNF. Exercise 3.5.2 Consider the relation courses(C,T,H,R,S,G),whose attributes may be thought of informally as course,teacher,hour, room,student and grade.FD's:C→T,HR→C,HT→R, HS→R,CS→G. a)what are all the keys for Courses? b)Verify that the given FD's are their own minimal basis. c)Use the 3NF synthesis algorithm to find a lossless-join, dependency-preserving decomposition of R into 3NF relations.Are any
ABC+=ABD+=ACD+=BCD+=ABCD. Thus we get new nontrivial FD’ s: ABCD, ABDC, ACDB, BCEA. To sum up, we can deduce 8 new nontrivial FD’ s from the given 4 FD’ s. From above, we find that AB, BC, CD and AD are keys, and that all the nontrivial FD’ s for R contain a key on the left side. Thus there ’ re no BCNF violations. 2) R(A,B,C,D) is already in BCNF. Exercise 3.5.2 Consider the relation courses(C,T,H,R,S,G),whose attributes may be thought of informally as course, teacher, hour, room, student and grade. FD’s: CT, HRC, HTR, HSR, CSG. a) what are all the keys for Courses? b) Verify that the given FD’s are their own minimal basis. c) Use the 3NF synthesis algorithm to find a lossless-join, dependency-preserving decomposition of R into 3NF relations. Are any
of the relations not in BCNE? Solution: a)key:HS b)implied FD's:CH→R,TH今C,HR今T,CTH→R,. c)They are the minimal basis.Because Right sides are single attributes.No FD can be removed.No attribute can be removed from a left side. d)According to 3NF synthesis,the relation is decomposed into R1(CT),R2 (HRC),R3(HTR),R4(HSR),R5(CSG)they are also in BCNF. Exercise 3.6.3 a),c) a)R(A,B,C,D)with MVD'sA→→B,A→→C c)A relation R(A,B,C,D)with MVD AB→→C,and FD B→D O Find all the 4NF violations Decompose the relations into a collection of relation schemas in 4NF Find the keys of the relation based on FD's a)Solutions:
of the relations not in BCNF? Solution: a) key: HS b) implied FD’s: CHR, THC, HRT,CTHR,… c) They are the minimal basis. Because Right sides are single attributes. No FD can be removed.No attribute can be removed from a left side. d) According to 3NF synthesis, the relation is decomposed into R1(CT),R2(HRC),R3(HTR),R4(HSR),R5(CSG) they are also in BCNF. Exercise 3.6.3 a), c) a) R(A,B,C,D) with MVD’ s AB, AC c) A relation R(A,B,C,D) with MVD ABC, and FD BD Find all the 4NF violations Decompose the relations into a collection of relation schemas in 4NF Find the keys of the relation based on FD’s a) Solutions:
Key is ABCD Derive al1MWD's:A→→CD,A→→BD Find all 4 NF violations based on the definition R1(AB)R2 (ACD)>R1(AB)is in 4NF,while R2(ACD) with A→→cD,andA→→C,therefore decompose into R21(AC)R22(AD) c)Solution 1)find all the 4NF violation: The first step is to know what a key for the relational schema is based on FD's .It's easy to see that ABC is the only key of R.So the given MVD'sAB→→C,B→D and derived MWD'sAB→→D,B→→AC are a114 NF violations. 2)Decompose the relations By using AB→→C,we decompose R into R1(A,B,C) and R2 (A,B,D).Now B->D is again a 4NF violation for R2 and we further decompose R2 into R21(B,D) and R22(A,B).R22 is a part of R1,so we omit it.Obviously,R1,R21 together constitute a 4NF decomposition of R
Key is ABCD Derive all MVD’ s : ACD, ABD Find all 4 NF violations based on the definition R1(AB) R2(ACD) R1(AB)is in 4NF, while R2(ACD) with ACD, and AC, therefore decompose into R21(AC)R22(AD) c) Solution 1) find all the 4NF violation: The first step is to know what a key for the relational schema is based on FD’s It’ s easy to see that ABC is the only key of R. So the given MVD’ s ABC, BD and derived MVD’ s ABD, BAC are all 4NF violations. 2) Decompose the relations By using ABC, we decompose R into R1(A,B,C) and R2(A,B,D). Now BD is again a 4NF violation for R2 and we further decompose R2 into R21(B,D) and R22(A,B). R22 is a part of R1, so we omit it. Obviously, R1, R21 together constitute a 4NF decomposition of R