DatabaseSystems:TheCompleteBook

SolutionsforChapter2

SolutionsforSection2.1

Exercise2.1.1

TheE/RDiagram.

Exercise2.1.8(a)

TheE/RDiagram

SolutionsforSection2.2

Exercise2.2.1

TheAddressesentitysetisnothingbutasingleaddress,sowewouldprefertomakeaddressan

attributeofCustomers.Werethebanktorecordseveraladdressesforacustomer,thenitmight

makesensetohaveanAddressesentitysetandmakeLives-atamany-manyrelationship.

TheAcct-Setsentitysetisuseless.Eachcustomerhasauniqueaccountsetcontaininghisorher

accounts.However,relatingcustomersdirectlytotheiraccountsinamany-manyrelationship

conveysthesameinformationandeliminatestheaccount-setconceptaltogether.

SolutionsforSection2.3

Exercise2.3.1(a)

KeysssNoandnumberareappropriateforCustomersandAccounts,respectively.Also,wethink

itdoesnotmakesenseforanaccounttoberelatedtozerocustomers,soweshouldroundtheedge

connectingOwnstoCustomers.Itdoesnotseeminappropriatetohaveacustomerwith0accounts;

theymightbeaborrower,forexample,soweputnoconstraintontheconnectionfromOwnsto

Accounts.HereistheTheE/RDiagram,

showingunderlinedkeysand

thenumerocityconstraint.

Exercise2.3.2(b)

IfRismany-onefromEltoE2,thentwotuples(el,e2)and(fl,⑵oftherelationshipsetforR

mustbethesameiftheyagreeonthekeyattributesforEl.Toseewhy,surelyelandflarethe

same.BecauseRismany-onefromEltoE2,e2andf2mustalsobethesame.Thus,thepairsare

thesame.

SolutionsforSection2.4

Exercise2.4.1

HereistheTheE/RDiagram.

WehaveomittedattributesotherthanourchoiceforthekeyattributesofStudentsandCourses.

Alsoomittedarenamesfortherelationships.AttributegradeisnotpartofthekeyforEnrollments.

ThekeyforEnrollementsisstudIDfromStudentsanddeptandnumberfromCourses.

Exercise2.4.4b

HereistheTheE/RDiagramAgain,wehaveomittedrelationshipnamesandattributesotherthan

ourchoiceforthekeyattributes.ThekeyforLeaguesisitsownname;thisentitysetisnotweak.

ThekeyforTeamsisitsownnameplusthenameoftheleagueofwhichtheteamisapart,e.g.,

(Rangers,MLB)or(Rangers,NHL).ThekeyforPlayersconsistsoftheplayer'snumberandthe

keyfortheteamonwhichheorsheplays.Sincethelatterkeyisitselfapairconsistingofteam

andleaguenames,thekeyforplayersisthetriple(number,teamName,leagueName).e.g.,Jeff

Garciais(5,49ers,NFL).

DatabaseSystems:TheCompleteBook

SolutionsforChapter3

SolutionsforSection3.1

Exercise3.1.2(a)

Wecanorderthethreetuplesinanyof3!=6ways.Also,thecolumnscanbeorderedinanyof3!

=6ways.Thus,thenumberofpresentationsis6*6=36.

SolutionsforSection3.2

Exercise3.2.1

Customers(ssNo,name,address,phone)

Flights(number,day,aircraft)

Bookings(ssNo,number,day,row,seat)

Beingaweakentityset,Bookings'relationhasthekeysforCustomersandFlightsandBookings'

ownattributes.

NoticethattherelationsobtainedfromthetoCustandtoFItrelationshipsareunnecessary.They

are:

toCust(ssNo,ssNol,number,day)

toFlt(ssNo,number,day,number1,dayl)

Thatis,fortoCust,thekeyofCustomersispairedwiththekeyforBookings.Sincebothinclude

ssNo,thisattributeisrepeatedwithtwodifferentnames,ssNoandssNol.Asimilarsituation

existsfortoFIt.

Exercise3.2.3

Ships(name,yearLaunched)

SisterOf(name,sisterName)

SolutionsforSection3.3

Exercise3.3.1

SinceCoursesisweak,itskeyisnumberandthenameofitsdepartment.Wedonothavea

relationforGivenBy.Inpart(a),thereisarelationforCoursesandarelationforLabCoursesthat

hasonlythekeyandthecomputer-allocationattribute.Itlookslike:

Depts(name,chair)

Courses(number,deptName,room)

LabCourses(number,deptName,allocation)

Forpart(b),LabCoursesgetsalltheattributesofCourses,as:

Depts(name,chair)

Courses(number,deptName,room)

LabCourses(number,deptName,room,allocation)

Andfor(c),CoursesandLabCoursesarecombined,as:

Depts(name,chair)

Courses(number,deptName,room,allocation)

Exercise3.3.4(a)

Thereisonerelationforeachentityset,sothenumberofrelationsise.Therelationfortheroot

entitysethasaattributes,whiletheotherrelations,whichmustincludethekeyattributes,have

a+kattributes.

SolutionsforSection3.4

Exercise3.4.2

SurelyIDisakeybyitself.However,wethinkthattheattributesx,y,andztogetherformanother

key.Thereasonisthatatnotimecantwomoleculesoccupythesamepoint.

Exercise3.4.4

Thekeyattributesareindicatedbycapitalizationintheschemabelow:

Customers(SSNO,name,address,phone)

Flights(NUMBER,DAY,aircraft)

Bookings(SSNO,NUMBER,DAY,row,seat)

Exercise3.4.6(a)

ThesuperkeysareanysubsetthatcontainsAl.Thus,thereare2A{n-l}suchsubsets,sinceeachof

then-1attributesA2throughAnmayindependentlybechoseninorout.

SolutionsforSection3.5

Exercise3.5.1(a)

Wecouldtryinferencerulestodeducenewdependenciesuntilwearesatisfiedwehavethemall.

Amoresystematicwayistoconsidertheclosuresofall15nonemptysetsofattributes.

ForthesingleattributeswehaveA+=A,B+=B,C+=ACD,andD+=AD.Thus,theonlynew

dependencywegetwithasingleattributeontheleftisC->A.

Nowconsiderpairsofattributes:

AB+=ABCD,sowegetnewdependencyAB->D.AC+=ACD,andAC->Disnontrivial.AD+=

AD,sonothingnew.BC+=ABCD,sowegetBC->A,andBC->D.BD+=ABCD,givingus

BD->AandBD->C.CD+=ACD,givingCD->A.

Forthetriplesofattributes,ACD+=ACD,buttheclosuresoftheothersetsareeachABCD.Thus,

wegetnewdependenciesABC->D,ABD->C,andBCD->A.

SinceABCD+=ABCD,wegetnonewdependencies.

Thecollectionof11newdependenciesmentionedaboveis:C->A,AB->D,AC->D,BC->A,

BC->D,BD->A,BD->C,CD->A,ABC->D,ABD->C,andBCD->A.

Exercise3.5.1(b)

Fromtheanalysisofclosuresabove,wefindthatAB,BC,andBDarekeys.Allothersetseither

donothaveABCDastheclosureorcontainoneofthesethreesets.

Exercise3.5.1(c)

Thesuperkeysareallthosethatcontainoneofthosethreekeys.Thatis,asuperkeythatisnota

keymustcontainBandmorethanoneofA,C,andD.Thus,the(proper)superkeysareABC,

ABD,BCD,andABCD.

Exercise3.5.3(a)

WemustcomputetheclosureofAlA2...AnC.SinceAlA2...An->Bisadependency,surelyBisin

thisset,provingA1A2...AnC->B.

Exercise3.5.4(a)

Considertherelation

——

AB

——

02

——

12

ThisrelationsatisfiesA->BbutdoesnotsatisfyB->A.

Exercise3.5.8(a)

Ifallsetsofattributesareclosed,thentherecannotbeanynontrivialfunctionaldependencies.For

supposeAlA2...An->Bisanontrivialdependency.ThenAlA2...An+containsBandthus

A1A2...Anisnotclosed.

Exercise3.5.10(a)

Weneedtocomputetheclosuresofallsubsetsof{ABC},althoughthereisnoneedtothinkabout

theemptysetorthesetofallthreeattributes.Herearethecalculationsfortheremainingsixsets:

A+=A

B+=B

C+=ACE

AB+=ABCDE

AC+=ACE

BC+=ABCDE

WeignoreDandE,soabasisfortheresultingfunctionaldependenciesforABCare:C->Aand

AB->C.NotethatBC->Aistrue,butfollowslogicallyfromC->A,andthereforemaybeomitted

fromourlist.

SolutionsforSection3.6

Exercise3.6.1(a)

InthesolutiontoExercise3.5.1wefoundthatthereare14nontrivialdependencies,includingthe

threegivenonesand11deriveddependencies.Theseare:C->A,C->D,D->A,AB->D,AB->C,

AC->D,BC->A,BC->D,BD->A,BD->C,CD->A,ABC->D,ABD->C,andBCD->A.

WealsolearnedthatthethreekeyswereAB,BC,andBD.Thus,anydependencyabovethatdoes

nothaveoneofthesepairsontheleftisaBCNFviolation.Theseare:C->A,C->D,D->A,AC->D,

andCD->A.

OnechoiceistodecomposeusingC->D.ThatgivesusABCandCDasdecomposedrelations.CD

issurelyinBCNF,sinceanytwo-attributerelationis.ABCisnotinBCNF,sinceABandBCare

itsonlykeys,butC->AisadependencythatholdsinABCDandthereforeholdsinABC.Wemust

furtherdecomposeABCintoACandBC.Thus,thethreerelationsofthedecompositionareAC,

BC,andCD.

SinceallattributesareinatleastonekeyofABCD,thatrelationisalreadyin3NF,andno

decompositionisnecessary.

Exercise3.6.1(b)

(Revised1/19/02)TheonlykeyisAB.Thus,B->CandB->DarebothBCNFviolations.The

derivedFD*sBD->CandBC->DarealsoBCNFviolations.However,anyothernontrivial,

derivedFDwillhaveAandBontheleft,andthereforewillcontainakey.

OnepossibleBCNFdecompositionisABandBCD.Itisobtainedstartingwithanyofthefour

violationsmentionedabove.ABistheonlykeyforAB,andBistheonlykeyforBCD.

SincethereisonlyonekeyforABCD,the3NFviolationsarethesame,andsoisthe

decomposition.

SolutionsforSection3.7

Exercise3.7.1

SinceA->->B,andallthetupleshavethesamevalueforattributeA,wecanpairtheB-valuefrom

anytuplewiththevalueoftheremainingattributeCfromanyothertuple.Thus,weknowthatR

musthaveatleasttheninetuplesoftheform(a,b,c),wherebisanyofbl,b2,orb3,andcisany

ofcl,c2,orc3.Thatis,wecanderive,usingthedefinitionofamultivalueddependency,thateach

ofthetuples(a,bl,c2),(a,bl,c3),(a,b2,cl),(a,b2,c3),(a,b3,cl),and(a,b3,c2)arealsoinR.

Exercise3.7.2(a)

First,peoplehaveuniqueSocialSecuritynumbersanduniquebirthdates.Thus,weexpectthe

functionaldependenciesssNo->nameandssNo->birthdatehold.Thesameappliestochildren,so

weexpectchildSSNo->childnameandchildSSNo->childBirthdate.Finally,anautomobilehasa

uniquebrand,soweexpectautoSerialNo->autoMake.

Therearetwomultivalueddependenciesthatdonotfollowfromthesefunctionaldependencies.

First,theinformationaboutonechildofapersonisindependentofotherinformationaboutthat

person.Thatis,ifapersonwithsocialsecuritynumbershasatuplewithcn,cs,cb,thenifthereis

anyothertupletforthesameperson,therewillalsobeanothertuplethatagreeswithtexceptthat

ithascn,cs,cbinitscomponentsforthechildname,SocialSecuritynumber,andbirthdate.Thatis

themultivalueddependency

ssNo->->childSSNochildNamechildBirthdate

Similarly,anautomobileserialnumberandmakeareindependentofanyoftheotherattributes,so

weexpectthemultivalueddependency

ssNo->->autoSerialNoautoMake

Thedependenciesaresummarizedbelow:

ssNo->namebirthdate

childSSNo->childNamechildBirthdate

autoSerialNo->autoMake

ssNo->->childSSNochildNamechildBirthdate

ssNo->->autoSerialNoautoMake

Exercise3.7.2(b)

Wesuggesttherelationschemas

{ssNo,name,birthdate)

{ssNo,childSSNo}

{childSSNo,childNamechildBirthdate}

{ssNo,autoSerialNo)

{autoSerialNo,autoMake}

Aninitialdecompositionbasedonthetwomultivalueddependencieswouldgiveus

{ssNo,name,birthDate}

{ssNo,childSSNo,childName,childBirthdate}

{ssNo,autoSerialNo,autoMake}

Functionaldependenciesforceustodecomposethesecondandthirdofthese.

Exercise3.7.3(a)

Sincetherearenofunctionaldependencies,theonlykeyisallfourattributes,ABCD.Thus,each

ofthenontrvialmultivalueddependenciesA->->BandA->->Cviolate4NF.Wemustseparateout

theattributesofthesedependencies,firstdecomposingintoABandACD,andthendecomposing

thelatterintoACandADbecauseA->->Cisstilla4NFviolationforACD.Thefinalsetof

relationsareAB,AC,andAD.

Exercise3.7.7(a)

LetWbethesetofattributesnotinX,Y,orZ.Considertwotuplesxyzwandxy'z'w'inthe

relationRinquestion.BecauseX->->Y,wecanswapthey's,soxy'zwandxyz'w'areinR.

BecauseX->->Z,wecantakethepairoftuplesxyzwandxyz'w1andswapZ'stogetxyz'wand

xyzw'.Similarly,wecantakethepairxy'z'w'andxy'zwandswapZ'stogetxy'zw'andxy'z'w.

Inconclusion,westartedwithtuplesxyzwandxy'z'w'andshowedthatxyzw1andxy'z'wmust

alsobeintherelation.ThatisexactlythestatementoftheMVDX->->Y-union-Z.Notethatthe

abovestatementsallmakesenseevenifthereareattributesincommonamongX,Y,andZ.

Exercise3.7.8(a)

ConsiderarelationRwithschemaABCDandtheinstancewithfourtuplesabed,abed',abt'd,and

ab'c'dr,ThisinstancesatisfiestheMVDA->->BC.However,itdoesnotsatisfyA->->B.For

example,ifitdidsatisfyA->->B,thenbecausetheinstancecontainsthetuplesabedandab'e'd,

wewouldexpectittocontainabe'dandab'ed,neitherofwhichisintheinstance.

DatabaseSystems:TheCompleteBook

SolutionsforChapter4

SolutionsforSection4.2

Exercise4.2.1

classCustomer{

attributestringname;

attributestringaddr;

attributestringphone;

attributeintegerssNo;

relationshipSet<Account>ownsAccts

inverseAccount::ownedBy;

)

classAccount{

attributeintegernumber;

attributestringtype;

attributerealbalance;

relationshipSet<Customer>ownedBy

inverseCustomer::ownsAccts

)

Exercise4.2.4

classPerson{

attributestringname;

relationshipPersonmotherOf

inversePerson::childrenOfFemale

relationshipPersonfatherOf

inversePerson::childrenOfMale

relationshipSet<Person>children

inversePerson::parentsOf

relationshipSet<Person>childrenOfFemale

inversePerson::motherOf

relationshipSet<Person>childrenOfMale

inversePerson::fatherOf

relationshipSet<Person>parentsOf

inversePerson::children

Noticethattherearesixdifferentrelationshipshere.Forexample,theinverseoftherelationship

thatconnectsapersontotheir(unique)motherisarelationshipthatconnectsamother(i.e.,a

femaleperson)tothesetofherchildren.Thatrelationship,whichwecallchildrenOfFemale,is

differentfromthechildrenrelationship,whichconnectsanyone-maleorfemale-totheir

children.

Exercise4.2.7

ArelationshipRisitsowninverseifandonlyifforeverypair(a,b)inR,thepair(b,a)isalsoinR.

Intheterminologyofsettheory,therelationRis''symmetric.”

SolutionsforSection4.3

Exercise4.3.1

WethinkthatSocialSecuritynumbershouldmethekeyforCustomer,andaccountnumber

shouldbethekeyforAccount.HereistheODLsolutionwithkeyandextentdeclarations.

classCustomer

(extentCustomerskeyssNo)

(

attributestringname;

attributestringaddr;

attributestringphone;

attributeintegerssNo;

relationshipSet<Account>ownsAccts

inverseAccount::ownedBy;

)

classAccount

(extentAccountskeynumber)

(

attributeintegernumber;

attributestringtype;

attributerealbalance;

relationshipSet<Customer>ownedBy

inverseCustomer::ownsAccts

)

SolutionsforSection4.4

Exercise4.4.1(a)

Sincetherelationshipbetweencustomersandaccountsismany-many,weshouldcreateaseparate

relationfromthatrelationship-pair.

Customers(ssNo,name,address,phone)

Accounts(number,type,balance)

CustAcct(ssNo,number)

Exercise4.4.1(d)

Therisonlyoneattribute,butthreepairsofrelationshipsfromPersontoitself.SincemotherOf

andfatherOfaremany-one,wecanstoretheirinversesintherelationforPerson.Thatis,foreach

person,childrenOfMaleandchildrenOfFemalewillindicatethatpersons'sfatherandmother.The

childrenrelationshipismany-many,andrequiresitsownrelation.Thisrelationactuallyturnsout

toberedundant,inthesensethatitstuplescanbededucedfromtherelationshipsstoredwith

Person.Theschema:

Persons(name,childrenOfFemale,childrenOfMale)

Parent-Child(parent,child)

Exercise4.4.4

Yougetaschemalike:

Studios(name,address,ownedMovie)

Sincename->addressistheonlyFD,thekeyis{name,ownedMovie},andtheFDhasaleftside

thatisnotasuperkey.

Exercise4.4.5(a,b,c)

(a)StructCard{stringrank,stringsuit};

(b)classHand{

attributeSettheHand;

)；

Forpart(c)wehave:

Hands(handld,rank,suit)

NoticethattheclassHandhasnokey,soweneedtocreateone:handID.Eachhandhas,inthe

relationHands,onetupleforeachcardinthehand.

Exercise4.4.5(e)

StructPlayerHand{stringPlayer,HandtheHand};

classDeal{

attributeSettheDeal;

)

Alternatively,PlayerHandcanbedefineddirectlywithinthedeclarationofattributetheDeal.

Exercise4.4.5(h)

SincekeysforHandandDealarelacking,amechanicalwaytodesignthedatabaseschemaisto

haveonerelationconnectingdealsandplayer-handpairs,andanothertospecifythecontentsof

hands.Thatis:

Deals(dealID,player,handID)

Hands(handID,rank,suit)

However,ifwethinkaboutit,wecangetridofhandIDandconnectthedealandtheplayer

directlytotheplayer'scards,as:

Deals(dealID,player,rank,suit)

Exercise4.4.5(i)

First,cardisreallyapairconsistingofasuitandarank,soweneedtwoattributesinarelation

schematorepresentcards.However,muchmoreimportantisthefactthattheproposedschema

doesnotdistinguishwhichcardisinwhichhand.Thus,weneedanotherattributethatindicates

whichhandwithinthedealacardbelongsto,somethinglike:

Deals(dealID,handID,rank,suit)

Exercise4.4.6(c)

Attributebisreallyabagof(f,g)pairs.Thus,associatedwitheacha-valuewillbezeroormore

(f,g)pairs,eachofwhichcanoccurseveraltimes.Weshalluseanattributecounttoindicatethe

numberofoccurrences,althoughifrelationsallowduplicatetupleswecouldsimplyallow

duplicate(a,f,g)triplesintherelation.Theproposedschemais:

C(a,f,g,count)

SolutionsforSection4.5

Exercise4.5.1(b)

Studios(name,address,movies{(title,year,inColor,length,

stars{(name,address,birthdate)})})

Sincetheinformationaboutastarisrepeatedonceforeachoftheirmovies,thereisredundancy.

Toeliminateit,wehavetouseaseparaterelationforstarsandusepointersfromstudios.Thatis:

Stars(name,address,birthdate)

Studios(name,address,movies{(title,year,inColor,length,

stars{*Stars})})

Sinceeachmovieisownedbyonestudio,theinformationaboutamovieappearsinonlyonetuple

ofStudios,andthereisnoredundancy.

Exercise4.5.2

Customers(name,address,phone,ssNo,accts{*Accounts})

Accounts(number,type,balance,owners{"Customers})

SolutionsforSection4.6

Exercise4.6.1(a)

WeneedtoaddnewnodeslabeledGeorgeLucasandGaryKurtz.Then,fromthenodesw(which

representsthemovieStarWars),weaddarcstothesetwonewnodes,labeleddirectedByand

producedBy,respectively.

Exercise4.6.2

Createnodesforeachaccountandeachcustomer.Fromeachcustomernodeisanarctoanode

representingtheattributesofthecustomer,e.g.,anarclabelednametothecustomer'sname.

Likewise,thereisanarcfromeachaccountnodetoeachattributeofthataccount,e.g.,anarc

labeledbalancetothevalueofthebalance.

Torepresentownershipofaccountsbycustomers,weplaceanarclabeledownsfromeach

customernodetothenodeofeachaccountthatcustomerholds(possiblyjointly).Also,weplace

anarclabeledownedByfromeachaccountnodetothecustomernodeforeachownerofthat

account.

Exercise4.6.5

Inthesemistructuredmodel,nodesrepresentdataelements,i.e.,entitiesratherthanentitysets.In

theE/Rmodel,nodesofalltypesrepresentschemaelements,andthedataisnotrepresentedatall.

SolutionsforSection4.7

Exercise4.7.1(a)

<STARS-MOVIES>

<STARstarld=Mcf1starredln="sw,esb,ijn>

<NAME>CarrieFisher</NAME>

<ADDRESSxSTREET>123MapleSt.</STREET>

<CITY>Hollywood</CITY></ADDRESS>

<ADDRESSxSTREET>5LocustLn.</STREET>

<CITY>Malibu</CITY></ADDRESS>

</STAR>

<STARstarld=nmhHstarredln=usw,esb,ijH>

<NAME>MarkHamill</NAME>

<ADDRESSxSTREET>456OakRd.<STREET>

<CITY>Brentwood</CITY></ADDRESS>

</STAR>

<STARstarld=nhfnstarredln=*'sw,esb,ij,witn>

<NAME>HarrisonFord</NAME>

<ADDRESSxSTREET>whatever</STREET>

<CITY>whatever</CITYx/ADDRESS>

</STAR>

<MOVIEmovield="sw"starsOf=Hcf,mhn>

<TITLE>StarWars</TITLE>

<YEAR>1977<VYEAR>

</MOVIE>

<MOVIEmovield="esb"starsOf="cf,mhu>

<TITLE>EmpireStrikesBack</TITLE>

<YEAR>1980<7YEAR>

</MOVIE>

<MOVIEmovield="ij"starsOf="cf,mh”>

<TITLE>ReturnoftheJedi</TITLE>

<YEAR>1983<yYEAR>

</MOVIE>

<MOVIEmovielD=HwitustarsOf="hF>

<TITLE>Witness</TITLE>

<YEAR>1985<7YEAR>

</MOVIE>

</STARS-MOVIES>

Exercise4.7.2

<!DOCTYPEBank[

<!ELEMENTBANK(CUSTOMER*ACCOUNT*)〉

<!ELEMENTCUSTOMER(NAME,ADDRESS,PHONE,SSNO)>

<!ATTLISTCUSTOMER

custldID

ownsIDREFS>

<!ELEMENTNAME(#PCDATA)>

<!ELEMENTADDRESS(#PCDATA)>

<!ELEMENTPHONE(#PCDATA)>

<!ELEMENTSSNO(#PCDATA)>

<!ELEMENTACCOUNT(NUMBER,TYPE,BALANCE)>

<!ATTLISTACCOUNT

acctldID

ownedByIDREFS>

<!ELEMENTNUMBER(#PCDATA)>

<!ELEMENTTYPE(#PCDATA)>

<!ELEMENTBALANCE(#PCDATA)>

DatabaseSystems:TheComplete

Book

SolutionsforChapter5

SolutionsforSection5.2

Exercise5.2.1(a)

PI_model(SIGMA_{speed>=1000})(PC)

Exercise5.2.1(f)

Thetrickistotheta-joinPCwithitselfontheconditionthattheharddisksizesare

equal.ThatgivesustuplesthathavetwoPCmodelnumberswiththesamevalueof

hd.However,thesetwoPC'scouldinfactbethesame,sowemustalsorequireinthe

theta-jointhatthemodelnumbersbeunequal.Finally,wewanttheharddisksizes,so

weprojectontohd.

Theexpressioniseasiesttoseeifwewriteitusingsometemporaryvalues.Westart

byrenamingPCtwicesowecantalkabouttwooccurrencesofthesameattributes.

RI=RHO_{PC1}(PC)

R2=RHO_{PC2}(PC)

R3=R1JOIN_{PCl.hd=PC2.hdANDPCI.model<>PC2.model}R2

R4=PI_{PCl.hd}(R3)

Exercise5.2.1(h)

First,wefindRI,themodel-speedpairsfrombothPCandLaptop.Then,wefind

fromRIthosecomputersthatareatleast133Mh.Atthesametime,wejoin

RIwithProducttoconnectmodelnumberstotheirmanufacturersandweprojectout

thespeedtogetR2.ThenwejoinR2withitself(afterrenaming)tofindpairsof

differentmodelsbythesamemaker.Finally,wegetouranswer,R5,byprojecting

ontooneofthemakerattributes.Asequenceofstepsgivingthedesiredexpressionis:

RI=PI_{model,speed}(PC)UNIONPI_{model,speed}(Laptop)

R2=PI_{maker,model}(SIGMA_{speed>=700}(RI)JOINProduct)

R3=RH0_{T(maker2,model2)}(R2)

R4=R2JOIN_{maker=maker2ANDmodel<>model2}(R3)

R5=PI_{maker}(R4)

Exercise5.2.2

HerearefiguresfortheexpressiontreesofExercise5.2.1Part(a)Part(f)Part(h).

Notethatthethirdfigureisnotreallyatree,sinceitusesacommonsubexpression.

Wecouldduplicatethenodestomakeitatree,butusingcommonsubexpressionsisa

valuableformofqueryoptimization.Oneofthebenefitsonegetsfromconstructing

'trees"forqueriesistheabilitytocombinenodesthatrepresentcommon

subexpressions.

K{PCIJd)

比nodel

>=1000

PCPCPC

n.

makei

PCLaptop

Exercise5.2.7

Therelationthatresultsfromthenaturaljoinhasonlyoneattributefromeachpairof

equatedattributes.Thetheta-joinhasattributesforboth,andtheircolumnsare

identical.

Exercise5.2.9(a)

IfallthetuplesofRandSaredifferent,thentheunionhasn+mtuples,andthis

numberisthemaximumpossible.

Theminimumnumberoftuplesthatcanappearintheresultoccursifeverytupleof

onerelationalsoappearsintheother.Surelytheunionhasatleastasmanytuplesas

thelargerofRandthatis,max(n,m)tuples.However,itispossibleforeverytupleof

thesmallertoappearintheother,soitispossiblethatthereareasfewasmax(n,m)

tuplesintheunion.

Exercise5.2.10

Inthefollowingweusethenameofarelationbothasitsinstance(setoftuples)and

asitsschema(setofattributes).Thecontextdeterminesuniquelywhichismeant.

PI_R(RJOINS)Note,however,thatthisexpressionworksonlyforsets;itdoesnot

preservethemultipicityoftuplesinR.Thenexttwoexpressionsworkforbags.

RJOINDELTA(PI_{RINTERSECTS}(S))Inthisexpression,eachprojectionofa

tuplefromSontotheattributesthatarealsoinRappearsexactlyonceinthesecond

argumentofthejoin,soitpreservesmultiplicityoftuplesinR,exceptforthosethat

donotjoinwithS,whichdisappear.TheDELTAoperatorremovesduplicates,as

describedinSection5.4.

R-[R-PI_R(RJOINS)]Here,thestrategyistofindthedanglingtuplesofRand

removethem.

SolutionsforSection5.3

Exercise5.3.1

Asabag,thevalueis{700,1500,866,866,1000,1300,1400,700,1200,750,1100,

350,733}.Theorderisunimportant,ofcourse.Theaverageis959.

Asaset,thevalueis{700,1500,866,1000,1300,1400,1200,750,1100,350,733},

andtheaverageis967.H3>Exercise5.3.4(a)

Assets,anelementxisintheleft-sideexpression

(RUNIONS)UNIONT

ifandonlyifitisinatleastoneofR,S,andT.Likewise,itisintheright-side

expression

RUNION(SUNIONT)

underexactlythesameconditions.Thus,thetwoexpressionshaveexactlythesame

members,andthesetsareequal.

Asbags,anelementxisintheleft-sideexpressionasmany