數(shù)據(jù)庫(kù)系統(tǒng)概念(database system concepts)英文第六版 課后練習(xí)題 答案 第8章

8CHAPTERExercises8.1SupposethatwedecomposetheschemaR=(,B,C,,E)into(,B,C)(,,E).Showthatthisdecompositionisalossless-joindecompositionifthefollowingsetFoffunctionaldependenciesholds:A→BCCD→EB→DE→AAnswer:Adecomposition{R,R}isalossless-joindecompositionif12R∩R→RorR∩R→R.LetR=(,B,C),R=12112212(,,E),andR∩R=.SinceAisacandidatekey(seePractice12Exercise8.6),ThereforeR∩R→R.1218.2Listallfunctionaldependenciessatis?edbytherelationofFigure8.17.Answer:Thenontrivialfunctionaldependenciesare:A→BandC→B,andadependencytheylogicallyimply:AC→B.Thereare19trivialfunctionaldependenciesoftheform?→?,where???.CdoesnotfunctionallydetermineAbecausethe?rstandthirdtupleshavethesameCbutdifferentAvalues.ThesametuplesalsoshowBdoesnotfunctionallydetermineA.Likewise,AdoesnotfunctionallydetermineCbecausethe?rsttwotupleshavethesameAvalueanddifferentCvalues.ThesametuplesalsoshowBdoesnotfunctionallydetermineC.8.3Explainhowfunctionaldependenciescanbeusedtoindicatethefol-lowing:9810?Aone-to-onerelationshipsetexistsbetweenentitysetsstudentandinstructor.?Amany-to-onerelationshipsetexistsbetweenentitysetsstudentandinstructor.Answer:LetPkr)denotetheprimarykeyattributeofrelationr.?ThefunctionaldependenciesPk(student)→Pk(instructor)andPk(instructor)→Pk(student)indicateaone-to-onerelationshipbecauseanytwotupleswiththesamevalueforstudentmusthavethesamevalueforinstructor,andanytwotuplesagreeingoninstructormusthavethesamevalueforstudent.?ThefunctionaldependencyPk(student)→Pk(instructor)indicatesamany-to-onerelationshipsinceanystudentvaluewhichisrepeatedwillhavethesameinstructorvalue,butmanystudentvaluesmayhavethesameinstructorvalue.8.4UseArmstrong’saxiomstoprovethesoundnessoftheunionrule.(Hint:Usetheaugmentationruletoshowthat,if?→?,then?→.Applytheaugmentationruleagain,using?→?,andthenapplythetransitivityrule.)Answer:Toprovethat:if?→?and?→?then?→??Followingthehint,wederive:?→?given??→???→???→?augmentationruleunionofidenticalsetsgiven??→???→??augmentationruletransitivityruleandsetunioncommutativity8.5UseArmstrong’saxiomstoprovethesoundnessofthepseudotransitiv-ityrule.Answer:ProofusingArmstrong’saxiomsofthePseudotransitivityRule:if?→?and??→,then??→.?→?given??→????→???→?augmentationruleandsetunioncommutativitygiventransitivityrule8.6ComputetheclosureofthefollowingsetFoffunctionaldependenciesforrelationschemaR=(,B,C,,E).Exercises11A→BCCD→EB→DE→AListthecandidatekeysforR.Answer:Note:ItisnotreasonabletoexpectstudentstoenumerateallofF.Someshorthandrepresentationoftheresultshouldbeacceptable+aslongasthenontrivialmembersofFarefound.+StartingwithA→BC,wecanconclude:A→BandA→C.SinceA→BandB→,A→DSinceA→CDandCD→E,A→E(decomposition,transitive)(union,decom-position,transi-tive)SinceA→,wehave(re?exive)A→ABCDEfromtheabovestepsSinceE→,E→ABCDESinceCD→E,CD→ABCDESinceB→DandBC→C,BC→ABCDE(union)(transitive)(transitive)(augmentative,transitive)Also,C→C,D→,BD→,etc.Therefore,anyfunctionaldependencywith,E,BC,orCDonthelefthandsideofthearrowisinF,nomatterwhichotherattributesappear+intheFD.Allow*torepresentanysetofattributesinR,thenFis+BD→B,BD→,C→C,D→,BD→B,B→,B→B,B→B,andallFDsoftheformA?→?,BC?→?,CD?→?,E?→?where?isanysubsetof{,B,C,,E.Thecandidatekeysare,BC,C,andE.8.7UsingthefunctionaldependenciesofPracticeExercise8.6,computethecanonicalcoverF.cAnswer:ThegivensetofFDsFis:-A→BCCD→EB→DE→ATheleftsideofeachFDinFisunique.AlsononeoftheattributesintheleftsideorrightsideofanyoftheFDsisextraneous.ThereforethecanonicalcoverFisequaltoF.c8128.8ConsiderthealgorithminFigure8.18tocompute?.Showthatthis+algorithmismoreef?cientthantheonepresentedinFigure8.8(Sec-tion8.4.2)andthatitcomputes?correctly.+Answer:Thealgorithmiscorrectbecause:?IfAisaddedtoresultthenthereisaproofthat?→.Toseethis,observethat?→?triviallyso?iscorrectlypartofresult.IfA∈?isaddedtoresulttheremustbesomeFD?→?suchthatA∈?and?isalreadyasubsetofresult.(Otherwisefdcountwouldbenonzeroandtheifconditionwouldbefalse.)Afullproofcanbegivenbyinductiononthedepthofrecursionforanexecutionofaddin,butsuchaproofcanbeexpectedonlyfromstudentswithagoodmathematicalbackground.?IfA∈?,thenAiseventuallyaddedtoresult.Weprovethisby+inductiononthelengthoftheproofof?→AusingArmstrong’saxioms.Firstobservethatifprocedureaddiniscalledwithsomeargument?,alltheattributesin?willbeaddedtoresult.AlsoifaparticularFD’sfdcountbecomes0,alltheattributesinitstailwillde?nitelybeaddedtoresult.Thebasecaseoftheproof,A∈??A∈?,isobviouslytruebecausethe?rstcalltoaddin+hastheargument?.Theinductivehypothesesisthatif?→AcanbeprovedinnstepsorlessthenA∈result.Ifthereisaproofinn+1stepsthat?→,thenthelaststepwasanapplicationofeitherre?exivity,augmentationortransitivityonafact?→?provedinnorfewersteps.Ifre?exivityoraugmentationwasusedinthe(n+1)step,Amusthavebeeninresultbytheendofthenstthstepitself.Otherwise,bytheinductivehypothesis??result.Thereforethedependencyusedinproving?→?,A∈?willhavefdcountsetto0bytheendofthenstep.HenceAwillbethaddedtoresult.Toseethatthisalgorithmismoreef?cientthantheonepresentedinthechapternotethatwescaneachFDonceinthemainprogram.TheresultingarrayappearshassizeproportionaltothesizeofthegivenFDs.Therecursivecallstoaddinresultinprocessinglinearinthesizeofappears.HencethealgorithmhastimecomplexitywhichislinearinthesizeofthegivenFDs.Ontheotherhand,thealgorithmgiveninthetexthasquadratictimecomplexity,asitmayperformtheloopasmanytimesasthenumberofFDs,ineachloopscanningallofthemonce.8.9GiventhedatabaseschemaRa,b,c),andarelationrontheschemaR,writeanquerytotestwhetherthefunctionaldependencyb→choldsonrelationr.Alsowriteanassertionthatenforcesthefunc-tionaldependency.Assumethatnonullvaluesarepresent.(Althoughpartofthestandard,suchassertionsarenotsupportedbyanydatabaseimplementationcurrently.)Answer:Exercisesa.Thequeryisgivenbelow.Itsresultisnon-emptyifandonlyifb→cdoesnotholdonr.selectbfromrgroupbybhavingcount(distinctc)>1b.createassertionbtoccheck(notexists(selectbfromrgroupbybhavingcount(distinctc)>1))8.10Ourdiscussionoflossless-joindecompositionimplicitlyassumedthatattributesontheleft-handsideofafunctionaldependencycannottakeonnullvalues.Whatcouldgowrongondecomposition,ifthispropertyisviolated?Answer:Thenaturaljoinoperatorisde?nedintermsofthecartesianproductandtheselectionoperator.Theselectionoperator,givesunknownforanyqueryonanullvalue.Thus,thenaturaljoinexcludesalltupleswithnullvaluesonthecommonattributesfromthe?nalresult.Thus,thedecompositionwouldbelossy(inamannerdifferentfromtheusualcaseoflossydecomposition),ifnullvaluesoccurintheleft-handsideofthefunctionaldependencyusedtodecomposetherelation.(Nullvaluesinattributesthatoccuronlyintheright-handsideofthefunctionaldependencydonotcauseanyproblems.)8.11Inthedecompositionalgorithm,supposeyouuseafunctionalde-pendency?→?todecomposearelationschemar(,?,?)intor(,?)1andr(,?).2a.Whatprimaryandforeign-keyconstraintdoyouexpecttoholdonthedecomposedrelations?b.Giveanexampleofaninconsistencythatcanariseduetoanerroneousupdate,iftheforeign-keyconstraintwerenotenforcedonthedecomposedrelationsabove.c.WhenarelationisdecomposedintousingthealgorithminSection8.5.2,whatprimaryandforeignkeydependencieswouldyouexpectwillholdonthedecomposedschema?8Answer:14a.?shouldbeaprimarykeyforr,and?shouldbetheforeignkey1fromr,referencingr.21b.Iftheforeignkeyconstraintisnotenforced,thenadeletionofatuplefromrwouldnothaveacorrespondingdeletionfromthe1referencingtuplesinr.Insteadofdeletingatuplefromr,this2wouldamounttosimplysettingthevalueof?tonullinsometuples.c.Foreveryschemar()addedtotheschemabecauseofarulei?→?,?shouldbemadetheprimarykey.Also,acandidatekey?fortheoriginalrelationislocatedinsomenewlycreatedrelationr,andisaprimarykeyforthatrelation.kForeignkeyconstraintsarecreatedasfollows:foreachrelationrcreatedabove,iftheprimarykeyattributesofralsooccuriniianyotherrelationr,thenaforeignkeyconstraintiscreatedfromjthoseattributesinr,referencing(theprimarykeyof)r.ji8.12LetR,R,...,RbeadecompositionofschemaU.LetuU)bearela-12ntion,andletr=(u).ShowthatiRIu?r1r1···1r12nAnswer:Considersometupletinu.Notethatr=(u)impliesthatt[R]∈r,1≤i≤.Thus,iiiit[R]1t[R]1...1t[R]∈r1r1...1r12n12nBythede?nitionofnaturaljoin,t[R]1t[R]1...1t[R]=(?(t[R]×t[R]×...×t[R]))12n??12nwherethecondition?issatis?edifvaluesofattributeswiththesamenameinatupleareequalandwhere?=U.Thecartesianproductofsingletuplesgeneratesonetuple.Theselectionprocessissatis?edbecauseallattributeswiththesamenamemusthavethesamevaluesincetheyareprojectionsfromthesametuple.Finally,theprojectionclauseremovesduplicateattributenames.Bythede?nitionofdecomposition,U=R∪R∪...∪R,whichmeans12nthatallattributesoftareint[R]1t[R]1...1t[R].Thatis,tisequal12ntotheresultofthisjoin.Sincetisanyarbitrarytupleinu,u?r1r1...1r12n8.13ShowthatthedecompositioninPracticeExercise8.1isnotadependency-preservingdecomposition.Answer:ThedependencyB→Disnotpreserved.F,therestriction1ofFto(,B,C)isA→ABC,A→AB,A→AC,A→BC,ExercisesA→B,A→C,A→,B→B,C→C,AB→AC,AB→ABC,AB→BC,AB→AB,AB→,AB→B,AB→C,AC(sameasAB),BC(sameasAB),ABC(sameasAB).F,therestrictionofFto2C,,E)isA→ADE,A→,A→AE,A→DE,A→,A→,A→E,D→,E(sameas),,AE,DE,ADE(sameas).(F∪F)iseasilyseennottocontainB→Dsincetheonly+12inF∪FwithBastheleftsideisB→B,atrivialFD.WeshallseeinPracticeExercise8.15thatB→DisindeedinF.ThusB→Disnot12+preserved.NotethatCD→ABCDEisalsonotpreserved.Asimplerargumentisasfollows:FcontainsnodependencieswithD1ontherightsideofthearrow.FcontainsnodependencieswithBonthe2leftsideofthearrow.ThereforeforB→DtobepreservedtheremustbeanB→?inF+and?→DinF+(soB→Dwouldfollow12bytransitivity).Sincetheintersectionofthetwoschemesis,?=.ObservethatB→AisnotinF+sinceB=B.+18.14Showthatitispossibletoensurethatadependency-preservingdecom-positionintoisalossless-joindecompositionbyguaranteeingthatatleastoneschemacontainsacandidatekeyfortheschemabeingdecom-posed.(Hint:Showthatthejoinofalltheprojectionsontotheschemasofthedecompositioncannothavemoretuplesthantheoriginalrelation.)Answer:LetFbeasetoffunctionaldependenciesthatholdonaschemaR.Let?={R,R,...,R}beadependency-preservingsitionofR.LetXbeacandidatekeyforR.decompo-12nConsideralegalinstancerofR.Letj=Xr)1r)1r)...112r).Wewanttoprovethatr=j.RnttjtXtXWeclaimthatifandaretwotuplesinsuchthat[]=[],then1212t=t.Toprovethisclaim,weusethefollowinginductiveargument–LetF=F∪F∪...∪F,whereeachFistherestrictionofFtotheschemaRin?.ConsidertheuseofthealgorithmgiveninFigure8.8to12′12niicomputetheclosureofXunderF.Weuseinductiononthenumberof′timesthattheforloopinthisalgorithmisexecuted.?Basis:Inthe?rststepofthealgorithm,resultisassignedtoX,andhencegiventhatt[X]=t[X],weknowthattresult]=tresult]1212istrue.?InductionStep:Lettresult]=tresult]betrueattheendofthe12kthexecutionoftheforloop.Supposethefunctionaldependencyconsideredinthek+1thexecutionoftheforloopis?→?,andthat??result.??resultimpliesthatt[?]=t[?]istrue.Thefactsthat?→?holdsfor12someattributesetRin?,andthatt[R]andt[R]areinr)i1i2iRiimplythatt[?]=t[?]isalsotrue.Since?isnowaddedtoresultbythealgorithm,weknowthattresult]=tresult]istrueattheendofthek+1thexecutionoftheforloop.1212816Since?isdependency-preservingandXisakeyforR,allattributesinRareinresultwhenthealgorithmterminates.Thus,t[R]=t[R]istrue,12thatis,t=t–asclaimedearlier.Ourclaimimpliesthatthesizeof12(j)isequaltothesizeofj.Notealsothat(j)=r)=r(sinceXisakeyforR).ThuswehaveXXXprovedthatthesizeofjequalsthatofr.UsingtheresultofPracticeExercise8.12,weknowthatr?j.Henceweconcludethatr=j.NotethatsinceXistriviallyin,?∪{X}isadependency-preservinglossless-joindecompositioninto.8.15GiveanexampleofarelationschemaRandsetFoffunctionaldepen-′′denciessuchthatthereareatleastthreedistinctlossless-joindecompo-sitionsofRinto.′Answer:GiventherelationR=(,B,C,)thesetoffunctional′dependenciesF=A→B,C→,B→Callowsthreedistinct′decompositions.R={(,B),C,),(B,C)}1isinasisR={(,B),C,),(,C)}2R={(,B),C,),(,C)}2R={(B,C),(,),(,B)}38.16Letaprimeattributebeonethatappearsinatleastonecandidatekey.Let?and?besetsofattributessuchthat?→?holds,but?→?doesnothold.LetAbeanattributethatisnotin?,isnotin?,andforwhich?→Aholds.WesaythatAistransitivelydependenton?.Wecanrestateourde?nitionofasfollows:ArelationschemaRisinwithrespecttoasetFoffunctionaldependenciesiftherearenononprimeattributesAinRforwhichAistransitivelydependentonakeyforR.Showthatthisnewde?nitionisequivalenttotheoriginalone.Answer:SupposeRisinaccordingtothetextbookde?nition.Weshowthatitisinaccordingtothede?nitionintheexercise.LetAbeanonprimeattributeinRthatistransitivelydependentonakey?forR.Thenthereexists??Rsuchthat?→,?→?,A∈,A∈?,and?→?doesnothold.Butthen?→Aviolatesthetextbookde?nitionofsince?A∈?implies?→Aisnontrivial?Since?→?doesnothold,?isnotasuperkey?Aisnotanycandidatekey,sinceAisnonprimeExercisesNowweshowthatifRisinaccordingtotheexercisede?nition,itisinaccordingtothetextbookde?nition.SupposeRisnotinaccordingthethetextbookde?nition.Thenthereisan?→?thatfailsallthreeconditions.Thus??→?isnontrivial.??isnotasuperkeyforR.?SomeAin???isnotinanycandidatekey.ThisimpliesthatAisnonprimeand?→.Let?beacandidatekeyforR.Then?→,?→?doesnothold(since?isnotasuperkey),A∈?,andA∈?(sinceAisnonprime).ThusAistransitivelydependenton?,violatingtheexercisede?nition.8.17Afunctionaldependency?→?iscalledapartialdependencyifthereisapropersubset?of?suchthat?→?.Wesaythat?ispartiallydependenton?.ArelationschemaRisinsecondnormalform()ifeachattributeAinRmeetsoneofthefollowingcriteria:?Itappearsinacandidatekey.?Itisnotpartiallydependentonacandidatekey.Showthateveryschemaisin.(Hint:Showthateverypartialdependencyisatransitivedependency.)Answer:Referringtothede?nitionsinPracticeExercise8.16,arelationschemaRissaidtobeinifthereisnonon-primeattributeAinRforwhichAistransitivelydependen