数据库系统概念(database system concepts)英文第六版 课后练习题 答案 第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.2ListallfunctionaldependenciessatisfiedbytherelationofFigure8.17.Answer:Thenontrivialfunctionaldependenciesare:A→BandC→B,andadependencytheylogicallyimply:AC→B.Thereare19trivialfunctionaldependenciesoftheform␣→␤,where␤⊆␣.CdoesnotfunctionallydetermineAbecausethefirstandthirdtupleshavethesameCbutdifferentAvalues.ThesametuplesalsoshowBdoesnotfunctionallydetermineA.Likewise,AdoesnotfunctionallydetermineCbecausethefirsttwotupleshavethesameAvalueanddifferentCvalues.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(reflexive)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+algorithmismoreefficientthantheonepresentedinFigure8.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,alltheattributesinitstailwilldefinitelybeaddedtoresult.Thebasecaseoftheproof,A∈␣⇒A∈␣,isobviouslytruebecausethefirstcalltoaddin+hastheargument␣.Theinductivehypothesesisthatif␣→AcanbeprovedinnstepsorlessthenA∈result.Ifthereisaproofinn+1stepsthat␣→,thenthelaststepwasanapplicationofeitherreflexivity,augmentationortransitivityonafact␣→␤provedinnorfewersteps.Ifreflexivityoraugmentationwasusedinthe(n+1)step,Amusthavebeeninresultbytheendofthenstthstepitself.Otherwise,bytheinductivehypothesis␤⊆result.Thereforethedependencyusedinproving␤→␥,A∈␥willhavefdcountsetto0bytheendofthenstep.HenceAwillbethaddedtoresult.ToseethatthisalgorithmismoreefficientthantheonepresentedinthechapternotethatwescaneachFDonceinthemainprogram.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:Thenaturaljoinoperatorisdefinedintermsofthecartesianproductandtheselectionoperator.Theselectionoperator,givesunknownforanyqueryonanullvalue.Thus,thenaturaljoinexcludesalltupleswithnullvaluesonthecommonattributesfromthefinalresult.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...1r12n12nBythedefinitionofnaturaljoin,t[R]1t[R]1...1t[R]=(␴(t[R]×t[R]×...×t[R]))12n␣␤12nwherethecondition␤issatisfiedifvaluesofattributeswiththesamenameinatupleareequalandwhere␣=U.Thecartesianproductofsingletuplesgeneratesonetuple.Theselectionprocessissatisfiedbecauseallattributeswiththesamenamemusthavethesamevaluesincetheyareprojectionsfromthesametuple.Finally,theprojectionclauseremovesduplicateattributenames.Bythedefinitionofdecomposition,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:Inthefirststepofthealgorithm,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␣.Wecanrestateourdefinitionofasfollows:ArelationschemaRisinwithrespecttoasetFoffunctionaldependenciesiftherearenononprimeattributesAinRforwhichAistransitivelydependentonakeyforR.Showthatthisnewdefinitionisequivalenttotheoriginalone.Answer:SupposeRisinaccordingtothetextbookdefinition.Weshowthatitisinaccordingtothedefinitionintheexercise.LetAbeanonprimeattributeinRthatistransitivelydependentonakey␣forR.Thenthereexists␤⊆Rsuchthat␤→,␣→␤,A∈,A∈␤,and␤→␣doesnothold.Butthen␤→Aviolatesthetextbookdefinitionofsince•A∈␤implies␤→Aisnontrivial•Since␤→␣doesnothold,␤isnotasuperkey•Aisnotanycandidatekey,sinceAisnonprimeExercisesNowweshowthatifRisinaccordingtotheexercisedefinition,itisinaccordingtothetextbookdefinition.SupposeRisnotinaccordingthethetextbookdefinition.Thenthereisan␣→␤thatfailsallthreeconditions.Thus•␣→␤isnontrivial.•␣isnotasuperkeyforR.•SomeAin␤−␣isnotinanycandidatekey.ThisimpliesthatAisnonprimeand␣→.Let␥beacandidatekeyforR.Then␥→,␣→␥doesnothold(since␣isnotasuperkey),A∈␣,andA∈␥(sinceAisnonprime).ThusAistransitivelydependenton␥,violatingtheexercisedefinition.8.17Afunctionaldependency␣→␤iscalledapartialdependencyifthereisapropersubset␥of␣suchthat␥→␤.Wesaythat␤ispartiallydependenton␣.ArelationschemaRisinsecondnormalform()ifeachattributeAinRmeetsoneofthefollowingcriteria:•Itappearsinacandidatekey.•Itisnotpartiallydependentonacandidatekey.Showthateveryschemaisin.(Hint:Showthateverypartialdependencyisatransitivedependency.)Answer:ReferringtothedefinitionsinPracticeExercise8.16,arelationschemaRissaidtobeinifthereisnonon-primeattributeAinRforwhichAistransitivelydependen