數(shù)據(jù)庫(kù)范式習(xí)題答案

1、 NormalizationQuestionsandAnswersDatabaseSystems,CSCI4380-01SibelAdalOctober28,2002Question1SupposeyouaregivenarelationR=(A,B,C,D,E)withthefollowingfunctionaldependencies:CEfD,DfB,CfA.Findallcandidatekeys.IdentifythebestnormalformthatRsatisfies(1NF,2NF,3NF,orBCNF).IftherelationisnotinBCNF,decomposei

2、tuntilitbecomesBCNF.Ateachstep,identifyanewrelation,decomposeandre-computethekeysandthenormalformstheysatisfy.Answer.TheonlykeyisC,ETherelationisin1NFDecomposeintoR1=(A,C)andR2=(B,C,D,E).R1isinBCNF,R2isin2NF.DecomposeR2into,R21=(C,D,E)andR22=(B,D).BothrelationsareinBCNF.Question2Supposeyouaregivenar

3、elationR=(A,B,C,D,E)withthefollowingfunctionaldependencies:BCfADE,DfB.Findallcandidatekeys.IdentifythebestnormalformthatRsatisfies(1NF,2NF,3NF,orBCNF).IftherelationisnotinBCNF,decomposeituntilitbecomesBCNF.Ateachstep,identifyanewrelation,decomposeandre-computethekeysandthenormalformstheysatisfy.Answ

4、er.ThekeysareB,CandC,DTherelationisin3NFItcannotbeputintoBCNF,evenifIremoveDandputintoarelationoftheform(B,C,D)(IneedCforthefunctionaldependency),theresultingrelationwouldnotbeinBCNF.Question3SupposeyouaregivenarelationR=(A,B,C,D,E)withthefollowingfunctionaldependencies:BDfE,AfC.Showthatthedecomposi

5、tionintoR1=(A,B,C)andR2=(D,E)islossy.Youcanshowusinganymethod.Mysuggestionistoshowhowspurioustuplesresultfromthisdecompositionwithrespecttothetablebelow:ABCDE1234518344FindasingledependencyfromasingleattributeXtoanotherattributeYsuchthatwhenyouaddthedependencyXYtotheabovedependencies,thedecompositio

6、ninpartaisnolongerlossy.Answera.Ifweweretodecomposetherelationsinto:ABCDE1234518344andthenjointhetwo(inthiscasewithacartesianproduct),wewouldget:ABCDE12345183451234418344Tuples2and3arenotintheoriginalrelation.Hence,thisdecompositionislossy.b.Thisdecompositioncannotbemadelossless.Theproblemisthereisn

7、olongerawaytomakedecompositionoftheform(A,B,C),(C,D,E)canbemadelosslessbyaddinganFDBC.sureBDEholdsacrosstworelationssincesureBDEholdsacrosstworelationssincetheydonotshareanyattributes.However,alossyQuestion4YouaregiventhefollowingsetoffunctionaldependenciesforarelationR(A,B,C,D,E,F),F=ABC,DCAE,EF.Wh

8、atarethekeysofthisrelation?IsthisrelationinBCNF?Ifnot,explainwhybyshowingoneviolation.Isthedecomposition(A,B,C,D)(B,C,D,E,F)adependencypreservingdecomposition?Ifnot,explainbriefly.Answer.Whatarethekeysofthisrelation?A,B,DandB,C,D.IsthisrelationinBCNF?Ifnot,explainwhybyshowingoneviolation.No,allfunct

9、ionaldependenciesareactuallyviolatingthis.Nodependencycontainsasuperkeyonitsleftside.Isthedecomposition(A,B,C,D)(B,C,D,E,F)adependencypreservingdecomposition?Ifnot,explainbriefly.Yes,ABCandDCAarepreservedinthefirstrelation.DCEandEFarepreservedinthesecondrelation.Question5Youaregiventhebelowfunctiona

10、ldependenciesforrelationR(A,B,C,D,E),F=ABC,ABD,DA,BCD,BCE.IsthisrelationisinBCNF?Ifnot,showalldependenciesthatviolateit.Isthisrelationin3NF?Ifnot,showalldependenciesthatviolateit.Isthefollowingdependencyimpliedbytheabovesetofdependencies?Ifso,showhowusingtheAmstrongsAxiomsgiveninthebook(p.362-363):A

11、BCtAEAnswer.Keysfortherelation:A,B,B,D,B,C.NotinBCNFsinceDtAdoeshaveasuperkeyonthelefthandside.In3NFsinceinDtA,Aispartofakey.BCtE(given)ABCtAEbytheaugmentationrule.Question6YouaregiventhetablebelowforarelationR(A,B,C,D,E).Youdonotknowthefunctionaldependenciesforthisrelation.Thisquestionisindependent

12、ofQuestion2above.ABCDEa1221s1ae2364e2ba1991b5cb2132z8dSupposethisrelationisdecomposedintothefollowingtwotables:R1(A,B,C,D)andR2(A,C,E).Isthisdecompositionlossless?Explainyourreasoning.Answer.R1R2R1R2ABCDEABCDACEa1221s1aa1221s1a1ae2364e2be2364e2e4ba1991b5ca1991b5a1cb2132z8db2132z8b2da1221s1aa1991b5cS

13、incethelasttworowsarenotintheoriginalrelation,thenthisdecompositionislossy.Question7YouaregiventhebelowsetoffunctionaldependenciesforarelationR(A,B,C,D,E,F,G),F=ADtBF,CDtEGC,BDtF,EtD,FtC,DtF.Findtheminimalcoverfortheabovesetoffunctionaldependenciesusingthealgorithmdescribedinclass.Givesufficientdeta

14、iltoshowyourreasoning,butbesuccinct.Youdonothavetolistallthecasesyoutest/considerforthealgorithm.Showallstepswhereyoumakechangestotheabovesetindetail.Usingthefunctionaldependenciesthatyoucomputedinstepa,findthekeysforthisrelation.IsitinBCNF?Explainyourreasoning.Supposewedecomposetheaboverelationinto

15、thefollowingtworelations:R1(A,B,C,D,E)R2(A,D,F,G)Usethefunctionaldependenciesintheminimalcover.Foreachrelation,writedownthefunctionaldependenciesthatfallwithinthatrelation(youcandecomposeadependencyoftheformADtBFintotwoi.e.ADtBandADtFwhencomputingthis).Usingthesefunctionaldependencies,determineifthi

16、sdecompositionislosslessand/ordependencypreserving.Explainyourreasoning.Answers.a.Step1.ADB,ADF,CDE,CDG,CDC,BDF,ED,FC,DFStep2.removeCDC,ADF,andBDF.ADB,CDE,CDG,FC,DF,EDStep3.removeDfromCDEandCDGADB,DE,DG,FC,DF,EDFinallyrecombineADB,DEGF,FC,ED.Keys:A,D,A,E.NotinBCNFsincethelastthreefunctionaldependenc

17、iesdonothaveasuperkeyonthelefthandside.R1(A,B,C,D,E)Dependencies:ADB,DE,EDR2(A,D,F,G)Dependencies:DGF.Notfunctionaldependencypreserving,thedependencyFCisnotpreserved.head(R1)Qhead(R2)=A,DR1:ADABCDEisnottruesinceCisnotimpliedbyA,DR2:ADADFGistruesincethisisimpliedbyDGFasfollows:ADADinclusionrule,since

18、DGF,usesetaccumulationrule,ADADGF.Hence,thisisalosslessdecomposition.Question8YouaregiventhefollowingsetFoffunctionaldependenciesforarelationR(A,B,C,D,E,F):F=ABCD,ABDE,CDF,CDFB,BFD.FindallkeysofRbasedonthesefunctionaldependencies.IsthisrelationinBoyce-CoddNormalForm?Isit3NF?Explainyouranswers.Canthe

19、setFbesimplified(byremovingfunctionaldependenciesorbyremovingattributesfromthelefthandsideoffunctionaldependencies)withoutchangingtheclosureofF(i.e.F+)?Hint.Considerthestepsoftheminimalcoveralgorithm.Doanyofthemapplytothisfunctionaldependency?Answer.Keys:A,B,CandA,C,DItisnotinBCNF.CounterexampleABDE

20、andABDisnotasuperkey.Itisnotin3NF.CounterexampleABDE,andABDisnotasuperkeyandEisnotprimeattribute(partofakey).LetFbeobtainedbyreplacingCDFBwithCDB.AccordingtoFandF,CD+=C,D,B,F.Hence,wecanremoveFfromthisfunctionaldependencywithoutchangingthemeaningofthesystem.Question9ConsiderrelationR(X,Y,Z).Relation

21、Rcurrentlyhasthreetuples:(6,4,2),(6,6,8)and(6,4,8).WhichofthefollowingthreefunctionaldependenciescanyouinferdonotholdforrelationR?Explainyouranswer.YXAnswer.Thefirstfunctionaldependencyholds,buttherestdonothold.Thesecondandthirdtuplesbothhave8forZbutdifferentvaluesofY.Thefirstandthirdtuplesbothhave6

22、and4forXandYbutdifferentvaluesforZ.Question10ConsidertherelationR(V,W,X,Y,Z)withfunctionaldependenciesZTY,YTZ,XTY,XTV,VWTX.ListthepossiblekeysforrelationRbasedonthefunctionaldependenciesabove.ShowtheclosureforattributeXgiventhefunctionaldependenciesabove.SupposethatrelationRisdecomposedintotworelati

23、ons,R1(V,W,X)andR2(X,Y,Z).Isthisdecompositionalosslessdecomposition?Explainyouranswer.Answer.V,W,X,WX+=X,V,Y,ZYesitislossless.Tobelosslesstheattributesincommonbetweenthetworelationsmustdeterminealltheattributesinoneofthetworelations.TheonlyattributeincommonisXanditfunctionallydeterminesalltheattribu

24、tesinR2.Question11GivenrelationR(W,X,Y,Z)andsetoffunctionaldependenciesF=XTW,WZTXY,YTWXZ.ComputetheminimalcoverforF.Answer.Step1:XTW,WZTX,WZTY,YTW,YTX,YTZStep2:DontneedWZTX,sinceWZTYandYTXDontneedYTW,sinceYTXandXTWThisleavesXTWWZTY,YTX,YTZStep3:OnlyneedtoconsiderWZTY.CanteliminateWorZ.Sonothingiseli

25、minated.Step4:XTWWZTY,YTXZistheminimalcoverQuestion12GivenrelationR(W,X,Y,Z)andsetoffunctionaldependenciesG=ZTW,YTXZ,XWTY,whereGisaminimalcover:DecomposeRintoasetofrelationsinThirdNormalForm.Isyourdecompositioninparta)alsoinBoyceCoddNormalForm?Explainyouranswer.Answer.Possiblekeys:Y,X,Z,W,XR1=(Z,W),

26、R2=(X,Y,Z),R3=(X,Y,W)Yes.Ineachofthethreerelations,theleftsideofthefuncationaldependenciesthatapplyaresuperkeysfortherelation.Hence,allthreerelationssatisfythedefinitionofBCNF.Question13ConsiderarelationnamedEMP_DEPTwithattributes:ENAME,SSN,BDATE,ADDRESS,DNUMBER,DNAME,andDMGRSSN.ConsideralsothesetGo

27、ffunctionaldependenciesforEMPDEPT:G=SSNENAMEBDATEADDRESSDNUMBER,DNUMBERDNAME,DMGRSSM.CalculatetheclosuresSSN+andDNAME+withrespecttoG.IsthesetoffunctionaldependencesGminimal?Ifnot,findaminimalsetoffunctionaldependenciesthatisequivalenttoG.ListanupdateanomalythatcanoccurforrelationEMPDEPT.ListaninsertionanomalythatcanoccurforrelationEMPDEPT.ListadeletionanomalythatcanoccurforrelationEMPDEPT.Answer.SSN+=SSN,ENAME,BDATE,ADDRESS,DNUMBER,DNAME,DMGRSSNDNAME+=DNAMEItisminimal.Sinceeverymemberofadepartmenthasareferencetothemanagerofthatdepartment(i.e.,Dmgrssn),whenthedepartmentmanager