数据库系统概念(database system concepts)英文第六版 课后练习

CHAPTER8

RelationalDatabaseDesignExercises

8.1SupposethatwedecomposetheschemaR=(A,B,C,D,E)into

(A,B,C)

(A,D,E).

Showthatthisdecompositionisalossless-joindecompositionifthefollowingsetFoffunctionaldependenciesholds:

A→BC

CD→E

B→D

E→A

Answer:Adecomposition{R1,R2}isalossless-joindecompositionifR1∩R2→R1orR1∩R2→R2.LetR1=(A,B,C),R2=(A,D,E),andR1∩R2=A.SinceAisacandidatekey(seePracticeExercise8.6),ThereforeR1∩R2→R1.

8.2Listallfunctionaldependenciessatis edbytherelationofFigure8.17.

Answer:Thenontrivialfunctionaldependenciesare:A→BandC→B,andadependencytheylogicallyimply:AC→B.Thereare19trivialfunctionaldependenciesoftheform → ,where .CdoesnotfunctionallydetermineAbecausethe rstandthirdtupleshavethesameCbutdifferentAvalues.ThesametuplesalsoshowBdoesnotfunctionallydetermineA.Likewise,AdoesnotfunctionallydetermineCbecausethe rsttwotupleshavethesameAvalueanddifferentCvalues.ThesametuplesalsoshowBdoesnotfunctionallydetermineC.Explainhowfunctionaldependenciescanbeusedtoindicatethefol-lowing:

98.3

10Chapter8RelationalDatabaseDesign

Aone-to-onerelationshipsetexistsbetweenentitysetsstudentandinstructor.

Amany-to-onerelationshipsetexistsbetweenentitysetsstudentandinstructor.

Answer:LetPk(r)denotetheprimarykeyattributeofrelationr.

ThefunctionaldependenciesPk(student)→Pk(instructor)andPk(instructor)→Pk(student)indicateaone-to-onerelationship

becauseanytwotupleswiththesamevalueforstudentmusthave

thesamevalueforinstructor,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

→ augmentationrule

→ unionofidenticalsets

→ given

→ augmentationrule

→ transitivityruleandsetunioncommutativity

8.5UseArmstrong’saxiomstoprovethesoundnessofthepseudotransitiv-

ityrule.Answer:ProofusingArmstrong’saxiomsofthePseudotransitivityRule:

if → and → ,then → .

→ given

→ augmentationruleandsetunioncommutativity → given

→ transitivityrule

8.6ComputetheclosureofthefollowingsetFoffunctionaldependencies

forrelationschemaR=(A,B,C,D,E).

Exercises11

A→BC

CD→E

B→D

E→A

ListthecandidatekeysforR.Answer:+Note:ItisnotreasonabletoexpectstudentstoenumerateallofF.SomeshorthandrepresentationoftheresultshouldbeacceptableaslongasthenontrivialmembersofF+arefound.

StartingwithA→BC,wecanconclude:A→BandA→C.

SinceA→BandB→D,A→D(decomposition,

transitive)SinceA→CDandCD→E,A→E(union,decom-position,transi-tive)

SinceA→A,wehave(re exive)A→ABCDEfromtheabovesteps(union)

SinceE→A,E→ABCDE(transitive)

SinceCD→E,CD→ABCDE(transitive)SinceB→DandBC→CD,BC→(augmentative,ABCDEtransitive)Also,C→C,D→D,BD→D,etc.

Therefore,anyfunctionaldependencywithA,E,BC,orCDonthelefthandsideofthearrowisinF+,nomatterwhichotherattributesappearintheFD.Allow*torepresentanysetofattributesinR,thenF+isBD→B,BD→D,C→C,D→D,BD→BD,B→D,B→B,B→BD,andallFDsoftheformA → ,BC → ,CD → ,E → where isanysubsetof{A,B,C,D,E}.ThecandidatekeysareA,BC,CD,andE.

8.7UsingthefunctionaldependenciesofPracticeExercise8.6,computethe

canonicalcoverFc.Answer:ThegivensetofFDsFis:-

A→BC

CD→E

B→D

E→A

TheleftsideofeachFDinFisunique.AlsononeoftheattributesintheleftsideorrightsideofanyoftheFDsisextraneous.ThereforethecanonicalcoverFcisequaltoF.

12Chapter8RelationalDatabaseDesign

8.8ConsiderthealgorithminFigure8.18tocompute +.Showthatthisalgorithmismoreef cientthantheonepresentedinFigure8.8(Sec-tion8.4.2)andthatitcomputes +correctly.

Answer:Thealgorithmiscorrectbecause:

IfAisaddedtoresultthenthereisaproofthat →A.Toseethis,observethat → triviallyso iscorrectlypartofresult.IfA∈ isaddedtoresulttheremustbesomeFD → suchthat

A∈ and isalreadyasubsetofresult.(Otherwisefdcount

wouldbenonzeroandtheifconditionwouldbefalse.)Afullproofcanbegivenbyinductiononthedepthofrecursionforanexecutionofaddin,butsuchaproofcanbeexpectedonlyfromstudentswithagoodmathematicalbackground.

IfA∈ +,thenAiseventuallyaddedtoresult.Weprovethisbyinductiononthelengthoftheproofof →AusingArmstrong’saxioms.Firstobservethatifprocedureaddiniscalledwithsomeargument ,alltheattributesin willbeaddedtoresult.AlsoifaparticularFD’sfdcountbecomes0,alltheattributesinitstailwillde nitelybeaddedtoresult.Thebasecaseoftheproof,

A∈ A∈ +,isobviouslytruebecausethe rstcalltoaddinhastheargument .Theinductivehypothesesisthatif →AcanbeprovedinnstepsorlessthenA∈result.Ifthereisaproofinn+1stepsthat →A,thenthelaststepwasanapplicationof

eitherre exivity,augmentationortransitivityonafact → provedinnorfewersteps.Ifre exivityoraugmentationwasusedinthe(n+1)ststep,Amusthavebeeninresultbytheendofthenthstepitself.Otherwise,bytheinductivehypothesis result.

Thereforethedependencyusedinproving → ,A∈ willhavefdcountsetto0bytheendofthenthstep.HenceAwillbeaddedtoresult.

Toseethatthisalgorithmismoreef cientthantheonepresentedinthechapternotethatwescaneachFDonceinthemainprogram.TheresultingarrayappearshassizeproportionaltothesizeofthegivenFDs.Therecursivecallstoaddinresultinprocessinglinearinthesizeofappears.HencethealgorithmhastimecomplexitywhichislinearinthesizeofthegivenFDs.Ontheotherhand,thealgorithmgiveninthetexthasquadratictimecomplexity,asitmayperformtheloopasmanytimesasthenumberofFDs,ineachloopscanningallofth …… 此处隐藏：13540字，全部文档内容请下载后查看。喜欢就下载吧 ……