Exercise5.1.1

Asaset:

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

Exercise5.1.2

Average=218

Asabag:

Average=215

Exercise5.1.3a

Asaset:

Asabag:

Exercise5.1.3b

7ibore(ShipstxlClasses)

Exercise5.1.4a

Forbags:

Ontheleft-handside:

GivenbagsRandSwhereatupletappearsnandmtimesrespectively,theunionofbags

RandSwillhavetupletappearn+mtimes.ThefurtherunionofbagTwiththetuplet

appearingotimeswillhavetupletappearn+m+otimesinthefinalresult.

Ontheright-handside:

GivenbagsSandTwhereatupletappearsmandotimesrespectively,theunionofbags

RandSwillhavetupletappearm+otimes.ThefurtherunionofbagRwiththetuplet

appearingntimeswillhavetupletappearm+o+ntimesinthefinalresult.

Forsets:

Thisisasimilarcasewhendealingwithbagsexceptthetupletcanonlyappearatmostoncein

eachset.Thetupletonlyappearsintheresultifallthesetshavethetuplet.Otherwise,thetuple

twillnotappearintheresult.Sincewecannothaveduplicates,theresultonlyhasatmostone

copyofthetuplet.

Exercise5.1.4b

Forbags:

Ontheleft-handside:

GivenbagsRandSwhereatupletappearsnandmtimesrespectively,theintersection

ofbagsRandSwillhavetupletappearmin(tt,m)times.Thefurtherintersectionofbag

Twiththetupletappearingotimeswillproducetupletmin(qmin(n.m))timesinthe

finalresult.

Ontheright-handside:

GivenbagsSandTwhereatupletappearsmandotimesrespectively,theintersectionof

bagsRandSwillhavetupletappearmin(m,o)times.ThefurtherintersectionofbagR

withthetupletappearingntimeswillproducetupletmin(",min(m,o))timesinthe

finalresult.

TheintersectionofbagsR,SandTwillyieldaresultwheretupletappearsmin（幾,m,o）times.

Forsets:

Thisisasimilarcasewhendealingwithbagsexceptthetupletcanonlyappearatmostoncein

eachset.Thetupletonlyappearsintheresultifallthesetshavethetuplet.Otherwise,thetuple

twillnotappearintheresult.

Exercise5.1.4c

Forbags:

Ontheleft-handside:

GiventhattuplerinR,whichappearsmtimes,cansuccessfullyjoinwithtuplesinS,

whichappearsntimes,weexpecttheresulttocontainmncopies.Alsogiventhattuplet

inT,whichappearsotimes,cansuccessfullyjoinwiththejoinedtuplesofrands,we

expectthefinalresulttohavemnocopies.

Ontheright-handside:

GiventhattuplesinS,whichappearsntimes,cansuccessfullyjoinwithtupletinT,

whichappearsotimes,weexpecttheresulttocontainnocopies.Alsogiventhattupler

inR,whichappearsmtimes,cansuccessfullyjoinwiththejoinedtuplesofsandZ,we

expectthefinalresulttohavenomcopies.

Theorderinwhichweperformthenaturaljoindoesnotmatterforbags.

Forsets:

Thisisasimilarcasewhendealingwithbagsexceptthejoinedtuplescanonlyappearatmost

onceineachresult.IftherearetuplesinrelationsR,S,Tthatcansuccessfullyjoin,thenthe

resultwillcontainatuplewiththeschemaoftheirjoinedattributes.

Exercise5.1.4d

Forbags:

SupposeatupletoccursnandmtimesinbagsRandSrespectively.Intheunionofthesetwo

bagsRuS,tupletwouldappearn+mtimes.Likewise,intheunionofthesetwobagsSuR,

tupletwouldappearm+ntimes.Bothsidesoftherelationyieldthesameresult.

Forsets:

Atupletcanonlyappearatmostonetime.TupletmightappeareachinsetsRandSoneorzero

times.ThecombinationsofnumberofoccurrencesfortuplezinRandSrespectivelyare(0,0),

(0,1),(1,0),and(1,1).OnlywhentupletappearsinbothsetsRandSwilltheunionRuShave

thetuplet.ThesamereasoningholdswhenwetaketheunionSuR.

Thereforethecommutativelawforunionholds.

Exercise5.1.4e

Forbags:

SupposeatupletoccursnandmtimesinbagsRandSrespectively.Intheintersectionofthese

twobagsRAS,tupletwouldappearmin()times.Likewiseintheintersectionofthesetwo

bagsSClR,tupletwouldappearmin(m.n)times.Bothsidesoftherelationyieldthesame

result.

Forsets:

Atupletcanonlyappearatmostonetime.TupletmightappeareachinsetsRandSoneorzero

times.Thecombinationsofnumberofoccurrencesfortuple/inRandSrespectivelyare(0,0),

(0,1),(1,0),and(1,1).OnlywhentupletappearsinatleastoneofthesetsRandSwillthe

intersectionRAShavethetuplet.ThesamereasoningholdswhenwetaketheintersectionSA

R.

Thereforethecommutativelawforintersectionholds.

Exercise5.1.4f

Forbags:

SupposeatupletoccursntimesinbagRandtupleuoccursmtimesinbagS.Supposealsothat

thetwotuplest.ucansuccessfullyjoin.TheninthenaturaljoinofthesetwobagsRtxlS,the

joinedtuplewouldappearnmtimes.LikewiseinthenaturaljoinofthesetwobagsStxlR,the

joinedtuplewouldappearmntimes.Bothsidesoftherelationyieldthesameresult.

Forsets:

Anarbitrarytupletcanonlyappearatmostonetimeinanyset.Tuplesw,vmightappear

respectivelyinsetsRandSoneorzerotimes.Thecombinationsofnumberofoccurrencesfor

tuplesu,vinRandSrespectivelyare(0,0),(0,1),(1,0),and(1,1).OnlywhentupleuexistsinR

andtuplevexistsinSwillthenaturaljoinRbdShavethejoinedtuple.Thesamereasoning

holdswhenwetakethenaturaljoinSMR.

Thereforethecommutativelawfornaturaljoinholds.

Exercise5.1.4g

Forbags:

SupposetupletappearsmtimesinRandntimesinS.IfwetaketheunionofRandSfirst,we

willgetarelationwheretupletappearsm+ntimes.TakingtheprojectionofalistofattributesL

willyieldaresultingrelationwheretheprojectedattributesfromtupletappearm+ntimes.If

wetaketheprojectionoftheattributesinlistLfirst,thentheprojectedattributesfromtuplet

wouldappearmtimesfromRandntimesfromS.Theunionoftheseresultingrelationswould

havetheprojectedattributesoftupletappearm+ntimes.

Forsets:

Anarbitrarytupletcanonlyappearatmostonetimeinanyset.TupletmightappearinsetsR

andSoneorzerotimes.ThecombinationsofnumberofoccurrencesfortuplerinRandS

respectivelyare(0,0),(0,1),(1,0),and(1,1).OnlywhentupletexistsinRorS(orbothRandS)

willtheprojectedattributesoftupletappearintheresult.

Thereforethelawholds.

Exercise5.1.4h

Forbags:

SupposetupletappearsutimesinR,vtimesinSandwtimesinT.Onthelefthandside,the

intersectionofSandTwouldproducearesultwheretupletwouldappearmin(v,卬)times.With

theadditionoftheunionofR,theoverallresultwouldhaveu+min(v,w)copiesoftuplet.On

therighthandside,wewouldgetaresultofmin(w+也〃+vv)copiesoftuplet.Theexpressions

onboththeleftandrightsidesareequivalent.

Forsets:

Anarbitrarytupletcanonlyappearatmostonetimeinanyset.TupletmightappearinsetsR,S

andToneorzerotimes.ThecombinationsofnumberofoccurrencesfortupleZinR,SandT

respectivelyare(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).Onlywhen

tupletappearsinRorinbothSandTwilltheresulthavetuplet.

Thereforethedistributivelawofunionoverintersectionholds.

Exercise5.1.4i

SupposethatinrelationR,utuplessatisfyconditionCandvtuplessatisfyconditionD.Suppose

alsothatwtuplessatisfybothconditionsCandDwherew<min(v,vv).Thenthelefthandside

willreturnthosewtuples.Ontherighthandside,QC(R)producesutuplesandQD(R)producesv

tuples.However,weknowtheintersectionwillproducethesamewtuplesintheresult.

Whenconsideringbagsandsets,theonlydifferenceisbagsallowduplicatetupleswhilesets

onlyallowonecopyofthetuple.Theexampleaboveappliestobothcases.

Thereforethelawholds.

Exercise5.1.5a

Forsets,anarbitrarytupletappearsonthelefthandsideifitappearsinbothR,SandnotinT.

Thesameistruefortherighthandside.

Asanexampleforbags,supposethattupletappearsonetimeeachinbothR,Tandtwotimesin

S.Theresultofthelefthandsidewouldhavezerocopiesoftupletwhiletherighthandside

wouldhaveonecopyoftuplet.

Thereforethelawholdsforsetsbutnotforbags.

Exercise5.1.5b

Forsets,anarbitrarytupletappearsonthelefthandsideifitappearsinRandeitherSorT.This

isequivalenttosayingtupletonlyappearswhenitisinatleastRandSorinRandT.The

equivalenceisexactlytherightside'sexpression.

Asanexampleforbags,supposethattupletappearsonetimeinRandtwotimeseachinSandT.

Thenthelefthandsidewouldhaveonecopyoftupletintheresultwhiletherighthandside

wouldhavetwocopiesoftuplet.

Thereforethelawholdsforsetsbutnotforbags.

Exercise5.1.5c

Forsets,anarbitrarytupletappearsonthelefthandsideifitsatisfiesconditionC,conditionD

orbothconditionCandD.Ontherighthandside,oc(R)selectsthosetuplesthatsatisfy

conditionCwhileOD(R)selectsthosetuplesthatsatisfyconditionD.However,theunion

operatorwilleliminateduplicatetuples,namelythosetuplesthatsatisfybothconditionCandD.

Thusweareensuredthatbothsidesareequivalent.

Asanexampleforbags,weonlyneedtolookattheunionoperator.Ifthereareindeedtuples

thatsatisfybothconditionsCandD,thentherighthandsidewillcontainduplicatecopiesof

thosetuples.Thelefthandside,however,willonlyhaveonecopyforeachtupleoftheoriginal

setoftuples.

Exercise5.2.1a

A+BA2B2

101

549

101

6416

7916

Exercise5.2.1b

B+lC-l

10

Exercise5.2.1c

AB

01

01

23

24

34

Exercise5.2.1d

BC

01

02

24

25

34

34

Exercise5.2.1e

pH

Exercise5.2.1f

BC

01

24

25

34

02

Exercise5.2.1g

ASUM(B)

02

27

34

Exercise5.2.1h

BAVG(C)

01.5

24.5

34

Exercise5.2.1i

Exercise5.2.1j

AMAX(C)

24

Exercise5.2.1k

ABc

234

234

01

01

24_L

34

Exercise5.2.11

ABc

234

234

JL01

_L24

JL25

±02

Exercise5.2.1m

ABc

234

234

01±

01_L

24

34_L

_L01

24

25

_L02

Exercise5.2.1n

AR.BS.Bc

0124

0125

0134

0134

0124

0125

0134

0134

23±±

24±±

34±

J_01

_L-L02

Exercise5.2.2a

Applyingthe8operatoronarelationwithnoduplicateswillyieldthesamerelation.Thus8is

idempotent.

Exercise5.2.2b

TheresultofTCLisarelationoverthelistofattributesL.Performingtheprojectionagainwill

returnthesamerelationbecausetherelationonlycontainsthelistofattributesL.ThusTILis

idempotent.

Exercise5.2.2c

TheresultofocisarelationwhereconditionCissatisfiedbyeverytuple.Performingthe

selectionagainwillreturnthesamerelationbecausetherelationonlycontainstuplesthatsatisfy

theconditionC.Thusocisidempotent.

Exercise5.2.2d

TheresultofYLisarelationwhoseschemaconsistsofthegroupingattributesandtheaggregated

attributes.Ifweperformthesamegroupingoperation,thereisnoguaranteethattheexpression

wouldmakesense.Thegroupingattributeswillstillappearinthenewresult.However,the

aggregatedattributesmayormaynotappearcorrectly.Iftheaggregatedattributeisgivena

differentnamethantheoriginalattribute,thenperformingYLwouldnotmakesensebecauseit

containsanaggregationforanattributenamethatdoesnotexist.Inthiscase,theresulting

relationwould,accordingtothedefinition,onlycontainthegroupingattributes.Thus,YLisnot

idempotent.

Exercise5.2.2e

TheresultofTisasortedlistoftuplesbasedonsomeattributesL.IfLisnottheentireschema

ofrelationR,thenthereareattributesthatarenotsortedon.IfinrelationRtherearetwotuples

thatagreeinallattributesLanddisagreeinsomeoftheremainingattributesnotinL,thenitis

arbitraryastowhichorderthesetwotuplesappearintheresult.Thus,performingtheoperationT

multipletimescanyieldadifferentrelationwherethesetwotuplesareswapped.Thus,Tisnot

idempotent.

Exercise5.2.3

Ifweonlyconsidersets,thenitispossible.WecantakeKA(R)anddoaproductwithitself.From

thisproduct,wetakethetupleswherethetwocolumnsareequaltoeachother.

Ifweconsiderbagsaswell,thenitisnotpossible.Takethecasewherewehavethetwotuples

(1,0)and(1,0).Wewishtoproducearelationthatcontainstuples(1,1)and(1,1).Ifweusethe

classicaloperationsofrelationalalgebra,wecaneithergetaresultwheretherearenotuplesor

fourcopiesofthetuple(1,1).Itisnotpossibletogetthedesiredrelationbecausenooperation

candistinguishbetweentheoriginaltuplesandtheduplicatedtuples.Thusitisnotpossibleto

gettherelationwiththetwotuples(1,1)and(1,1).

Exercise5.3.1

a)Answer(model)<—PC(model,speed,ANDspeed>3.00

b)Answer(maker)<—Laptop(model,_,_,hd,_,_)ANDProduct(maker,model,_)ANDhd>

100

c)Answer(model,price)<—PC(model,price)ANDProduct(maker,model,_)AND

maker='B'

Answer(model,price)<—Laptop(model,price)ANDProduct(maker,model,_)

ANDmaker=,B,

Answer(model,price)<—Printer(model,_,_,price)ANDProduct(maker,model,_)AND

maker='B'

d)Answer(model)<—Printer(inodel,color,type,_)ANDcolor=,true,ANDtype='laser'

e)PCMaker(maker)<—Product(maker,_,type)ANDtype=,pc,

LaptopMaker(maker)<—Product(maker,type)ANDtype=,laptop,

Answer(maker)<—LaptopMaker(maker)ANDNOTPCMaker(maker)

f)Answer(hd)PC(modell,_,_,hd,_)ANDPC(model2,_,_,hd,_)ANDmodel1<>

model2

g)Answer(model1,model2)<—PC(model1,speed,ram,_,_)AND

PC(model2,_speed,ram,_,_)ANDmodel1<mode!2

h)FastComputer(model)<—PC(model,speed,ANDspeed>2.80

FastComputer(model)<—Laptop(model,speed,ANDspeed>2.80

Answer(maker)<—Product(maker,model1,_)ANDProduct(maker,model2,_)AND

FastComputer(model1)ANDFastComputer(model2)ANDmodel1<>model2

i)Computers(model,speed)—PC(model,speed,

Computers(model,speed)<—Laptop(model,speed,

SlowComputers(model)—Coinputers(model,speed)ANDComputers(model1,speed1)

ANDspeed<speed1

FastestComputers(model)<—Computers(model,_)ANDNOTSlowComputers(model)

Answer(maker)<—FastestComputers(model)ANDProduct(maker,model,_)

j)PCs(maker,speed)<—PC(model,speed,ANDProduct(maker,model,_)

Answer(maker)<—PCs(maker,speed)ANDPCs(maker,speed1)ANDPCs(maker,speed2)

ANDspeed<>speed1ANDspeed<>speed2ANDspeed1<>speed2

k)PCs(maker,model)<—Product(maker,model,type)ANDtype—pc，

Answer(maker)<—PCs(maker,model)ANDPCs(maker,model1)AND

PCs(maker,model2)ANDPCs(maker,model3)ANDmodel<>model1ANDmodel<>

model2ANDmodel1<>mode12AND(mode13=modelORmodel3=model1OR

model3=model2)

Exercise5.3.2

a)Answer(class,country)Classes(class,_,countrybore,_)ANDbore>16

b)Answer(name)<—Ships(name,_,launched)ANDlaunched<1921

c)Answer(ship)<—Outcomes(ship,battle,result)ANDbattle=,DenmarkStrait9ANDresult

=’sunk'

d)Answer(name)<—Classes(class,_,displacement)ANDShips(name,class,launched)

ANDdisplacement>35000ANDlaunched>1921

e)Answer(name,displacement,numGuns)<—Classes(class,_,_,numGuns,_,displacement)

ANDShips(name,class,_)ANDOutcomes(ship,battle,_)ANDbattle=,Guadalcanal9

ANDship=name

f)Answer(name)<—Ships(name,_,_)

Answer(name)<—Outcomes(name,_,_)ANDNOTAnswer(name)

g)MoreThanOne(class)<—Ships(name,class,_)ANDShips(namel,class,_)ANDname<>

namel

Answer(class)<—Classes(class,_2_2_2_2_)ANDNOTMoreThanOne(class)

h)Battleship(country)<—Classes(_,type,countryANDtype=,bb,

Battlecruiser(country)<—Classes(_,type,country,ANDtype='bc，

Answer(country)<—Battleship(country)ANDBattlecruiser(country)

i)Results(ship,result,date)<—Battles(name,date)ANDOutcomes(ship,battle,result)AND

battle=name

Answer(ship)<—Results(ship,result,date)ANDResults(ship,_,date1)AND

result=,damaged9ANDdate<datel

Exercise5.3.3

Answer(x,y)<—R(x,y)ANDz=z

Exercise5.4.1a

Answer(a,b,c)<—R(a,b,c)

Answer(a,b,c)<—S(a,b,c)

Exercise5.4.1b

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.Id

Union(a,b,c)<—R(a,b,c)

Union(a,b,c)<—S(a,b,c)

Answer(a,b,c)<—Union(a,b,c)ANDNOTT(a,b,c)

Exercise5.4.Ie

J(a,b,c)-R(a,b,c)ANDNOTS(a,b,c)

K(a,b,c)-