数据库系统基础教程第三章答案.pdf

《数据库系统基础教程第三章答案.pdf》由会员分享，可在线阅读，更多相关《数据库系统基础教程第三章答案.pdf（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数数据据库库系系统统基基础础教教程程第第三三章章答答案案-CAL-FENGHAI.-(YICAI)-Company One1Exercise 3.1.1Exercise 3.1.1Answers for this exercise may vary because of different interpretations.Some possible FDs:Social Security number nameArea code stateStreet address,city,state zipcodePossible keys:Social Security number,street a

2、ddress,city,state,area code,phone numberNeed street address,city,state to uniquely determine location.A person could have multipleaddresses.The same is true for phones.These days,a person could have a landline and a cellularphoneExercise 3.1.2Exercise 3.1.2Answers for this exercise may vary because

3、of different interpretationsSome possible FDs:ID x-position,y-position,z-positionID x-velocity,y-velocity,z-velocityx-position,y-position,z-position IDPossible keys:IDx-position,y-position,z-positionThe reason why the positions would be a key is no two molecules can occupy the same point.Exercise 3.

4、1.3aExercise 3.1.3aThe superkeys are any subset that contains A1.Thus,there are 2(n-1)such subsets,since each of the n-1attributes A2 through An may independently be chosen in or out.Exercise 3.1.3bExercise 3.1.3b(n-1)The superkeys are any subset that contains A1 or A2.There are 2 such subsets when(

5、n-2)considering A1 and the n-1 attributes A2 through An.There are 2 such subsets whenconsidering A2 and the n-2 attributes A3 through An.We do not count A1 in these subsetsbecause they are already counted in the first group of subsets.The total number of(n-1)(n-2)subsets is 2+2.Exercise 3.1.3cExerci

6、se 3.1.3c2The superkeys are any subset that contains A1,A2 or A3,A4.There are 2 such subsets(n-2)(n-4)when considering A1,A2 and the n-2 attributes A3 through An.There are 2 2 suchsubsets when considering A3,A4 and attributes A5 through An along with the individual(n-4)attributes A1 and A2.We get th

7、e 2 term because we have to discard the subsets that(n-2)contain the key A1,A2 to avoid double counting.The total number of subsets is 2+(n-2)(n-4)2 2.Exercise 3.1.3dExercise 3.1.3d(n-2)The superkeys are any subset that contains A1,A2 or A1,A3.There are 2 such subsets(n-3)when considering A1,A2 and

8、the n-2 attributes A3 through An.There are 2 such subsetswhen considering A1,A3 and the n-3 attributes A4 through An We do not count A2 in thesesubsets because they are already counted in the first group of subsets.The total number(n-2)(n-3)of subsets is 2+2.Exercise 3.2.1aExercise 3.2.1aWe could tr

9、y inference rules to deduce new dependencies until we are satisfied we havethem all.A more systematic way is to consider the closures of all 15 nonempty sets ofattributes.+For the single attributes we have A=A,B =B,C =ACD,and D =AD.Thus,theonly new dependency we get with a single attribute on the le

10、ft is CA.Now consider pairs of attributes:+AB =ABCD,so we get new dependency ABD.AC =ACD,and ACD is nontrivial.AD+=AD,so nothing new.BC=ABCD,so we get BCA,and BCD.BD =ABCD,giving us+BDA and BDC.CD =ACD,giving CDA.+For the triples of attributes,ACD=ACD,but the closures of the other sets are eachABCD.

11、Thus,we get new dependencies ABCD,ABDC,and BCDA.+Since ABCD =ABCD,we get no new dependencies.The collection of 11 new dependencies mentioned above are:CA,ABD,ACD,BCA,BCD,BDA,BDC,CDA,ABCD,ABDC,and BCDA.Exercise 3.2.1bExercise 3.2.1bFrom the analysis of closures above,we find that AB,BC,and BD are key

12、s.All other setseither do not have ABCD as the closure or contain one of these three sets.Exercise 3.2.1cExercise 3.2.1cThe superkeys are all those that contain one of those three keys.That is,a superkeythat is not a key must contain B and more than one of A,C,and D.Thus,the(proper)superkeys are ABC

13、,ABD,BCD,and ABCD.(n-2)3Exercise 3.2.2aExercise 3.2.2a+i)For the single attributes we have A=ABCD,B =BCD,C =C,and D =D.Thus,the new dependencies are AC and AD.Now consider pairs of attributes:+AB =ABCD,AC =ABCD,AD =ABCD,BC =BCD,BD =BCD,CD =CD.Thus the newdependencies are ABC,ABD,ACB,ACD,ADB,ADC,BCD

14、and BDC.+For the triples of attributes,BCD=BCD,but the closures of the other sets are eachABCD.Thus,we get new dependencies ABCD,ABDC,and ACDB.+Since ABCD =ABCD,we get no new dependencies.The collection of 13 new dependencies mentioned above are:AC,AD,ABC,ABD,ACB,ACD,ADB,ADC,BCD,BDC,ABCD,ABDC andACD

15、B.+ii)For the single attributes we have A=A,B =B,C =C,and D =D.Thus,there are no new dependencies.Now consider pairs of attributes:+AB =ABCD,AC =AC,AD =ABCD,BC =ABCD,BD =BD,CD =ABCD.Thus the newdependencies are ABD,ADC,BCA and CDB.For the triples of attributes,all the closures of the sets are each A

16、BCD.Thus,we getnew dependencies ABCD,ABDC,ACDB and BCDA.+Since ABCD =ABCD,we get no new dependencies.The collection of 8 new dependencies mentioned above are:ABD,ADC,BCA,CDB,ABCD,ABDC,ACDB and BCDA.+iii)For the single attributes we have A=ABCD,B =ABCD,C =ABCD,and D =ABCD.Thus,the new dependencies ar

17、e AC,AD,BD,BA,CA,CB,DB and DC.Since all the single attributes closures are ABCD,any superset of the singleattributes will also lead to a closure of ABCD.Knowing this,we can enumerate the restof the new dependencies.The collection of 24 new dependencies mentioned above are:AC,AD,BD,BA,CA,CB,DB,DC,ABC

18、,ABD,ACB,ACD,ADB,ADC,BCA,BCD,BDA,BDC,CDA,CDB,ABCD,ABDC,ACDB and BCDA.Exercise 3.2.2bExercise 3.2.2b4i)From the analysis of closures in 3.2.2a(i),we find that the only key is A.All othersets either do not have ABCD as the closure or contain A.ii)From the analysis of closures 3.2.2a(ii),we find that A

19、B,AD,BC,and CD are keys.All other sets either do not have ABCD as the closure or contain one of these four sets.iii)From the analysis of closures 3.2.2a(iii),we find that A,B,C and D are keys.Allother sets either do not have ABCD as the closure or contain one of these four sets.Exercise 3.2.2cExerci

20、se 3.2.2ci)The superkeys are all those sets that contain one of the keys in 3.2.2b(i).Thesuperkeys are AB,AC,AD,ABC,ABD,ACD,BCD and ABCD.ii)The superkeys are all those sets that contain one of the keys in 3.2.2b(ii).Thesuperkeys are ABC,ABD,ACD,BCD and ABCD.iii)The superkeys are all those sets that

21、contain one of the keys in 3.2.2b(iii).Thesuperkeys are AB,AC,AD,BC,BD,CD,ABC,ABD,ACD,BCD and ABCD.Exercise 3.2.3aExercise 3.2.3aSince A1A2AnC contains A1A2An,then the closure of A1A2AnC contains B.Thus it followsthat A1A2AnCB.Exercise 3.2.3bExercise 3.2.3bFrom 3.2.3a,we know that A1A2AnCB.Using the

22、 concept of trivial dependencies,we canshow that A1A2AnCC.Thus A1A2AnCBC.Exercise 3.2.3cExercise 3.2.3cFrom A1A2AnE1E2Ej,we know that the closure contains B1B2Bm because of the FD A1A2AnB1B2Bm.The B1B2Bm and the E1E2Ej combine to form the C1C2Ck.Thus the closure ofA1A2AnE1E2Ej contains D as well.Thu

23、s,A1A2AnE1E2EjD.Exercise 3.2.3dExercise 3.2.3dFrom A1A2AnC1C2Ck,we know that the closure contains B1B2Bm because of the FD A1A2AnB1B2Bm.The C1C2Ck also tell us that the closure of A1A2AnC1C2Ck contains D1D2Dj.Thus,A1A2AnC1C2CkB1B2BkD1D2Dj.Exercise 3.2.4aExercise 3.2.4aIf attribute A represented Soci

24、al Security Number and B represented a person s name,then we would assume AB but BA would not be valid because there may be many peoplewith the same name and different Social Security Numbers.5Exercise 3.2.4bExercise 3.2.4bLet attribute A represent Social Security Number,B represent gender and C rep

25、resent name.Surely Social Security Number and gender can uniquely identify a person s name(i.e.ABC).A Social Security Number can also uniquely identify a persons name(i.e.AC).However,gender does not uniquely determine a name(i.e.BC is not valid).Exercise 3.2.4cExercise 3.2.4cLet attribute A represen

26、t latitude and B represent longitude.Together,both attributescan uniquely determine C,a point on the world map(i.e.ABC).However,neither A nor Bcan uniquely identify a point(i.e.AC and BC are not valid).Exercise 3.2.5Exercise 3.2.5Given a relation with attributes A1A2An,we are told that there are no

27、functionaldependencies of the form B1B2Bn-1C where B1B2Bn-1 is n-1 of the attributes from A1A2Anand C is the remaining attribute from A1A2An.In this case,the set B1B2Bn-1 and anysubset do not functionally determine C.Thus the only functional dependencies that we canmake are ones where C is on both t

28、he left and right hand sides.All of these functionaldependencies would be trivial and thus the relation has no nontrivial FD s.Exercise 3.2.6Exercise 3.2.6+Lets prove this by using the contrapositive.We wish to show that if X is not a subset+of Y,then it must be that X is not a subset of Y.+If X is

29、not a subset of Y,there must be attributes A1A2An in X that are not in Y.Ifany of these attributes were originally in X,then we are done because Y does not containany of the A1A2An.However,if the A1A2An were added by the closure,then we mustexamine the case further.Assume that there was some FD C1C2

30、CmA1A2Aj where A1A2Aj issome subset of A1A2An.It must be then that C1C2Cm or some subset of C1C2Cm is in X.However,the attributes C1C2Cm cannot be in Y because we assumed that attributes A1A2An+are only in X and are not in Y.Thus,X is not a subset of Y.+By proving the contrapositive,we have also pro

31、ved if X Y,then X Y.Exercise 3.2.7Exercise 3.2.7+The algorithm to find X is outlined on pg.76.Using that algorithm,we can prove that+(X)=X.We will do this by using a proof by contradiction.+Suppose that(X)X.Then for(X),it must be that some FD allowed additional+attributes to be added to the original

32、 set X.For example,X A where A is some+attribute not in X.However,if this were the case,then X would not be the closure of X.The closure of X would have to include A as well.This contradicts the fact that we were6given the closure of X,X.Therefore,it must be that(X)=X or else X is not theclosure of

33、X.Exercise 3.2.8aExercise 3.2.8aIf all sets of attributes are closed,then there cannot be any nontrivial functional+dependencies.Suppose A1A2.AnB is a nontrivial dependency.Then A1A2.An contains Band thus A1A2.An is not closed.Exercise 3.2.8bExercise 3.2.8bIf the only closed sets are and A,B,C,D,the

34、n the following FDs hold:ABACADBABCBDCACBCDDADBDCABCABDACBACDADBADCBCABCDBDABDCCDACDBABCDABDCACDBBCDAExercise 3.2.8cExercise 3.2.8cIf the only closed sets are,A,B and A,B,C,D,then the following FDs hold:ABBACACBCDDADBDCACBACDADBADCBCABCDBDABDCCDACDBABCDABDCACDBBCDAExercise 3.2.9Exercise 3.2.9+7We ca

35、n think of this problem as a situation where the attributes A,B,C represent citiesand the functional dependencies represent one way paths between the cities.The minimalbases are the minimal number of pathways that are needed to connect the cities.We do notwant to create another roadway if the two ci

36、ties are already connected.The systematic way to do this would be to check all possible sets of the pathways.However,we can simplify the situation by noting that it takes more than two pathways tovisit the two other cities and come back.Also,if we find a set of pathways that isminimal,adding additio

37、nal pathways will not create another minimal set.The two sets of minimal bases that were given in example 3.11 are:AB,BC,CAAB,BA,BC,CBThe additional sets of minimal bases are:CB,BA,ACAB,AC,BA,CAAC,BC,CA,CBExercise 3.2.10aExercise 3.2.10aWe need to compute the closures of all subsets of ABC,although

38、there is no need tothink about the empty set or the set of all three attributes.Here are the calculationsfor the remaining six sets:+A=A+B=B+C=ACE+AB=ABCDE+AC=ACE+BC=ABCDEWe ignore D and E,so a basis for the resulting functional dependencies for ABC is:C Aand ABC.Note that BC-A is true,but follows l

39、ogically from C-A,and therefore may beomitted from our list.Exercise 3.2.10bExercise 3.2.10bWe need to compute the closures of all subsets of ABC,although there is no need tothink about the empty set or the set of all three attributes.Here are the calculationsfor the remaining six sets:+A=AD+B=B+C=C

40、+AB=ABDE8AC=ABCDE+BC=BCWe ignore D and E,so a basis for the resulting functional dependencies for ABC is:ACB.Exercise 3.2.10cExercise 3.2.10cWe need to compute the closures of all subsets of ABC,although there is no need tothink about the empty set or the set of all three attributes.Here are the cal

41、culationsfor the remaining six sets:+A=A+B=B+C=C+AB=ABD+AC=ABCDE+BC=ABCDEWe ignore D and E,so a basis for the resulting functional dependencies for ABC is:AC Band BCA.Exercise 3.2.10dExercise 3.2.10dWe need to compute the closures of all subsets of ABC,although there is no need tothink about the emp

42、ty set or the set of all three attributes.Here are the calculationsfor the remaining six sets:+A=ABCDE+B=ABCDE+C=ABCDE+AB=ABCDE+AC=ABCDE+BC=ABCDEWe ignore D and E,so a basis for the resulting functional dependencies for ABC is:A B,BC and CA.Exercise 3.2.11Exercise 3.2.11For step one of Algorithm 3.7

43、,suppose we have the FD ABCDE.We want to use Armstrongs Axioms to show that ABCD and ABCE follow.Surely the functional dependencies DEDand DEE hold because they are trivial and follow the reflexivity property.Using thetransitivity rule,we can derive the FD ABCD from the FDs ABCDE and DED.Likewise,we

44、 can do the same for ABCDE and DEE and derive the FD ABCE.For steps two through four of Algorithm 3.7,suppose we have the initial set ofattributes of the closure as ABC.Suppose also that we have FDs CD and DE.Accordingto Algorithm 3.7,the closure should become ABCDE.Taking the FD CD and augmenting b

45、othsides with attributes AB we get the FD ABCABD.We can use the splitting method in step+9one to get the FD ABCD.Since D is not in the closure,we can add attribute D.Takingthe FD DE and augmenting both sides with attributes ABC we get the FD ABCDABCDE.Using again the splitting method in step one we

46、get the FD ABCDE.Since E is not in theclosure,we can add attribute E.Given a set of FDs,we can prove that a FD F follows by taking the closure of the leftside of FD F.The steps to compute the closure in Algorithm 3.7 can be mimicked byArmstrongs axioms and thus we can prove F from the given set of F

47、Ds using Armstrong saxioms.Exercise 3.3.1aExercise 3.3.1aIn the solution to Exercise 3.2.1 we found that there are 14 nontrivial dependencies,including the three given ones and eleven derived dependencies.They are:C A,CD,DA,ABD,AB C,ACD,BCA,BCD,BDA,BDC,CDA,ABCD,ABDC,and BCDA.We also learned that the

48、 three keys were AB,BC,and BD.Thus,any dependency above thatdoes not have one of these pairs on the left is a BCNF violation.These are:C A,CD,DA,ACD,and CDA.One choice is to decompose using the violation CD.Using the above FDs,we get ACD andBC as decomposed relations.BC is surely in BCNF,since any t

49、wo-attribute relation is.Using Algorithm 3.12 to discover the projection of FDs on relation ACD,we discover thatACD is not in BCNF since C is its only key.However,DA is a dependency that holds inABCD and therefore holds in ACD.We must further decompose ACD into AD and CD.Thus,thethree relations of t

50、he decomposition are BC,AD,and CD.Exercise 3.3.1bExercise 3.3.1bBy computing the closures of all 15 nonempty subsets of ABCD,we can find all thenontrivial FDs.They are BC,BD,ABC,ABD,BCD,BDC,ABCD and ABDC.Fromthe closures we can also deduce that the only key is AB.Thus,any dependency above thatdoes n