数据库系统基础教程第五章答案

Asaset:

speed

2.66

2.10

1.42

2.80

3.20

2.20

2.00

1.86

3.06

Average=2.37

Asabag:

speed

2.66

2.10

1.42

2.80

3.20

3.20

2.20

2.20

2.00

2.80

1.86

2.80

3.06

Average=2.48

Asaset:

hd

250

80

320

200

300

160

Average=218

Asabag:

hd

250

250

80

250

250

320

200

250

250

300

160

160

80

Average=215

Asaset:

bore

15

16

14

18

Asabag:

bore

15

16

14

16

15

15

14

18

πbore(ShipsClasses)

Forbags:

Ontheleft-handside:

GivenbagsRandSwhereatupletappearsnandmtimesrespectively,theunionofbagsRandSwillhavetupletappearn+mtimes.ThefurtherunionofbagTwiththetupletappearingotimeswillhavetupletappearn+m+otimesinthefinalresult.

Ontheright-handside:

GivenbagsSandTwhereatupletappearsmandotimesrespectively,theunionofbagsRandSwillhavetupletappearm+otimes.ThefurtherunionofbagRwiththetupletappearingntimeswillhavetupletappearm+o+ntimesinthefinalresult.

Forsets:

Thisisasimilarcasewhendealingwithbagsexceptthetupletcanonlyappearatmostonceineachset.Thetupletonlyappearsintheresultifallthesetshavethetuplet.Otherwise,thetupletwillnotappearintheresult.Sincewecannothaveduplicates,theresultonlyhasatmostonecopyofthetuplet.

Forbags:

Ontheleft-handside:

GivenbagsRandSwhereatupletappearsnandmtimesrespectively,theintersectionofbagsRandSwillhavetupletappearmin(n,m)times.ThefurtherintersectionofbagTwiththetupletappearingotimeswillproducetupletmin(o,min(n,m))timesinthefinalresult.

Ontheright-handside:

GivenbagsSandTwhereatupletappearsmandotimesrespectively,theintersectionofbagsRandSwillhavetupletappearmin(m,o)times.ThefurtherintersectionofbagRwiththetupletappearingntimeswillproducetupletmin(n,min(m,o))timesinthefinalresult.

TheintersectionofbagsR,SandTwillyieldaresultwheretupletappearsmin(n,m,o)times.

Forsets:

Thisisasimilarcasewhendealingwithbagsexceptthetupletcanonlyappearatmostonceineachset.Thetupletonlyappearsintheresultifallthesetshavethetuplet.Otherwise,thetupletwillnotappearintheresult.

Forbags:

Ontheleft-handside:

GiventhattuplerinR,whichappearsmtimes,cansuccessfullyjoinwithtuplesinS,whichappearsntimes,weexpecttheresulttocontainmncopies.AlsogiventhattupletinT,whichappearsotimes,cansuccessfullyjoinwiththejoinedtuplesofrands,weexpectthefinalresulttohavemnocopies.

Ontheright-handside:

GiventhattuplesinS,whichappearsntimes,cansuccessfullyjoinwithtupletinT,whichappearsotimes,weexpecttheresulttocontainnocopies.AlsogiventhattuplerinR,whichappearsmtimes,cansuccessfullyjoinwiththejoinedtuplesofsandt,weexpectthefinalresulttohavenomcopies.

Theorderinwhichweperformthenaturaljoindoesnotmatterforbags.

Forsets:

Thisisasimilarcasewhendealingwithbagsexceptthejoinedtuplescanonlyappearatmostonceineachresult.Iftherearetuplesr,s,tinrelationsR,S,Tthatcansuccessfullyjoin,thentheresultwillcontainatuplewiththeschemaoftheirjoinedattributes.

Forbags:

SupposeatupletoccursnandmtimesinbagsRandSrespectively.IntheunionofthesetwobagsRS,tupletwouldappearn+mtimes.Likewise,intheunionofthesetwobagsSR,tupletwouldappearm+ntimes.Bothsidesoftherelationyieldthesameresult.

Forsets:

Atupletcanonlyappearatmostonetime.TupletmightappeareachinsetsRandSoneorzerotimes.ThecombinationsofnumberofoccurrencesfortupletinRandSrespectivelyare(0,0),(0,1),(1,0),and(1,1).OnlywhentupletappearsinbothsetsRandSwilltheunionRShavethetuplet.ThesamereasoningholdswhenwetaketheunionSR.

Thereforethecommutativelawforunionholds.

Forbags:

SupposeatupletoccursnandmtimesinbagsRandSrespectively.IntheintersectionofthesetwobagsR∩S,tupletwouldappearmin(n,m)times.LikewiseintheintersectionofthesetwobagsS∩R,tupletwouldappearmin(m,n)times.Bothsidesoftherelationyieldthesameresult.

Forsets:

Atupletcanonlyappearatmostonetime.TupletmightappeareachinsetsRandSoneorzerotimes.ThecombinationsofnumberofoccurrencesfortupletinRandSrespectivelyare(0,0),(0,1),(1,0),and(1,1).OnlywhentupletappearsinatleastoneofthesetsRandSwilltheintersectionR∩Shavethetuplet.ThesamereasoningholdswhenwetaketheintersectionS∩R.

Thereforethecommutativelawforintersectionholds.

Forbags:

SupposeatupletoccursntimesinbagRandtupleuoccursmtimesinbagS.Supposealsothatthetwotuplest,ucansuccessfullyjoin.TheninthenaturaljoinofthesetwobagsRS,thejoinedtuplewouldappearnmtimes.LikewiseinthenaturaljoinofthesetwobagsSR,thejoinedtuplewouldappearmntimes.Bothsidesoftherelationyieldthesameresult.

Forsets:

Anarbitrarytupletcanonlyappearatmostonetimeinanyset.Tuplesu,vmightappearrespectivelyinsetsRandSoneorzerotimes.Thecombinationsofnumberofoccurrencesfortuplesu,vinRandSrespectivelyare(0,0),(0,1),(1,0),and(1,1).OnlywhentupleuexistsinRandtuplevexistsinSwillthenaturaljoinRShavethejoinedtuple.ThesamereasoningholdswhenwetakethenaturaljoinSR.

Thereforethecommutativelawfornaturaljoinholds.

Forbags:

SupposetupletappearsmtimesinRandntimesinS.IfwetaketheunionofRandSfirst,wewillgetarelationwheretupletappearsm+ntimes.TakingtheprojectionofalistofattributesLwillyieldaresultingrelationwheretheprojectedattributesfromtupletappearm+ntimes.IfwetaketheprojectionoftheattributesinlistLfirst,thentheprojectedattributesfromtupletwouldappearmtimesfromRandntimesfromS.Theunionoftheseresultingrelationswouldhavetheprojectedattributesoftupletappearm+ntimes.

Forsets:

Anarbitrarytupletcanonlyappearatmostonetimeinanyset.TupletmightappearinsetsRandSoneorzerotimes.ThecombinationsofnumberofoccurrencesfortupletinRandSrespectivelyare(0,0),(0,1),(1,0),and(1,1).OnlywhentupletexistsinRorS(orbothRandS)willtheprojectedattributesoftupletappearintheresult.

Thereforethelawholds.

Forbags:

SupposetupletappearsutimesinR,vtimesinSandwtimesinT.Onthelefthandside,theintersectionofSandTwouldproducearesultwheretupletwouldappearmin(v,w)times.WiththeadditionoftheunionofR,theoverallresultwouldhaveu+min(v,w)copiesoftuplet.Ontherighthandside,wewouldgetaresultofmin(u+v,u+w)copiesoftuplet.Theexpressionsonboththeleftandrightsidesareequivalent.

Forsets:

Anarbitrarytupletcanonlyappearatmostonetimeinanyset.TupletmightappearinsetsR,SandToneorzerotimes.ThecombinationsofnumberofoccurrencesfortupletinR,SandTrespectivelyare(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0)and(1,1,1).OnlywhentupletappearsinRorinbothSandTwilltheresulthavetuplet.

Thereforethedistributivelawofunionoverintersectionholds.

SupposethatinrelationR,utuplessatisfyconditionCandvtuplessatisfyconditionD.SupposealsothatwtuplessatisfybothconditionsCandDwherew≤min(v,w).Thenthelefthandsidewillreturnthosewtuples.Ontherighthandside,σC(R)producesutuplesandσD(R)producesvtuples.However,weknowtheintersectionwillproducethesamewtuplesintheresult.

Whenconsideringbagsandsets,theonlydifferenceisbagsallowduplicatetupleswhilesetsonlyallowonecopyofthetuple.Theexampleaboveappliestobothcases.

Thereforethelawholds.

Forsets,anarbitrarytupletappearsonthelefthandsideifitappearsinbothR,SandnotinT.Thesameistruefortherighthandside.

Asanexampleforbags,supposethattupletappearsonetimeeachinbothR,TandtwotimesinS.Theresultofthelefthandsidewouldhavezerocopiesoftupletwhiletherighthandsidewouldhaveonecopyoftuplet.

Thereforethelawholdsforsetsbutnotforbags.

Forsets,anarbitrarytupletappearsonthelefthandsideifitappearsinRandeitherSorT.ThisisequivalenttosayingtupletonlyappearswhenitisinatleastRandSorinRandT.Theequivalenceisexactlytherightside’sexpression.

Asanexampleforbags,supposethattupletappearsonetimeinRandtwotimeseachinSandT.Thenthelefthandsidewouldhaveonecopyoftupletintheresultwhiletherighthandsidewouldhavetwocopiesoftuplet.

Thereforethelawholdsforsetsbutnotforbags.

Forsets,anarbitrarytupletappearsonthelefthandsideifitsatisfiesconditionC,conditionDorbothconditionCandD.Ontherighthandside,σC(R)selectsthosetuplesthatsatisfyconditionCwhileσD(R)selectsthosetuplesthatsatisfyconditionD.However,theunionoperatorwilleliminateduplicatetuples,namelythosetuplesthatsatisfybothconditionCandD.Thusweareensuredthatbothsidesareequivalent.

Asanexampleforbags,weonlyneedtolookattheunionoperator.IfthereareindeedtuplesthatsatisfybothconditionsCandD,thentherighthandsidewillcontainduplicatecopiesofthosetuples.Thelefthandside,however,willonlyhaveonecopyforeachtupleoftheoriginalsetoftuples.

A+B

A2

B2

1

0

1

5

4

9

1

0

1

6

4

16

7

9

16

B+1

C-1

1

0

3

3

3

4

4

3

1

1

4

3

A

B

0

1

0

1

2

3

2

4

3

4

B

C

0

1

0

2

2

4

2

5

3

4

3

4

A

B

0

1

2

3

2

4

3

4

B

C

0

1

2

4

2

5

3

4

0

2

A

SUM(B)

0

2

2

7

3

4

B

AVG(C)

0

1.5

2

4.5

3

4

A

0

2

3

A

MAX(C)

2

4

A

B

C

2

3

4

2

3

4

0

1

┴

0

1

┴

2

4

┴

3

4

┴

A

B

C

2

3

4

2

3

4

┴

0

1

┴

2

4

┴

2

5

┴

0

2

A

B

C

2

3

4

2

3

4

0

1

┴

0

1

┴

2

4

┴

3

4

┴

┴

0

1

┴

2

4

┴

2

5

┴

0

2

A

R.B

S.B

C

0

1

2

4

0

1

2

5

0

1

3

4

0

1

3

4

0

1

2

4

0

1

2

5

0

1

3

4

0

1

3

4

2

3

┴

┴

2

4

┴

┴

3

4

┴

┴

┴

┴

0

1

┴

┴

0

2

Applyingtheδoperatoronarelationwithnoduplicateswillyieldthesamerelation.Thusδisidempotent.

TheresultofπLisarelationoverthelistofattributesL.PerformingtheprojectionagainwillreturnthesamerelationbecausetherelationonlycontainsthelistofattributesL.ThusπLisidempotent.

TheresultofσCisarelationwhereconditionCissatisfiedbyeverytuple.PerformingtheselectionagainwillreturnthesamerelationbecausetherelationonlycontainstuplesthatsatisfytheconditionC.ThusσCisidempotent.

TheresultofγLisarelationwhoseschemaconsistsofthegroupingattributesandtheaggregatedattributes.Ifweperformthesamegroupingoperation,thereisnoguaranteethattheexpressionwouldmakesense.Thegroupingattributeswillstillappearinthenewresult.However,theaggregatedattributesmayormaynotappearcorrectly.Iftheaggregatedattributeisgivenadifferentnamethantheoriginalattribute,thenperformingγLwouldnotmakesensebecauseitcontainsanaggregationforanattributenamethatdoesnotexist.Inthiscase,theresultingrelationwould,accordingtothedefinition,onlycontainthegroupingattributes.Thus,γLisnotidempotent.

TheresultofτisasortedlistoftuplesbasedonsomeattributesL.IfLisnottheentireschemaofrelationR,thenthereareattributesthatarenotsortedon.IfinrelationRtherearetwotuplesthatagreeinallattributesLanddisagreeinsomeoftheremainingattributesnotinL,thenitisarbitraryastowhichorderthesetwotuplesappearintheresult.Thus,performingtheoperationτmultipletimescanyieldadifferentrelationwherethesetwotuplesareswapped.Thus,τisnotidempotent.

Ifweonlyconsidersets,thenitispossible.WecantakeπA(R)anddoaproductwithitself.Fromthisproduct,wetakethetupleswherethetwocolumnsareequaltoeachother.

Ifweconsiderbagsaswell,thenitisnotpossible.Takethecasewherewehavethetwotuples(1,0)and(1,0).Wewishtoproducearelationthatcontainstuples(1,1)and(1,1).Ifweusetheclassicaloperationsofrelationalalgebra,wecaneithergetaresultwheretherearenotuplesorfourcopiesofthetuple(1,1).Itisnotpossibletogetthedesiredrelationbecausenooperationcandistinguishbetweentheoriginaltuplesandtheduplicatedtuples.Thusitisnotpossibletogettherelationwiththetwotuples(1,1)and(1,1).

Answer(model)←PC(model,speed,_,_,_)ANDspeed≥3.00

Answer(maker)←Laptop(model,_,_,hd,_,_)ANDProduct(maker,model,_)ANDhd≥100

Answer(model,price)←PC(model,_,_,_,price)ANDProduct(maker,model,_)ANDmaker=’B’

Answer(model,price)←Laptop(model,_,_,_,_,price)ANDProduct(maker,model,_)ANDmaker=’B’

Answer(model,price)←Printer(model,_,_,price)ANDProduct(maker,model,_)ANDmaker=’B’

Answer(model)←Printer(model,color,type,_)ANDcolor=’true’ANDtype=’laser’

PCMaker(maker)←Product(maker,_,type)ANDtype=’pc’

LaptopMaker(maker)←Product(maker,_,type)ANDtype=’laptop’

Answer(maker)←LaptopMaker(maker)ANDNOTPCMaker(maker)

Answer(hd)←PC(model1,_,_,hd,_)ANDPC(model2,_,_,hd,_)ANDmodel1<>model2

Answer(model1,model2)←PC(model1,speed,ram,_,_)ANDPC(model2,_speed,ram,_,_)ANDmodel1<model2

FastComputer(model)←PC(model,speed,_,_,_)ANDspeed≥2.80

FastComputer(model)←Laptop(model,speed,_,_,_,_)ANDspeed≥2.80

Answer(maker)←Product(maker,model1,_)ANDProduct(maker,model2,_)ANDFastComputer(model1)ANDFastComputer(model2)ANDmodel1<>model2

Computers(model,speed)←PC(model,speed,_,_,_)

Computers(model,speed)←Laptop(model,speed,_,_,_,_)

SlowComputers(model)←Computers(model,speed)ANDComputers(model1,speed1)ANDspeed<speed1

FastestComputers(model)←Computers(model,_)ANDNOTSlowComputers(model)

Answer(maker)←FastestComputers(model)ANDProduct(maker,model,_)

PCs(maker,speed)←PC(model,speed,_,_,_)ANDProduct(maker,model,_)

Answer(maker)←PCs(maker,speed)ANDPCs(maker,speed1)ANDPCs(maker,speed2)ANDspeed<>speed1ANDspeed<>speed2ANDspeed1<>speed2

PCs(maker,model)←Product(maker,model,type)ANDtype=’pc’

Answer(maker)←PCs(maker,model)ANDPCs(maker,model1)ANDPCs(maker,model2)ANDPCs(maker,model3)ANDmodel<>model1ANDmodel<>model2ANDmodel1<>model2AND(model3=modelORmodel3=model1ORmodel3=model2)

Answer(class,country)←Classes(class,_,country,_,bore,_)ANDbore≥16

Answer(name)←Ships(name,_,launched)ANDlaunched<1921

Answer(ship)←Outcomes(ship,battle,result)ANDbattle=’DenmarkStrait’ANDresult=‘sunk’

Answer(name)←Classes(class,_,_,_,_,displacement)ANDShips(name,class,launched)ANDdisplacement>35000ANDlaunched>1921

Answer(name,displacement,numGuns)←Classes(class,_,_,numGuns,_,displacement)ANDShips(name,class,_)ANDOutcomes(ship,battle,_)ANDbattle=’Guadalcanal’ANDship=name

Answer(name)←Ships(name,_,_)

Answer(name)←Outcomes(name,_,_)ANDNOTAnswer(name)

MoreThanOne(class)←Ships(name,class,_)ANDShips(name1,class,_)ANDname<>name1

Answer(class)←Classes(class,_,_,_,_,_)ANDNOTMoreThanOne(class)

Battleship(country)←Classes(_,type,country,_,_,_)ANDtype=’bb’

Battlecruiser(country)←Classes(_,type,country,_,_,_)ANDtype=’bc’

Answer(country)←Battleship(country)ANDBattlecruiser(country)

Results(ship,result,date)←Battles(name,date)ANDOutcomes(ship,battle,result)ANDbattle=name

Answer(ship)←Results(ship,result,date)ANDResults(ship,_,date1)ANDresult=’damaged’ANDdate<date1

Answer(x,y)←R(x,y)ANDz=z

Answer(a,b,c)←R(a,b,c)

Answer(a,b,c)←S(a,b,c)

Answer(a,b,c)←R(a,b,c)ANDS(a,b,c)

Exercise5.4.1c

Answer(a,b,c)←R(a,b,c)ANDNOTS(a,b,c)

Exercise5.4.1d

Union(a,b,c)←R(a,b,c)

Union(