數(shù)據(jù)庫(kù)系統(tǒng)基礎(chǔ)教程第三章答案

Exercise3.1.1

Answersforthisexercisemayvarybecauseofdifferentinterpretations.

SomepossibleFDs:

SocialSecuritynumbername

Areacodestate

Streetaddress,city,statezipcode

Possiblekeys:

{SocialSecuritynumber,streetaddress,city,state,areacode,phonenumber}

Needstreetaddress,city,statetouniquelydeterminelocation.Apersoncouldhavemultipleaddresses.Thesameistrueforphones.Thesedays,apersoncouldhavealandlineandacellularphone

Exercise3.1.2

Answersforthisexercisemayvarybecauseofdifferentinterpretations

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.3a

ThesuperkeysareanysubsetthatcontainsA1.Thus,thereare2(n-1)suchsubsets,sinceeachofthen-1attributesA2throughAnmayindependentlybechoseninorout.

Exercise3.1.3b

ThesuperkeysareanysubsetthatcontainsA1orA2.Thereare2(n-1)suchsubsetswhenconsideringA1andthen-1attributesA2throughAn.Thereare2(n-2)suchsubsetswhenconsideringA2andthen-2attributesA3throughAn.WedonotcountA1inthesesubsetsbecausetheyarealreadycountedinthefirstgroupofsubsets.Thetotalnumberofsubsetsis2(n-1)+2(n-2).

Exercise3.1.3c

Thesuperkeysareanysubsetthatcontains{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.3d

Thesuperkeysareanysubsetthatcontains{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.1a

Wecouldtryinferencerulestodeducenewdependenciesuntilwearesatisfiedwehavethemall.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.1b

Fromtheanalysisofclosuresabove,wefindthatAB,BC,andBDarekeys.AllothersetseitherdonothaveABCDastheclosureorcontainoneofthesethreesets.

Exercise3.2.1c

Thesuperkeysareallthosethatcontainoneofthosethreekeys.Thatis,asuperkeythatisnotakeymustcontainBandmorethanoneofA,C,andD.Thus,the(proper)superkeysareABC,ABD,BCD,andABCD.

Exercise3.2.2a

i)Forthesingleattributeswehave{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.

ii)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.

iii)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.2b

i)Fromtheanalysisofclosuresin3.2.2a(i),wefindthattheonlykeyisA.AllothersetseitherdonothaveABCDastheclosureorcontainA.

ii)Fromtheanalysisofclosures3.2.2a(ii),wefindthatAB,AD,BC,andCDarekeys.AllothersetseitherdonothaveABCDastheclosureorcontainoneofthesefoursets.

iii)Fromtheanalysisofclosures3.2.2a(iii),wefindthatA,B,CandDarekeys.AllothersetseitherdonothaveABCDastheclosureorcontainoneofthesefoursets.

Exercise3.2.2c

i)Thesuperkeysareallthosesetsthatcontainoneofthekeysin3.2.2b(i).ThesuperkeysareAB,AC,AD,ABC,ABD,ACD,BCDandABCD.

ii)Thesuperkeysareallthosesetsthatcontainoneofthekeysin3.2.2b(ii).ThesuperkeysareABC,ABD,ACD,BCDandABCD.

iii)Thesuperkeysareallthosesetsthatcontainoneofthekeysin3.2.2b(iii).ThesuperkeysareAB,AC,AD,BC,BD,CD,ABC,ABD,ACD,BCDandABCD.

Exercise3.2.3a

SinceA1A2…AnCcontainsA1A2…An,thentheclosureofA1A2…AnCcontainsB.ThusitfollowsthatA1A2…AnCB.

Exercise3.2.3b

From3.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.3d

FromA1A2…AnC1C2…Ck,weknowthattheclosurecontainsB1B2…BmbecauseoftheFDA1A2…AnB1B2…Bm.TheC1C2…CkalsotellusthattheclosureofA1A2…AnC1C2…CkcontainsD1D2…Dj.Thus,A1A2…AnC1C2…CkB1B2…BkD1D2…Dj.

Exercise3.2.4a

IfattributeArepresentedSocialSecurityNumberandBrepresentedaperson’sname,thenwewouldassumeABbutBAwouldnotbevalidbecausetheremaybemanypeoplewiththesamenameanddifferentSocialSecurityNumbers.

Exercise3.2.4b

LetattributeArepresentSocialSecurityNumber,BrepresentgenderandCrepresentname.SurelySocialSecurityNumberandgendercanuniquelyidentifyaperson’sname(i.e.ABC).ASocialSecurityNumbercanalsouniquelyidentifyaperson’sname(i.e.AC).However,genderdoesnotuniquelydetermineaname(i.e.BCisnotvalid).

Exercise3.2.4c

LetattributeArepresentlatitudeandBrepresentlongitude.Together,bothattributescanuniquelydetermineC,apointontheworldmap(i.e.ABC).However,neitherAnorBcanuniquelyidentifyapoint(i.e.ACandBCarenotvalid).

Exercise3.2.5

GivenarelationwithattributesA1A2…An,wearetoldthattherearenofunctionaldependenciesoftheformB1B2…Bn-1CwhereB1B2…Bn-1isn-1oftheattributesfromA1A2…AnandCistheremainingattributefromA1A2…An.Inthiscase,thesetB1B2…Bn-1andanysubsetdonotfunctionallydetermineC.ThustheonlyfunctionaldependenciesthatwecanmakeareoneswhereCisonboththeleftandrighthandsides.AllofthesefunctionaldependencieswouldbetrivialandthustherelationhasnonontrivialFD’s.

Exercise3.2.6

Let’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.7

ThealgorithmtofindX+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.8a

Ifallsetsofattributesareclosed,thentherecannotbeanynontrivialfunctionaldependencies.SupposeA1A2...AnBisanontrivialdependency.Then{A1A2...An}+containsBandthusA1A2...Anisnotclosed.

Exercise3.2.8b

Iftheonlyclosedsetsare?and{A,B,C,D},thenthefollowingFDshold:

AB AC AD

BA BC BD

CA CB CD

DA DB DC

ABC ABD

ACB ACD

ADB ADC

BCA BCD

BDA BDC

CDA CDB

ABCD

ABDC

ACDB

BCDA

Exercise3.2.8c

Iftheonlyclosedsetsare?,{A,B}and{A,B,C,D},thenthefollowingFDshold:

AB

BA

CA CB CD

DA DB DC

ACB ACD

ADB ADC

BCA BCD

BDA BDC

CDA CDB

ABCD

ABDC

ACDB

BCDA

Exercise3.2.9

WecanthinkofthisproblemasasituationwheretheattributesA,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.10a

Weneedtocomputetheclosuresofallsubsetsof{ABC},althoughthereisnoneedtothinkabouttheemptysetorthesetofallthreeattributes.Herearethecalculationsfortheremainingsixsets:

{A}+=A

{B}+=B

{C}+=ACE

{AB}+=ABCDE

{AC}+=ACE

{BC}+=ABCDE

WeignoreDandE,soabasisfortheresultingfunctionaldependenciesforABCis:CAandABC.NotethatBC->Aistrue,butfollowslogicallyfromC->A,andthereforemaybeomittedfromourlist.

Exercise3.2.10b

Weneedtocomputetheclosuresofallsubsetsof{ABC},althoughthereisnoneedtothinkabouttheemptysetorthesetofallthreeattributes.Herearethecalculationsfortheremainingsixsets:

{A}+=AD

{B}+=B

{C}+=C

{AB}+=ABDE

{AC}+=ABCDE

{BC}+=BC

WeignoreDandE,soabasisfortheresultingfunctionaldependenciesforABCis:ACB.

Exercise3.2.10c

Weneedtocomputetheclosuresofallsubsetsof{ABC},althoughthereisnoneedtothinkabouttheemptysetorthesetofallthreeattributes.Herearethecalculationsfortheremainingsixsets:

{A}+=A

{B}+=B

{C}+=C

{AB}+=ABD

{AC}+=ABCDE

{BC}+=ABCDE

WeignoreDandE,soabasisfortheresultingfunctionaldependenciesforABCis:ACBandBCA.

Exercise3.2.10d

Weneedtocomputetheclosuresofallsubsetsof{ABC},althoughthereisnoneedtothinkabouttheemptysetorthesetofallthreeattributes.Herearethecalculationsfortheremainingsixsets:

{A}+=ABCDE

{B}+=ABCDE

{C}+=ABCDE

{AB}+=ABCDE

{AC}+=ABCDE

{BC}+=ABCDE

WeignoreDandE,soabasisfortheresultingfunctionaldependenciesforABCis:AB,BCandCA.

Exercise3.2.11

ForsteponeofAlgorithm3.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.1a

InthesolutiontoExercise3.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.1b

Bycomputingtheclosuresofall15nonemptysubsetsofABCD,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.1d

InthesolutiontoExercise3.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.1e

Bycomputingtheclosuresofall31nonemptysubsetsofABCDE,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,wediscoverthatABCDisnotinBCNFsinceABisitsonlykeyandtheFDBDfollowsforABCD.UsingviolationBDtofurtherdecompose,wegetBDandABCasdecomposedrelations.BDisinBCNFbecauseitisatwo-attributerelation.UsingAlgorithm3.12again,wediscoverthatABCisinBCNFsinceABistheonlykeyandABCistheonlynontrivialFD.GoingbacktorelationABE,followingAlgorithm3.12tellsusthatABEisinBCNFbecausetherearenokeysandnonontrivialFDs.ThusthethreerelationsofthedecompositionareABC,BDandABE.

Exercise3.3.1f

Bycomputingtheclosuresofall31nonemptysubsetsofABCDE,wecanfindallthenontrivialFDs.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.FromtheclosureswecanalsodeducethatthekeysareAB,ACandAD.Thus,anydependencyabovethatdoesnotcontainoneoftheabovepairsontheleftisaBCNFviolation.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.2

Yes,wewillgetthesameresult.BothABandABChaveAontheleftsideandpartoftheprocessofdecompositioninvolvesfinding{A}+toformonedecomposedrelationandAplustherestoftheattributesnotin{A}+asthesecondrelation.Bothcasesyieldthesamedecomposedrelations.

Exercise3.3.3

Yes,wewillstillgetthesameresult.BothABandABChaveAontheleftsideandpartoftheprocessofdecompositioninvolvesfinding{A}+toformonedecomposedrelationandAplustherestoftheattributesnotin{A}+asthesecondrelation.Bothcasesyieldthesamedecomposedrelations.

Exercise3.3.4

ThisistakenfromExample3.21pg.95.

SupposethataninstanceofrelationRonlycontainstwotuples.

A

B

C

1

2

3

4

2

5

TheprojectionsofRontotherelationswithschemas{A,B}and{B,C}are:

A

B

1

2

4

2

B

C

2

3

2

5

Ifwedoanaturaljoinonthetwoprojections,wewillget:

A

B

C

1

2

3

1

2

5

4

2

3

4

2

5

TheresultofthenaturaljoinisnotequaltotheoriginalrelationR.

Exercise3.4.1a

Thisistheinitialtableau:

A

B

C

D

E

a

b

c

d1

e1

a1

b

c

d

e1

a

b1

c

d1

e

ThisisthefinaltableauafterapplyingFDsBEandCEA.

A

B

C

D

E

a

b

c

d1

e1

a

b

c

d

e1

a

b1

c

d1

e

Sincethereisnotanunsubscriptedrow,thedecompositionforRisnotlosslessforthissetofFDs.

WecanusethefinaltableauasaninstanceofRasanexampleforwhythejoinisnotlossless.Theprojectedrelationsare:

A

B

C

a

b

c

a

b1

c

B

C

D

b

c

d1

b

c

d

b1

c

d1

A

C

E

a

c

e1

a

c

e

Thejoinedrelationis:

A

B

C

D

E

a

b

c

d1

e1

a

b

c

d

e1

a

b1

c

d1

e1

a

b

c

d1

e

a

b

c

d

e

a

b1

c

d1

e

Thejoinedrelationhasthreemoretuplesthantheoriginaltableau.

Exercise3.4.1b

Thisistheinitialtableau:

A

B

C

D

E

a

b

c

d1

e1

a1

b

c

d

e1

a

b1

c

d1

e

ThisisthefinaltableauafterapplyingFDsACEandBCD

A

B

C

D

E

a

b

c

d

e

a1

b

c

d

e1

a

b1

c

d1

e

Sincethereisanunsubscriptedrow,thedecompositionforRislosslessforthissetofFDs.

Exercise3.4.1c

Thisistheinitialtableau:

A

B

C

D

E

a

b

c

d1

e1

a1

b

c

d

e1

a

b1

c

d1

e

ThisisthefinaltableauafterapplyingFDsAD,DEandBD.

A

B

C

D

E

a

b

c

d

e

a1

b

c

d

e

a

b1

c

d

e

Sincethereisanunsubscriptedrow,thedecompositionforRislosslessforthissetofFDs.

Exercise3.4.1d

Thisistheinitialtableau:

A

B

C

D

E

a

b

c

d1

e1

a1

b

c

d

e1

a

b1

c

d1

e

ThisisthefinaltableauafterapplyingFDsAD,CDEandED

A

B

C

D

E

a

b

c

d

e

a1

b

c

d

e

a

b1

c

d

e

Sincethereisanunsubscriptedrow,thedecompositionforRislosslessforthissetofFDs.

Exercise3.4.2

WhenwedecomposearelationintoBCNF,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.1a

InthesolutiontoExercise3.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.1b

InthesolutiontoExercise3.3.1bwefoundthatthereare8nontrivialdependencies.TheyareBC,BD,ABC,ABD,BCD,BDC,ABCDandABDC.

WealsofoundoutthattheonlykeyisAB.FDswheretheleftsideisnotasuperkeyortheattributesontherightarenotpartofsomekeyare3NFviolations.The3NFviolationsareBC,BD,BCDandBDC.

Usingalgorithm3.26,wecandecomposeintorelationsusingtheminimalbasisBCandBD.TheresultingdecomposedrelationswouldbeBCandBD.However,noneofthesetwosetsofattributesisasuperkey.ThusweaddrelationABtotheresult.ThefinalsetofdecomposedrelationsisBC,BDandAB.

Exercise3.5.1c

InthesolutiontoExercise3.3.1cwefoundthatthereare12nontrivialdependencies.TheyareABC,BCD,CDA,ADB,ABD,ADC,BCA,CDB,ABCD,ABDC,ACDBandBCDA.

WealsofoundoutthatthekeysareAB,AD,BC,andCD.SincealltheattributesontherightsidesoftheFDsareprime,thereareno3NFviolations.

Sincethereareno3NFviolations,itisnotnecessarytodecomposetherelation.

Exercise3.5.1d

InthesolutiontoExercise3.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.1e

InthesolutiontoExercise3.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.1f

InthesolutiontoExercise3.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,DBandDE.TheresultingdecomposedrelationswouldbeABC,CD,BDandDE.SincerelationABCcontainsakey,wecanstopwiththedecomposition.ThefinalsetofdecomposedrelationsisABC,CD,BDandDE.

Exercise3.5