**Exercise3.1.1Answersforthisexercisemayvarybecauseofdifferentinterpretations.感謝閱讀SomepossibleFDs:SocialSecuritynumbername謝謝閱讀AreacodestateStreetaddress,city,statezipcode謝謝閱讀Possiblekeys:{SocialSecuritynumber,streetaddress,city,state,areacode,phonenumber}謝謝閱讀Needstreetaddress,city,statetouniquelydeterminelocation.Apersoncouldhavemultipleaddresses.Thesameistrueforphones.Thesedays,apersoncouldhavealandlineandacellularphone精品文檔放心下載Exercise3.1.2Answersforthisexercisemayvarybecauseofdifferentinterpretations精品文檔放心下載SomepossibleFDs:IDx-position,y-position,z-position感謝閱讀IDx-velocity,y-velocity,z-velocity感謝閱讀x-position,y-position,z-positionID感謝閱讀Possiblekeys:{ID}{x-position,y-position,z-position}感謝閱讀Thereasonwhythepositionswouldbeakeyisnotwomoleculescanoccupythesamepoint.精品文檔放心下載Exercise3.1.3aThesuperkeysareanysubsetthatcontainsA1.Thus,thereare2(n-1)suchsubsets,sinceeachofthen-1attributesA2throughAnmayindependentlybechoseninorout.謝謝閱讀**Exercise3.1.3bThesuperkeysareanysubsetthatcontainsA1orA2.Thereare2(n-1)suchsubsetswhenconsideringA1andthen-1attributesA2throughAn.Thereare2(n-2)suchsubsetswhenconsideringA2andthen-2attributesA3throughAn.WedonotcountA1inthesesubsetsbecausetheyarealreadycountedinthefirstgroupofsubsets.Thetotalnumberofsubsets謝謝閱讀is2(n-1)+2(n-2).Exercise3.1.3cThesuperkeysareanysubsetthatcontains{A1,A2}or{A3,A4}.Thereare2(n-2)suchsubsetswhenconsidering{A1,A2}andthen-2attributesA3throughAn.Thereare2(n-2)–2(n-4)suchsubsetswhenconsidering{A3,A4}andattributesA5throughAnalongwiththeindividualattributesA1andA2.Wegetthe2(n-4)termbecausewehavetodiscardthesubsetsthatcontainthekey{A1,A2}toavoiddoublecounting.Thetotalnumberofsubsetsis2(n-2)+2(n-2)精品文檔放心下載–2(n-4).Exercise3.1.3dThesuperkeysareanysubsetthatcontains{A1,A2}or{A1,A3}.Thereare2(n-2)suchsubsetswhenconsidering{A1,A2}andthen-2attributesA3throughAn.Thereare2(n-3)suchsubsetswhenconsidering{A1,A3}andthen-3attributesA4throughAnWedonotcountA2inthesesubsetsbecausetheyarealreadycountedinthefirstgroupofsubsets.Thetotalnumberofsubsetsis2(n-2)+2(n-3).謝謝閱讀Exercise3.2.1aWecouldtryinferencerulestodeducenewdependenciesuntilwearesatisfiedwehavethemall.Amoresystematicwayistoconsidertheclosuresofall15nonemptysetsofattributes.精品文檔放心下載Forthesingleattributeswehave{A}+=A,{B}+=B,{C}+=ACD,and{D}+=AD.Thus,theonlynewdependencywegetwithasingleattributeontheleftisCA.感謝閱讀**Nowconsiderpairsofattributes:精品文檔放心下載{AB}+=ABCD,sowegetnewdependencyABD.{AC}+=ACD,andACDisnontrivial.{AD}+=AD,sonothingnew.{BC}+=ABCD,sowegetBCA,andBCD.{BD}+=ABCD,givingusBDAandBDC.{CD}+=ACD,givingCDA.感謝閱讀Forthetriplesofattributes,{ACD}+=ACD,buttheclosuresoftheothersetsareeachABCD.謝謝閱讀Thus,wegetnewdependenciesABCD,ABDC,andBCDA.感謝閱讀Since{ABCD}+=ABCD,wegetnonewdependencies.感謝閱讀Thecollectionof11newdependenciesmentionedaboveare:精品文檔放心下載CA,ABD,ACD,BCA,BCD,BDA,BDC,CDA,ABCD,ABDC,andBCDA.謝謝閱讀Exercise3.2.1bFromtheanalysisofclosuresabove,wefindthatAB,BC,andBDarekeys.AllothersetseitherdonothaveABCDastheclosureorcontainoneofthesethreesets.謝謝閱讀Exercise3.2.1cThesuperkeysareallthosethatcontainoneofthosethreekeys.Thatis,asuperkeythatisnotakeymustcontainBandmorethanoneofA,C,andD.Thus,the(proper)superkeysareABC,ABD,BCD,andABCD.謝謝閱讀Exercise3.2.2aForthesingleattributeswehave{A}+=ABCD,{B}+=BCD,{C}+=C,and{D}+=D.Thus,thenewdependenciesareACandAD.感謝閱讀Nowconsiderpairsofattributes:感謝閱讀{AB}+=ABCD,{AC}+=ABCD,{AD}+=ABCD,{BC}+=BCD,{BD}+=BCD,{CD}+=CD.ThusthenewdependenciesareABC,ABD,ACB,ACD,ADB,ADC,BCDandBDC.感謝閱讀**Forthetriplesofattributes,{BCD}+=BCD,buttheclosuresoftheothersetsareeachABCD.謝謝閱讀Thus,wegetnewdependenciesABCD,ABDC,andACDB.精品文檔放心下載Since{ABCD}+=ABCD,wegetnonewdependencies.謝謝閱讀Thecollectionof13newdependenciesmentionedaboveare:謝謝閱讀AC,AD,ABC,ABD,ACB,ACD,ADB,ADC,BCD,BDC,ABCD,ABDCandACDB.精品文檔放心下載Forthesingleattributeswehave{A}+=A,{B}+=B,{C}+=C,and{D}+=D.Thus,therearenonewdependencies.感謝閱讀Nowconsiderpairsofattributes:感謝閱讀{AB}+=ABCD,{AC}+=AC,{AD}+=ABCD,{BC}+=ABCD,{BD}+=BD,{CD}+=ABCD.ThusthenewdependenciesareABD,ADC,BCAandCDB.謝謝閱讀Forthetriplesofattributes,alltheclosuresofthesetsareeachABCD.Thus,wegetnewdependenciesABCD,ABDC,ACDBandBCDA.感謝閱讀Since{ABCD}+=ABCD,wegetnonewdependencies.感謝閱讀Thecollectionof8newdependenciesmentionedaboveare:謝謝閱讀ABD,ADC,BCA,CDB,ABCD,ABDC,ACDBandBCDA.謝謝閱讀Forthesingleattributeswehave{A}+=ABCD,{B}+=ABCD,{C}+=ABCD,and{D}+=ABCD.Thus,thenewdependenciesareAC,AD,BD,BA,CA,CB,DBandDC.謝謝閱讀Sinceallthesingleattributes’closuresareABCD,anysupersetofthesingleattributeswillalsoleadtoaclosureofABCD.Knowingthis,wecanenumeratetherestofthenewdependencies.精品文檔放心下載Thecollectionof24newdependenciesmentionedaboveare:謝謝閱讀AC,AD,BD,BA,CA,CB,DB,DC,ABC,ABD,ACB,ACD,ADB,ADC,BCA,BCD,BDA,BDC,CDA,CDB,ABCD,ABDC,ACDBandBCDA.感謝閱讀**Exercise3.2.2bFromtheanalysisofclosuresin3.2.2a(i),wefindthattheonlykeyisA.AllothersetseitherdonothaveABCDastheclosureorcontainA.感謝閱讀Fromtheanalysisofclosures3.2.2a(ii),wefindthatAB,AD,BC,andCDarekeys.AllothersetseitherdonothaveABCDastheclosureorcontainoneofthesefoursets.謝謝閱讀Fromtheanalysisofclosures3.2.2a(iii),wefindthatA,B,CandDarekeys.AllothersetseitherdonothaveABCDastheclosureorcontainoneofthesefoursets.精品文檔放心下載Exercise3.2.2cThesuperkeysareallthosesetsthatcontainoneofthekeysin3.2.2b(i).ThesuperkeysareAB,AC,AD,ABC,ABD,ACD,BCDandABCD.謝謝閱讀Thesuperkeysareallthosesetsthatcontainoneofthekeysin3.2.2b(ii).ThesuperkeysareABC,ABD,ACD,BCDandABCD.感謝閱讀Thesuperkeysareallthosesetsthatcontainoneofthekeysin3.2.2b(iii).ThesuperkeysareAB,AC,AD,BC,BD,CD,ABC,ABD,ACD,BCDandABCD.精品文檔放心下載Exercise3.2.3aSinceA1A2…AnCcontainsA1A2…An,thentheclosureofA1A2…AnCcontainsB.ThusitfollowsthatA1A2…AnCB.感謝閱讀Exercise3.2.3bFrom3.2.3a,weknowthatA1A2…AnCB.Usingtheconceptoftrivialdependencies,wecanshowthatA1A2…AnCC.ThusA1A2…AnCBC.謝謝閱讀Exercise3.2.3c**FromA1A2…AnE1E2…Ej,weknowthattheclosurecontainsB1B2…BmbecauseoftheFDA1A2…AnB1B2…Bm.TheB1B2…BmandtheE1E2…EjcombinetoformtheC1C2…Ck.ThustheclosureofA1A2…AnE1E2…EjcontainsDaswell.Thus,A1A2…AnE1E2…EjD.感謝閱讀Exercise3.2.3dFromA1A2…AnC1C2…Ck,weknowthattheclosurecontainsB1B2…BmbecauseoftheFDA1A2…AnB1B2…Bm.TheC1C2…CkalsotellusthattheclosureofA1A2…AnC1C2…CkcontainsD1D2…Dj.Thus,A1A2…AnC1C2…CkB1B2…BkD1D2…Dj.謝謝閱讀Exercise3.2.4aIfattributeArepresentedSocialSecurityNumberandBrepresentedaperson’sname,thenwewouldassumeABbutBAwouldnotbevalidbecausetheremaybemanypeoplewiththesamenameanddifferentSocialSecurityNumbers.謝謝閱讀Exercise3.2.4bLetattributeArepresentSocialSecurityNumber,BrepresentgenderandCrepresentname.謝謝閱讀SurelySocialSecurityNumberandgendercanuniquelyidentifyaperson’sname(i.e.謝謝閱讀ABC).ASocialSecurityNumbercanalsouniquelyidentifyaperson’sname(i.e.AC).感謝閱讀However,genderdoesnotuniquelydetermineaname(i.e.BCisnotvalid).精品文檔放心下載Exercise3.2.4cLetattributeArepresentlatitudeandBrepresentlongitude.Together,bothattributescanuniquelydetermineC,apointontheworldmap(i.e.ABC).However,neitherAnorBcanuniquelyidentifyapoint(i.e.ACandBCarenotvalid).謝謝閱讀Exercise3.2.5GivenarelationwithattributesA1A2…An,wearetoldthattherearenofunctionaldependenciesoftheformB1B2…Bn-1CwhereB1B2…Bn-1isn-1oftheattributesfromA1A2…AnandCistheremainingattributefromA1A2…An.Inthiscase,thesetB1B2…Bn-1andanysubsetdonotfunctionallydetermineC.Thustheonlyfunctionaldependenciesthatwecan感謝閱讀**makeareoneswhereCisonboththeleftandrighthandsides.AllofthesefunctionaldependencieswouldbetrivialandthustherelationhasnonontrivialFD’s.謝謝閱讀Exercise3.2.6Let’sprovethisbyusingthecontrapositive.WewishtoshowthatifX+isnotasubsetofY+,thenitmustbethatXisnotasubsetofY.謝謝閱讀IfX+isnotasubsetofY+,theremustbeattributesA1A2…AninX+thatarenotinY+.IfanyoftheseattributeswereoriginallyinX,thenwearedonebecauseYdoesnotcontainanyoftheA1A2…An.However,iftheA1A2…Anwereaddedbytheclosure,thenwemustexaminethecasefurther.AssumethattherewassomeFDC1C2…CmA1A2…AjwhereA1A2…AjissomesubsetofA1A2…An.ItmustbethenthatC1C2…CmorsomesubsetofC1C2…CmisinX.However,theattributesC1C2…CmcannotbeinYbecauseweassumedthatattributesA1A2…AnareonlyinX+andarenotinY+.Thus,XisnotasubsetofY.謝謝閱讀Byprovingthecontrapositive,wehavealsoprovedifX?Y,thenX+?Y+.感謝閱讀Exercise3.2.7ThealgorithmtofindX+isoutlinedonpg.76.Usingthatalgorithm,wecanprovethat(X+)+=X+.Wewilldothisbyusingaproofbycontradiction.謝謝閱讀Supposethat(X+)+≠X+.Thenfor(X+)+,itmustbethatsomeFDallowedadditionalattributestobeaddedtotheoriginalsetX+.Forexample,X+AwhereAissomeattributenotinX+.However,ifthiswerethecase,thenX+wouldnotbetheclosureofX.TheclosureofXwouldhavetoincludeAaswell.ThiscontradictsthefactthatweweregiventheclosureofX,X+.Therefore,itmustbethat(X+)+=X+orelseX+isnottheclosureofX.精品文檔放心下載Exercise3.2.8aIfallsetsofattributesareclosed,thentherecannotbeanynontrivialfunctionaldependencies.SupposeA1A2...AnBisanontrivialdependency.Then{A1A2...An}+containsBandthusA1A2...Anisnotclosed.精品文檔放心下載**Exercise3.2.8bIftheonlyclosedsetsare?and{A,B,C,D},thenthefollowingFDshold:感謝閱讀ABBACADAABCABDACBACDADBADCBCABCDBDABDCCDACDBABCDABDCACDBBCDA感謝閱讀

AC ADBC BDCB CDDB DCExercise3.2.8cIftheonlyclosedsetsare?,{A,B}and{A,B,C,D},thenthefollowingFDshold:精品文檔放心下載ABBACA CB CDDA DB DCACBACDADBADCBCABCDBDABDCCDACDBABCDABDCACDB**BCDAExercise3.2.9WecanthinkofthisproblemasasituationwheretheattributesA,B,Crepresentcitiesandthefunctionaldependenciesrepresentonewaypathsbetweenthecities.Theminimalbasesaretheminimalnumberofpathwaysthatareneededtoconnectthecities.Wedonotwanttocreateanotherroadwayifthetwocitiesarealreadyconnected.謝謝閱讀Thesystematicwaytodothiswouldbetocheckallpossiblesetsofthepathways.However,wecansimplifythesituationbynotingthatittakesmorethantwopathwaystovisitthetwoothercitiesandcomeback.Also,ifwefindasetofpathwaysthatisminimal,addingadditionalpathwayswillnotcreateanotherminimalset.精品文檔放心下載Thetwosetsofminimalbasesthatweregiveninexample3.11are:感謝閱讀{AB,BC,CA}{AB,BA,BC,CB}Theadditionalsetsofminimalbasesare:感謝閱讀{CB,BA,AC}{AB,AC,BA,CA}{AC,BC,CA,CB}Exercise3.2.10aWeneedtocomputetheclosuresofallsubsetsof{ABC},althoughthereisnoneedtothink精品文檔放心下載abouttheemptysetorthesetofallthreeattributes.Herearethecalculationsforthe感謝閱讀remainingsixsets:{A}+=A{B}+=B{C}+=ACE{AB}+=ABCDE{AC}+=ACE**{BC}+=ABCDEWeignoreDandE,soabasisfortheresultingfunctionaldependenciesforABCis:CAandABC.NotethatBC->Aistrue,butfollowslogicallyfromC->A,andthereforemaybeomittedfromourlist.謝謝閱讀Exercise3.2.10bWeneedtocomputetheclosuresofallsubsetsof{ABC},althoughthereisnoneedtothink感謝閱讀abouttheemptysetorthesetofallthreeattributes.Herearethecalculationsforthe謝謝閱讀remainingsixsets:{A}+=AD{B}+=B{C}+=C{AB}+=ABDE{AC}+=ABCDE{BC}+=BCWeignoreDandE,soabasisfortheresultingfunctionaldependenciesforABCis:ACB.感謝閱讀Exercise3.2.10cWeneedtocomputetheclosuresofallsubsetsof{ABC},althoughthereisnoneedtothink謝謝閱讀abouttheemptysetorthesetofallthreeattributes.Herearethecalculationsforthe謝謝閱讀remainingsixsets:{A}+=A{B}+=B{C}+=C{AB}+=ABD{AC}+=ABCDE{BC}+=ABCDEWeignoreDandE,soabasisfortheresultingfunctionaldependenciesforABCis:ACBandBCA.感謝閱讀**Exercise3.2.10dWeneedtocomputetheclosuresofallsubsetsof{ABC},althoughthereisnoneedtothink謝謝閱讀abouttheemptysetorthesetofallthreeattributes.Herearethecalculationsforthe感謝閱讀remainingsixsets:{A}+=ABCDE{B}+=ABCDE{C}+=ABCDE{AB}+=ABCDE{AC}+=ABCDE{BC}+=ABCDEWeignoreDandE,soabasisfortheresultingfunctionaldependenciesforABCis:AB,BCandCA.謝謝閱讀Exercise3.2.11ForsteponeofAlgorithm3.7,supposewehavetheFDABCDE.WewanttouseArmstrong’sAxiomstoshowthatABCDandABCEfollow.SurelythefunctionaldependenciesDEDandDEEholdbecausetheyaretrivialandfollowthereflexivityproperty.Usingthetransitivityrule,wecanderivetheFDABCDfromtheFDsABCDEandDED.Likewise,wecandothesameforABCDEandDEEandderivetheFDABCE.精品文檔放心下載ForstepstwothroughfourofAlgorithm3.7,supposewehavetheinitialsetofattributesoftheclosureasABC.SupposealsothatwehaveFDsCDandDE.AccordingtoAlgorithm3.7,theclosureshouldbecomeABCDE.TakingtheFDCDandaugmentingbothsideswithattributesABwegettheFDABCABD.WecanusethesplittingmethodinsteponetogettheFDABCD.SinceDisnotintheclosure,wecanaddattributeD.TakingtheFDDEandaugmentingbothsideswithattributesABCwegettheFDABCDABCDE.UsingagainthesplittingmethodinsteponewegettheFDABCDE.SinceEisnotintheclosure,wecanaddattributeE.精品文檔放心下載GivenasetofFDs,wecanprovethataFDFfollowsbytakingtheclosureoftheleftsideofFDF.ThestepstocomputetheclosureinAlgorithm3.7canbemimickedbyArmstrong’saxiomsandthuswecanproveFfromthegivensetofFDsusingArmstrong’saxioms.精品文檔放心下載**Exercise3.3.1aInthesolutiontoExercise3.2.1wefoundthatthereare14nontrivialdependencies,includingthethreegivenonesandelevenderiveddependencies.Theyare:CA,CD,DA,ABD,ABC,ACD,BCA,BCD,BDA,BDC,CDA,ABCD,ABDC,andBCDA.精品文檔放心下載WealsolearnedthatthethreekeyswereAB,BC,andBD.Thus,anydependencyabovethatdoesnothaveoneofthesepairsontheleftisaBCNFviolation.Theseare:CA,CD,DA,ACD,andCDA.謝謝閱讀OnechoiceistodecomposeusingtheviolationCD.UsingtheaboveFDs,wegetACDandBCasdecomposedrelations.BCissurelyinBCNF,sinceanytwo-attributerelationis.UsingAlgorithm3.12todiscovertheprojectionofFDsonrelationACD,wediscoverthatACDisnotinBCNFsinceCisitsonlykey.However,DAisadependencythatholdsinABCDandthereforeholdsinACD.WemustfurtherdecomposeACDintoADandCD.Thus,thethreerelationsofthedecompositionareBC,AD,andCD.感謝閱讀Exercise3.3.1bBycomputingtheclosuresofall15nonemptysubsetsofABCD,wecanfindallthenontrivialFDs.TheyareBC,BD,ABC,ABD,BCD,BDC,ABCDandABDC.FromtheclosureswecanalsodeducethattheonlykeyisAB.Thus,anydependencyabovethatdoesnotcontainABontheleftisaBCNFviolation.Theseare:BC,BD,BCDandBDC.精品文檔放心下載OnechoiceistodecomposeusingtheviolationBC.UsingtheaboveFDs,wegetBCDandABasdecomposedrelations.ABissurelyinBCNF,sinceanytwo-attributerelationis.UsingAlgorithm3.12todiscovertheprojectionofFDsonrelationBCD,wediscoverthatBCDisinBCNFsinceBisitsonlykeyandtheprojectedFDsallhaveBontheleftside.ThusthetworelationsofthedecompositionareABandBCD.精品文檔放心下載Exercise3.3.1c**InthesolutiontoExercise3.2.2(ii),wefoundthatthereare12nontrivialdependencies,includingthefourgivenonesandtheeightderivedones.TheyareABC,BCD,CDA,ADB,ABD,ADC,BCA,CDB,ABCD,ABDC,ACDBandBCDA.謝謝閱讀WealsofoundoutthatthekeysareAB,AD,BC,andCD.Thus,anydependencyabovethatdoesnothaveoneofthesepairsontheleftisaBCNFviolation.However,alloftheFDscontainakeyontheleftsotherearenoBCNFviolations.感謝閱讀NodecompositionisnecessarysincealltheFDsdonotviolateBCNF.謝謝閱讀Exercise3.3.1dInthesolutiontoExercise3.2.2(iii),wefoundthatthereare28nontrivialdependencies,精品文檔放心下載includingthefourgivenonesandthe24derivedones.TheyareAB,BC,CD,DA,感謝閱讀AC,AD,BD,BA,CA,CB,DB,DC,ABC,ABD,ACB,ACD,ADB,ADC,感謝閱讀BCA,BCD,BDA,BDC,CDA,CDB,ABCD,ABDC,ACDBandBCDA.精品文檔放心下載WealsofoundoutthatthekeysareA,B,C,D.Thus,anydependencyabovethatdoesnothaveoneoftheseattributesontheleftisaBCNFviolation.However,alloftheFDscontainakeyontheleftsotherearenoBCNFviolations.精品文檔放心下載NodecompositionisnecessarysincealltheFDsdonotviolateBCNF.感謝閱讀Exercise3.3.1eBycomputingtheclosuresofall31nonemptysubsetsofABCDE,wecanfindallthenontrivialFDs.TheyareABC,DEC,BD,ABD,BCD,BEC,BED,ABCD,ABDC,ABEC,ABED,ADEC,BCED,BDEC,ABCED,andABDEC.FromtheclosureswecanalsodeducethattheonlykeyisABE.Thus,anydependencyabovethatdoesnotcontainABEontheleftisaBCNFviolation.Theseare:ABC,DEC,BD,ABD,BCD,BEC,BED,ABCD,ABDC,ADEC,BCEDandBDEC.精品文檔放心下載OnechoiceistodecomposeusingtheviolationABC.UsingtheaboveFDs,wegetABCDandABEasdecomposedrelations.UsingAlgorithm3.12todiscovertheprojectionofFDsonrelationABCD,wediscoverthatABCDisnotinBCNFsinceABisitsonlykeyandtheFD感謝閱讀**BDfollowsforABCD.UsingviolationBDtofurtherdecompose,wegetBDandABCasdecomposedrelations.BDisinBCNFbecauseitisatwo-attributerelation.UsingAlgorithm3.12again,wediscoverthatABCisinBCNFsinceABistheonlykeyandABCistheonlynontrivialFD.GoingbacktorelationABE,followingAlgorithm3.12tellsusthatABEisinBCNFbecausetherearenokeysandnonontrivialFDs.ThusthethreerelationsofthedecompositionareABC,BDandABE.精品文檔放心下載Exercise3.3.1fBycomputingtheclosuresofall31nonemptysubsetsofABCDE,wecanfindallthe精品文檔放心下載nontrivialFDs.Theyare:CB,CD,CE,DB,DE,ABC,ABD,ABE,ACB,ACD,感謝閱讀ACE,ADB,ADC,ADE,BCD,BCE,BDE,CDB,CDE,CEB,CED,DEB,感謝閱讀ABCD,ABCE,ABDC,ABDE,ABEC,ABED,ACDB,ACDE,ACEB,ACED,精品文檔放心下載ADEB,ADEC,BCDE,BCED,CDEB,ABCDE,ABCED,ABDECandACDEB.From精品文檔放心下載theclosureswecanalsodeducethatthekeysareAB,ACandAD.Thus,anydependency精品文檔放心下載abovethatdoesnotcontainoneoftheabovepairsontheleftisaBCNFviolation.Theseare:謝謝閱讀CB,CD,CE,DB,DE,BCD,BCE,BDE,CDB,CDE,CEB,CED,DEB,精品文檔放心下載BCDE,BCEDandCDEB.OnechoiceistodecomposeusingtheviolationDB.UsingtheaboveFDs,wegetBDEandABCasdecomposedrelations.UsingAlgorithm3.12todiscovertheprojectionofFDsonrelationBDE,wediscoverthatBDEisinBCNFsinceD,BD,DEaretheonlykeysandalltheprojectedFDscontainD,BD,orDEintheleftside.GoingbacktorelationABC,followingAlgorithm3.12tellsusthatABCisnotinBCNFbecausesinceABandACareitsonlykeysandtheFDCBfollowsforABC.UsingviolationCBtofurtherdecompose,wegetBCandACasdecomposedrelations.BothBCandACareinBCNFbecausetheyaretwo-attributerelations.ThusthethreerelationsofthedecompositionareBDE,BCandAC.感謝閱讀Exercise3.3.2Yes,wewillgetthesameresult.BothABandABChaveAontheleftsideandpartoftheprocessofdecompositioninvolvesfinding{A}+toformonedecomposedrelationandAplustherestoftheattributesnotin{A}+asthesecondrelation.Bothcasesyieldthesamedecomposedrelations.精品文檔放心下載**Exercise3.3.3Yes,wewillstillgetthesameresult.BothABandABChaveAontheleftsideandpartoftheprocessofdecompositioninvolvesfinding{A}+toformonedecomposedrelationandAplustherestoftheattributesnotin{A}+asthesecondrelation.Bothcasesyieldthesamedecomposedrelations.感謝閱讀Exercise3.3.4ThisistakenfromExample3.21pg.95.感謝閱讀SupposethataninstanceofrelationRonlycontainstwotuples.謝謝閱讀ABC123425TheprojectionsofRontotherelationswithschemas{A,B}and{B,C}are:謝謝閱讀ABBC12234225Ifwedoanaturaljoinonthetwoprojections,wewillget:精品文檔放心下載ABC123125423425TheresultofthenaturaljoinisnotequaltotheoriginalrelationR.謝謝閱讀Exercise3.4.1a**Thisistheinitialtableau:感謝閱讀ABCDEabcd1e1a1bcde1ab1cd1eThisisthefinaltableauafterapplyingFDsBEandCEA.謝謝閱讀ABCDEabcd1e1abcde1ab1cd1eSincethereisnotanunsubscriptedrow,thedecompositionforRisnotlosslessforthissetofFDs.感謝閱讀WecanusethefinaltableauasaninstanceofRasanexampleforwhythejoinisnotlossless.謝謝閱讀Theprojectedrelationsare:感謝閱讀ABCabcab1cBCDbcd1bcdb1cd1ACEace1aceThejoinedrelationis:**ABCDEabcd1e1abcde1ab1cd1e1abcd1eabcdeab1cd1eThejoinedrelationhasthreemoretuplesthantheoriginaltableau.精品文檔放心下載Exercise3.4.1bThisistheinitialtableau:感謝閱讀ABCDEabcd1e1a1bcde1ab1cd1eThisisthefinaltableauafterapplyingFDsACEandBCD感謝閱讀ABCDEabcdea1bcde1ab1cd1eSincethereisanunsubscriptedrow,thedecompositionforRislosslessforthissetofFDs.感謝閱讀Exercise3.4.1cThisistheinitialtableau:感謝閱讀ABCDEabcd1e1a1bcde1**a b1 c d1 eThisisthefinaltableauafterapplyingFDsAD,DEandBD.精品文檔放心下載ABCDEabcdea1bcdeab1cdeSincethereisanunsubscriptedrow,thedecompositionforRislosslessforthissetofFDs.謝謝閱讀Exercise3.4.1dThisistheinitialtableau:精品文檔放心下載ABCDEabcd1e1a1bcde1ab1cd1eThisisthefinaltableauafterapplyingFDsAD,CDEandED謝謝閱讀ABCDEabcdea1bcdeab1cdeSincethereisanunsubscriptedrow,thedecompositionforRislosslessforthissetofFDs.感謝閱讀Exercise3.4.2WhenwedecomposearelationintoBCNF,wewillprojecttheFDsontothedecomposedrelationstogetnewsetsofFDs.ThesedependenciesarepreservediftheunionofthesenewsetsisequivalenttotheoriginalsetofFDs.謝謝閱讀**FortheFDsof3.4.1a,thedependenciesarenotpreserved.TheunionofthenewsetsofFDsisCEA.However,theFDBEisnotintheunionandcannotbederived.ThusthetwosetsofFDsarenotequivalent.謝謝閱讀FortheFDsof3.4.1b,thedependenciesarepreserved.TheunionofthenewsetsofFDsisACEandBCD.ThisispreciselythesameastheoriginalsetofFDsandthusthetwosetsofFDsareequivalent.謝謝閱讀FortheFDsof3.4.1c,thedependenciesarenotpreserved.TheunionofthenewsetsofFDsisBDandAE.TheFDsADandDEarenotintheunionandcannotbederived.ThusthetwosetsofFDsarenotequivalent.精品文檔放心下載FortheFDsof3.4.1d,thedependenciesarenotpreserved.TheunionofthenewsetsofFDsisACE.However,theFDsAD,CDEandEDarenotintheunionandcannotbederived.ThusthetwosetsofFDsarenotequivalent.感謝閱讀Exercise3.5.1aInthesolutiontoExercise3.3.1awefoundthatthereare14nontrivialdependencies.Theyare:CA,CD,DA,ABD,ABC,ACD,BCA,BCD,BDA,BDC,CDA,ABCD,ABDC,andBCDA.精品文檔放心下載WealsolearnedthatthethreekeyswereAB,BC,andBD.SincealltheattributesontherightsidesoftheFDsareprime,thereareno3NFviolations.謝謝閱讀Sincethereareno3NFviolations,itisnotnecessarytodecomposetherelation.感謝閱讀Exercise3.5.1bInthesolutiontoExercise3.3.1bwefoundthatthereare8nontrivialdependencies.TheyareBC,BD,ABC,ABD,BCD,BDC,ABCDandABDC.精品文檔放心下載WealsofoundoutthattheonlykeyisAB.FDswheretheleftsideisnotasuperkeyortheattributesontherightarenotpartofsomekeyare3NFviolations.The3NFviolationsareBC,BD,BCDandBDC.精品文檔放心下載**Usingalgorithm3.26,wecandecomposeintorelationsusingtheminimalbasisBCand謝謝閱讀BD.TheresultingdecomposedrelationswouldbeBCandBD.However,noneofthesetwosetsofattributesisasuperkey.ThusweaddrelationABtotheresult.ThefinalsetofdecomposedrelationsisBC,BDandAB.精品文檔放心下載Exercise3.5.1cInthesolutiontoExercise3.3.1cwefoundthatthereare12nontrivialdependencies.TheyareABC,BCD,CDA,ADB,ABD,ADC,BCA,CDB,ABCD,ABDC,ACDBandBCDA.感謝閱讀WealsofoundoutthatthekeysareAB,AD,BC,andCD.SincealltheattributesontherightsidesoftheFDsareprime,thereareno3NFviolations.精品文檔放心下載Sincethereareno3NFviolations,itisnotnecessarytodecomposetherelation.感謝閱讀Exercise3.5.1dInthesolutiontoExercise3.3.1dwefoundthatthereare28nontrivialdependencies.TheyareAB,BC,CD,DA,AC,AD,BD,BA,CA,CB,DB,DC,ABC,ABD,ACB,ACD,ADB,ADC,BCA,BCD,BDA,BDC,CDA,CDB,ABCD,ABDC,ACDBandBCDA.謝謝閱讀WealsofoundoutthatthekeysareA,B,C,D.SincealltheattributesontherightsidesoftheFDsareprime,thereareno3NFviolations.精品文檔放心下載Sincethereareno3NFviolations,itisnotnecessarytodecomposetherelation.謝謝閱讀Exercise3.5.1eInthesolutiontoExercise3.3.1ewefoundthatthereare16nontrivialdependencies.TheyareABC,DEC,BD,ABD,BCD,BEC,BED,ABCD,ABDC,ABEC,ABED,ADEC,BCED,BDEC,ABCED,andABDEC.謝謝閱讀**WealsofoundoutthattheonlykeyisABE.FDswheretheleftsideisnotasuperkeyortheattributesontherightarenotpartofsomekeyare3NFviolations.The3NFviolationsareABC,DEC,BD,ABD,BCD,BEC,BED,ABCD,ABDC,ADEC,BCEDandBDEC.謝謝閱讀Usingalgorithm3.26,wecandecomposeintorelationsusingtheminimalbasisABC,感謝閱讀DECandBD.TheresultingdecomposedrelationswouldbeABC,CDEandBD.However,noneofthesethreesetsofattributesisasuperkey.ThusweaddrelationABEtotheresult.ThefinalsetofdecomposedrelationsisABC,CDE,BDandABE.精品文檔放心下載Exercise3.5.1fInthesolutiontoExercise3.3.1fwefoundthatthereare41nontrivialdependencies.Theyare:CB,CD,CE,DB,DE,ABC,ABD,ABE,ACB,ACD,ACE,ADB,ADC,ADE,BCD,BCE,BDE,CDB,CDE,CEB,CED,DEB,ABCD,ABCE,ABDC,ABDE,ABEC,ABED,ACDB,ACDE,ACEB,ACED,ADEB,ADEC,BCDE,BCED,CDEB,ABCDE,ABCED,ABDECandACDEB.精品文檔放心下載WealsofoundoutthatthekeysareAB,ACandAD.FDswheretheleftsideisnotasuperkeyortheattributesontherightarenotpartofsomekeyare3NFviolations.The3NFviolationsareCE,DE,BCE,BDE,CDEandBCDE.謝謝閱讀Usingalgorithm3.26,wecandecomposeintorelationsusingtheminimalbasisABC,CD,