數(shù)據(jù)庫系統(tǒng)基礎(chǔ)教程第三章答案

1、Answers for this exercise may vary because of different interpretations.Some possible FDs:Social Security numbernameArea codestateStreet address, city, statezipcodePossible keys:Social Security number, street address, city, state, area code, phone numberNeed streetaddress,city,statetouniquelydetermi

2、nelocation.A personcouldhavemultipleaddresses.The same istrueforphones.Thesedays,a personcouldhave a landline and a cellular phoneAnswers for this exercise may vary because of different interpretationsSome possible FDs:IDx-position, y-position, z-positionIDx-velocity, y-velocity, z-velocityx-positio

3、n, y-position, z-positionIDPossible keys:IDx-position, y-position, z-positionThe reason why the positions would be a key is no two molecules can occupy the same point.The superkeysareanysubsetthatcontainsA1.Thus,thereare2(n-1)suchsubsets,sinceeach of the n-1 attributes A2 through An may independentl

4、y be chosen in or out.The superkeysareanysubsetthat containsA1orA2.Thereare2(n-1)suchsubsetswhenconsideringAandthen-1attributesAthroughA .Thereare(n-2)suchsubsetswhen212nconsideringA2andthen-2attributesA3throughAn.We donotcountA1inthesesubsetsbecausetheyarealreadycountedinthefirstgroupofsubsets.Thet

5、otalnumberofsubsets is 2(n-1)+ 2 (n-2) .(n-2)The superkeys are any subset that contains A1,A 2 or A3,A 4. There are 2such subsetswhen considering12and the n-2 attributes3nThereare2(n-2)2(n-4)suchA,A A throughA .subsetswhenconsideringA 3,A 4andattributesA5throughAn alongwiththeindividualattributes1an

6、d2We getthe(n-4)termbecausewehavetodiscardthesubsetsthatAA .2contain the key A1 ,A 2 to avoid double counting. The total number of subsets is 2(n-2)+ 2(n-2) 2 (n-4) .(n-2)The superkeys are any subset that contains A1,A 2 or A1,A 3. There are 2such subsetswhen considering A123through An(n-3)such subs

7、ets,A and the n-2 attributes A. There are 2when consideringA 1,A 3and the n-3attributesA4throughAnWe do notcountA2inthesesubsets because they are already counted in the first group of subsets. The total numberof subsets is 2(n-2)+ 2 (n-3) .We couldtryinferencerulestodeducenew dependenciesuntilwe are

8、satisfiedwe havethem all.A moresystematicwayistoconsidertheclosuresofall15nonemptysetsofattributes.+=A,B+=B,C+ = ACD, and D+ = AD. Thus, theFor the single attributes we have Aonly new dependency we get with a single attribute on the left is CA.Now consider pairs of attributes:AB + = ABCD, so we get

9、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 BDAand BDC. CD + = ACD, giving CDA.+ = ACD, but the closures of the other sets are eachFor the triples of attributes, ACDABCD. Thus, we get new dependencies ABCD,

10、ABDC, and BCDA.Since ABCD + = ABCD, we get no new dependencies.The collection of 11 new dependencies mentioned above are:CA, ABD, AC D, BCA, BCD, BDA, BDC, CDA, ABCD, ABDC, and BCDA.From the analysis of closures above, we find that AB, BC, and BD are keys. All other setseither do not have ABCD as th

11、e closure or contain one of these three sets.The superkeys are all those that contain one of those three keys. That is, a superkey thatis not a key must contain B and more than one of A, C, and D. Thus, the (proper) superkeysare ABC, ABD, BCD, and ABCD.+ = ABCD, B+ = BCD, C+ = C, and D+ = D. Thus,i)

12、 For the single attributes we have Athe new dependencies are AC and AD.Now consider pairs of attributes:+= ABCD, AC+= ABCD, BC+AB= ABCD, AD= BCD, BD= BCD, CD= CD. Thus the newdependencies are ABC, ABD, ACB, ACD, ADB, ADC, BCD and BDC.For the triples of attributes, BCD+ = BCD, but the closures of the

13、 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 and ACDB.ii)Forthesingleattributeswe haveA += A,B +=B,C +=

14、C,andD+ =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 ABCD. Thus, we getnew dependenci

15、es 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)Forthesingleattributeswe haveA +=ABCD, B + =ABCD, C + =ABCD, andD+=ABCD. Thus, the new dependencies are AC, AD, BD,

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

17、ACB,ACD,ADB,ADC,BCA, BCD, BDA, BDC, CDA, CDB, ABCD, ABDC, ACDB and BCDA.Since A 1A2 AnC contains A1A2 An, then the closure of A1A2 AnC contains B. Thus it followsthat A1A2 AnCB.A ACC. ThusAACB. Using the concept of trivial dependencies, we can show that A1 2n1 2nA1A2 AnC BC.B B because of the FD AA

18、AFrom AA A E E E , we know that the closure contains B1 2n 1 2j1 2m1 2nB1B2 Bm. The B1B2 Bm and the E1E2 Ej combine to form the C1C2 Ck. Thus the closure of A1A2A E E E contains D as well. Thus, AAAEEED.n1 2j1 2n1 2jFrom A 1A2 AnC1C2 Ck , we know that the closure contains B1B2 Bm because of the FD A

19、1A2 AnB B B . The CC C also tell us that the closure of AA A CC C contains DD D . Thus,1 2m1 2k1 2n 1 2k1 2jA1A2 AnC1C2CkB1B2Bk D1D2 Dj .If attribute A represented Social Security Number and B represented a person s name, thenwe would assume AB but B A would not be valid because there may be many pe

20、ople with thesame name and different Social Security Numbers.Let attribute A represent Social Security Number, B represent gender and C represent name.SurelySocialSecurityNumberandgendercanuniquelyidentifya person s name (i.e.ABC). A Social Security Number can also uniquely identify a person s name

21、(i.e. AC).However, gender does not uniquely determine a name (i.e. BC is not valid).LetattributeArepresentlatitudeandBrepresentlongitude.Together,bothattributescan 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 B C are no

22、t valid).Exercise 3.2.5Givena relationwithattributesA1A2 An,wearetoldthattherearenofunctionaldependencies of the form BB BC where B B Bis n-1 of the attributes from AA A1 2n-11 2n-11 2nand CistheremainingattributefromA1A2 An.Inthiscase,thesetB1B2 Bn-1andanysubset do not functionally determine C. Thu

23、s the only functional dependencies that we canmake are ones where C is on both the left and right hand sides. All of these functionaldependencies would be trivial and thus the relation has no nontrivial FD s.Exercise 3.2.6+Let s prove this by using the contrapositive. We wish to show that if Xis not

24、 a subsetof Y + , then it must be that X is not a subset of Y.If X+ is not a subset of Y+, there must be attributes A1A2 An 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 A1A2 An. However, if the A1A2 An were added by t

25、he closure, then we must examineissomethecasefurther.Assume thattherewas some FDCCCAAAwhereAA A12m12j12jsubset of A1A2 An. It must be then that C1C2 C or some subset of C1C C is in X. However,the attributes Cm2mA A are onlyC C cannot be in Y because we assumed that attributes A11 2m2nin X + and are

26、not in Y+. Thus, X is not a subset of Y.+?Y +.By proving the contrapositive, we have also proved if X ? Y, then XExercise 3.2.7+ is outlined on pg. 76. Using that algorithm, we can prove thatThe algorithm to find X(X +) + = X +. We will do this by using a proof by contradiction.Suppose that(X+) +X+.

27、Thenfor(X +) +,itmustbethatsomeFDallowedadditionalattributestobeaddedtotheoriginalset X+. For example,X+AwhereAissomeattribute 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 weregive

28、ntheclosureofX,X+.Therefore,itmust bethat(X+) += X+orelseX+isnottheclosure of X.Ifallsetsofattributesareclosed,thentherecannotbeanynontrivialn +functionaldependencies.SupposeA1A2.A n Bisanontrivialdependency.ThenA 1A2.AcontainsBand thus AA .Anis not closed.1 2If the only closed sets are? and A,B,C,D

29、, then the following FDs hold:ABACADBABCBDCACBCDDADBDCABCABDAC BAC DAD BAD CBC ABC DBD ABD CCD ACD BABC DABD CACD BBCD AIf the only closed sets are?, A,B and A,B,C,D, then the following FDs hold:BACACBCDDADBDCAC BAC DAD BAD CBC ABC DBD ABD CCD ACD BABC DABD CACD BBCD AExercise 3.2.9We canthinkofthis

30、problemasasituationwheretheattributesA,B,Crepresentcitiesandthefunctionaldependenciesrepresentone waypathsbetweenthecities.Theminimalbases are the minimal number of pathways that are needed to connect the cities. We do notwant to create another roadway if the two cities are already connected.The sys

31、tematic 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 to visit thetwo other cities and come back. Also, if we find a set of pathways that is minimal, addingadditional pathways will not create a

32、nother 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, CBWe needtocomputetheclosuresofallsubsetsofABC,althoughthereisnoneedtothinkabout theempty setorthe set of allthree

33、attributes. Herearethecalculationsfor the remaining six sets:A +=AB +=BC +=ACEAB + =ABCDEAC + =ACEBC + =ABCDEWe ignore D and E, so a basis for the resulting functional dependencies for ABC is: CAand ABC. Note that BC-A is true, but follows logically from C-A, and therefore may beomitted from our lis

34、t.We needtocomputetheclosuresofallsubsetsofABC,althoughthereisnoneedtothinkabout theempty setorthe set of allthreeattributes. Herearethecalculationsfor the remaining six sets:+A =AD+C =CAB + =ABDE+AC =ABCDE+We ignore D and E, so a basis for the resulting functional dependencies for ABC is: ACWe need

35、tocomputetheclosuresofallsubsetsofABC,althoughthinkabout theempty setorthe set of allthreeattributes. Herefor the remaining six sets:+B =B+C =CB.thereisno needtoarethecalculations+AB =ABD+AC =ABCDE+BC =ABCDEWe ignore D and E, so a basis for the resulting functional dependencies for ABC is: ACBand BC

36、A.We needtocomputetheclosuresofallsubsetsofABC,althoughthereisnoneed tothinkabout theempty setorthe set of allthreeattributes. Herearethecalculationsfor the remaining six sets:A +=ABCDEB+=ABCDEC +=ABCDE+AB =ABCDEAC + =ABCDEBC + =ABCDEWe ignore D and E, so a basis for the resulting functional depende

37、ncies for ABC is: AB,BC and C A.For step one of Algorithm 3.7, suppose we have the FD ABCDE. We want to use Armstrong sAxioms to show that ABCD and ABCE follow. Surely the functional dependencies DED andDEEholdbecausetheyaretrivialandfollowthereflexivityproperty.Usingthetransitivity rule, we can der

38、ive the FD ABCD from the FDs ABCDE and DED. Likewise, wecan 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 of attributesof the closure as ABC. Suppose also that we have FDs CD and D E. According to Algorithm3.7,theclo

39、sureshouldbecomeABCDE. TakingtheFD CD andaugmentingbothsideswithattributes AB we get the FD ABCABD. We can use the splitting method in step one to getthe FD ABCD. Since D is not in the closure, we can add attribute D. Taking the FD DEand augmenting both sides with attributes ABC we get the FD ABCDAB

40、CDE. Using again thesplitting method in step one we get the FD ABCDE. Since E is not in the closure, we canadd attribute E.Givena set of FDs,wecan provethata FD FfollowsbytakingtheclosureoftheleftsideofFDF.ThestepstocomputetheclosureinAlgorithm3.7canbemimickedbyArmstrong s axioms and thus we can pro

41、ve F from the given set of FDs using Armstrong saxioms.InthesolutiontoExercise3.2.1wefoundthatthereare14nontrivialdependencies,including the three given ones and eleven derived dependencies. They are: CA, CD, DA,ABD, ABC, ACD, BCA, BCD, BDA, BDC, CDA, ABCD, ABDC, and BCDA.We also learned that the th

42、ree 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: CA, CD,DA, ACD, and CDA.One choice is to decompose using the violation CD. Using the above FDs, we get ACD andBC asdecomposedrelations.BC issurelyinBCNF,sinceanyt

43、wo-attributerelationis.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

44、of the decomposition are BC, AD, and CD.Bycomputingtheclosuresofall15nonemptysubsetsof ABCD,we can findallthenontrivial FDs. They are BC, BD, ABC, ABD, BCD, BDC, ABC D and ABDC. From theclosures we can also deduce that the only key is AB. Thus, any dependency above that doesnot contain AB on the lef

45、t is a BCNF violation. These are: BC, BD, BCD and BDC.One choice is to decompose using the violation BC. Using the above FDs, we get BCD andABasdecomposedrelations.ABissurelyinBCNF,sinceanytwo-attributerelationis.Using Algorithm 3.12 to discover the projection of FDs on relation BCD, we discover tha

46、t BCD is in BCNF since B is its only key and the projected FDs all have B on the left side.Thus the two relations of the decomposition are AB and BCD.C, BCD, CDA, ADB, ABD, ADC, BCA, CDB, ABCD, ABDC, ACDB and BCDA.We also found out that the keys are AB, AD, BC, and CD. Thus, any dependency above tha

47、tdoes not have one of these pairs on the left is a BCNF violation. However, all of the FDscontain a key on the left so there are no BCNF violations.No decomposition is necessary since all the FDs do not violate BCNF.B, BC, CD, DA, AC, AD, BD, BA, CA, CB, DB, DC, ABC, ABD, ACB,AC D, AD B, AD C, BC A,

48、 BC D,BD A,BDC,CDA,CD B,ABC D, ABDC,ACD BandBCD A.We also found out that the keys are A,B,C,D. Thus, any dependency above that does not haveone of these attributes on the left is a BCNF violation. However, all of the FDs contain akey on the left so there are no BCNF violations.No decomposition is ne

49、cessary since all the FDs do not violate BCNF.Bycomputingtheclosuresofall31nonemptysubsetsofABCDE,wecanfindallthenontrivialFDs.Theyare ABC,DEC,BD,ABD, BC D, BE C, BE D, ABC D,ABDC,ABEC, ABED, ADEC, BCED, BDEC, ABCED, and ABDEC. From the closures we can alsodeduce that the only key is ABE. Thus, any

50、dependency above that does not contain ABE ontheleftisaBCNF violation.Theseare:AB C,DEC,BD,ABD,BC D,BEC,BED,ABC D, ABDC, ADEC, BCED and BDEC.One choice is to decompose using the violation ABC. Using the above FDs, we get ABCD andABE asdecomposedrelations.UsingAlgorithm3.12todiscovertheprojectionofFD

51、sonrelation ABCD, we discover that ABCD is not in BCNF since AB is its only key and the FDB D followsforABCD. UsingviolationBD tofurtherdecompose, we getBD andABC asdecomposedrelations.BDisinBCNFbecauseitisatwo-attributerelation.UsingAlgorithm 3.12 again, we discover that ABC is in BCNF since AB is

52、the only key and ABCis the only nontrivial FD. Going back to relation ABE, following Algorithm 3.12 tells usthatABE isinBCNF becausetherearenokeysandnonontrivialFDs. Thusthethreerelations of the decomposition are ABC, BD and ABE.Bycomputingtheclosuresofall31nonemptysubsetsofABCDE,wecanfindallthenont

53、rivial FDs. They are: CB, CD, CE, DB, DE, ABC, ABD, ABE, ACB, ACD,ACE, ADB, ADC, ADE, BCD, BCE, BDE, CDB, CDE, CEB, CED, DEB, ABCD,ABC E,ABDC,ABD E,ABEC,ABED,ACD B,ACD E,ACE B,ACE D, ADEB,ADEC,BCD E,BCE D,CDE B,ABCD E,ABCE D,ABDE C andACDE B.Fromtheclosureswecanalsodeducethatthekeysare AB,AC andAD.

54、Thus,any dependencyabovethatdoesnotcontain one of the above pairs on the left is a BCNF violation. These are: CB, CD, CE,D B,DE, BCD, BCE, BDE, CDB, CDE, CEB, CED, DE B, BCDE, BCE D and CDE B.One choice is to decompose using the violation DB. Using the above FDs, we get BDE andABC asdecomposedrelati

55、ons.UsingAlgorithm3.12todiscovertheprojectionofFDsonrelation BDE, we discover that BDE is in BCNF since D, BD, DE are the only keys and alltheprojectedFDscontainD,BD,orDEintheleftside.Going backtorelationABC,following Algorithm 3.12 tells us that ABC is not in BCNF because since AB and AC are itsonl

56、y keys and the FD CB follows for ABC. Using violation CB to further decompose, weget BC and AC as decomposed relations. Both BC and AC are in BCNF because they are two-attribute relations. Thus the three relations of the decomposition are BDE, BC and AC.Exercise 3.3.2Yes, we will get the same result

57、. Both AB and A+BC have A on the left side and part ofthe processofdecompositioninvolvesfindingtoformone decomposed relationand AAplus the rest of the attributes not in A+ as the second relation. Both cases yield thesame decomposed relations.Exercise 3.3.3Yes, we will still get the same result. Both

58、 AB and A BC have A on the left side andpart of the process of decomposition involves finding A+ to form one decomposed relationand A plus the rest of the attributes not in A+ as the second relation. Both cases yieldthe same decomposed relations.This is taken from Example 3.21 pg. 95.Suppose that an

59、 instance of relation R only contains two tuples.ABC123425The projectionsofR onto therelationswith schemas A,B andB,C are:BCAB23122542If we do a natural join on the two projections, we will get:ABC123125423425The result of the natural join is not equal to the original relation R.This is the initial

60、tableau:ABCDEabcd1e1a1bcde1ab1cd1eThis is the final tableau after applying FDs BE and CE A.ABCDEabcd1e1abcde1ab1cd1eSince there is not an unsubscripted row, the decomposition for R is not lossless for this set of FDs.We can usethe finaltableau as an instance ofR as an example for why the join is not