数据库系统基础教程(第二版)课后习题答案

DatabaseSystems:TheCompleteBookSolutionsforChapter2SolutionsforSection2.1ExerciseTheE/RDiagram.Exercise(a)TheE/RDiagramKobvxybzSolutionsforSection2.2ExerciseTheAddressesentitysetisnothingbutasingleaddress,sowewouldprefertomakeaddressanattributeofCustomers.Werethebanktorecordseveraladdressesforacustomer,thenitmightmakesensetohaveanAddressesentitysetandmakeLives-atamany-manyrelationship.TheAcct-Setsentitysetisuseless.Eachcustomerhasauniqueaccountsetcontaininghisorheraccounts.However,relatingcustomersdirectlytotheiraccountsinamany-manyrelationshipconveysthesameinformationandeliminatestheaccount-setconceptaltogether.SolutionsforSection2.3Exercise(a)KeysssNoandnumberareappropriateforCustomersandAccounts,respectively.Also,wethinkitdoesnotmakesenseforanaccounttoberelatedtozerocustomers,soweshouldroundtheedgeconnectingOwnstoCustomers.Itdoesnotseeminappropriatetohaveacustomerwith0accounts;theymightbeaborrower,forexample,soweputnoconstraintontheconnectionfromOwnstoAccounts.HereistheTheE/RDiagram，showingunderlinedkeysandthenumerocityconstraint.Exercise(b)IfRismany-onefromE1toE2,thentwotuples(e1,e2)and(f1,f2)oftherelationshipsetforRmustbethesameiftheyagreeonthekeyattributesforE1.Toseewhy,surelye1andf1arethesame.BecauseRismany-onefromE1toE2,e2andf2mustalsobethesame.Thus,thepairsarethesame.SolutionsforSection2.4ExerciseHereistheTheE/RDiagram.WehaveomittedattributesotherthanourchoiceforthekeyattributesofStudentsandCourses.Alsoomittedarenamesfortherelationships.AttributegradeisnotpartofthekeyforEnrollments.ThekeyforEnrollementsisstudIDfromStudentsanddeptandnumberfromCourses.ExercisebHereistheTheE/RDiagramAgain,wehaveomittedrelationshipnamesandattributesotherthanourchoiceforthekeyattributes.ThekeyforLeaguesisitsownname;thisentitysetisnotweak.ThekeyforTeamsisitsownnameplusthenameoftheleagueofwhichtheteamisapart,e.g.,(Rangers,MLB)or(Rangers,NHL).ThekeyforPlayersconsistsoftheplayer'snumberandthekeyfortheteamonwhichheorsheplays.Sincethelatterkeyisitselfapairconsistingofteamandleaguenames,thekeyforplayersisthetriple(number,teamName,leagueName).e.g.,JeffGarciais(5,49ers,NFL).DatabaseSystems:TheCompleteBookSolutionsforChapter3

SolutionsforSection3.1Exercise(a)Wecanorderthethreetuplesinanyof3!=6ways.Also,thecolumnscanbeorderedinanyof3!=6ways.Thus,thenumberofpresentationsis6*6=36.SolutionsforSection3.2ExerciseCustomers(ssNo,name,address,phone)Flights(number,day,aircraft)Bookings(ssNo,number,day,row,seat)Beingaweakentityset,Bookings'relationhasthekeysforCustomersandFlightsandBookings'ownattributes.NoticethattherelationsobtainedfromthetoCustandtoFltrelationshipsareunnecessary.Theyare:toCust(ssNo,ssNo1,number,day)toFlt(ssNo,number,day,number1,day1)Thatis,fortoCust,thekeyofCustomersispairedwiththekeyforBookings.SincebothincludessNo,thisattributeisrepeatedwithtwodifferentnames,ssNoandssNo1.AsimilarsituationexistsfortoFlt.ExerciseShips(name,yearLaunched)SisterOf(name,sisterName)SolutionsforSection3.3ExerciseSinceCoursesisweak,itskeyisnumberandthenameofitsdepartment.WedonothavearelationforGivenBy.Inpart(a),thereisarelationforCoursesandarelationforLabCoursesthathasonlythekeyandthecomputer-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)Exercise(a)Thereisonerelationforeachentityset,sothenumberofrelationsise.Therelationfortherootentitysethasaattributes,whiletheotherrelations,whichmustincludethekeyattributes,havea+kattributes.SolutionsforSection3.4ExerciseSurelyIDisakeybyitself.However,wethinkthattheattributesx,y,andztogetherformanotherkey.Thereasonisthatatnotimecantwomoleculesoccupythesamepoint.ExerciseThekeyattributesareindicatedbycapitalizationintheschemabelow:Customers(SSNO,name,address,phone)Flights(NUMBER,DAY,aircraft)Bookings(SSNO,NUMBER,DAY,row,seat)Exercise(a)ThesuperkeysareanysubsetthatcontainsA1.Thus,thereare2^{n-1}suchsubsets,sinceeachofthen-1attributesA2throughAnmayindependentlybechoseninorout.SolutionsforSection3.5Exercise(a)Wecouldtryinferencerulestodeducenewdependenciesuntilwearesatisfiedwehavethemall.Amoresystematicwayistoconsidertheclosuresofall15nonemptysetsofattributes.ForthesingleattributeswehaveA+=A,B+=B,C+=ACD,andD+=AD.Thus,theonlynewdependencywegetwithasingleattributeontheleftisC->A.Nowconsiderpairsofattributes:AB+=ABCD,sowegetnewdependencyAB->D.AC+=ACD,andAC->Disnontrivial.AD+=AD,sonothingnew.BC+=ABCD,sowegetBC->A,andBC->D.BD+=ABCD,givingusBD->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.Exercise(b)Fromtheanalysisofclosuresabove,wefindthatAB,BC,andBDarekeys.AllothersetseitherdonothaveABCDastheclosureorcontainoneofthesethreesets.Exercise(c)Thesuperkeysareallthosethatcontainoneofthosethreekeys.Thatis,asuperkeythatisnotakeymustcontainBandmorethanoneofA,C,andD.Thus,the(proper)superkeysareABC,ABD,BCD,andABCD.Exercise(a)WemustcomputetheclosureofA1A2...AnC.SinceA1A2...An->Bisadependency,surelyBisinthisset,provingA1A2...AnC->B.Exercise(a)ConsidertherelationAB0212ThisrelationsatisfiesA->BbutdoesnotsatisfyB->A.Exercise(a)Ifallsetsofattributesareclosed,thentherecannotbeanynontrivialfunctionaldependencies.ForsupposeA1A2...An->Bisanontrivialdependency.ThenA1A2...An+containsBandthusA1A2...Anisnotclosed.Exercise(a)Weneedtocomputetheclosuresofallsubsetsof{ABC},althoughthereisnoneedtothinkabouttheemptysetorthesetofallthreeattributes.Herearethecalculationsfortheremainingsixsets:A+=AB+=BC+=ACEAB+=ABCDEAC+=ACEBC+=ABCDEWeignoreDandE,soabasisfortheresultingfunctionaldependenciesforABCare:C->AandAB->C.NotethatBC->Aistrue,butfollowslogicallyfromC->A,andthereforemaybeomittedfromourlist.SolutionsforSection3.6Exercise(a)InthesolutiontoExercisewefoundthatthereare14nontrivialdependencies,includingthethreegivenonesand11deriveddependencies.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,anydependencyabovethatdoesnothaveoneofthesepairsontheleftisaBCNFviolation.Theseare:C->A,C->D,D->A,AC->D,andCD->A.OnechoiceistodecomposeusingC->D.ThatgivesusABCandCDasdecomposedrelations.CDissurelyinBCNF,sinceanytwo-attributerelationis.ABCisnotinBCNF,sinceABandBCareitsonlykeys,butC->AisadependencythatholdsinABCDandthereforeholdsinABC.WemustfurtherdecomposeABCintoACandBC.Thus,thethreerelationsofthedecompositionareAC,BC,andCD.SinceallattributesareinatleastonekeyofABCD,thatrelationisalreadyin3NF,andnodecompositionisnecessary.Exercise(b)(Revised1/19/02)TheonlykeyisAB.Thus,B->CandB->DarebothBCNFviolations.ThederivedFD'sBD->CandBC->DarealsoBCNFviolations.However,anyothernontrivial,derivedFDwillhaveAandBontheleft,andthereforewillcontainakey.OnepossibleBCNFdecompositionisABandBCD.Itisobtainedstartingwithanyofthefourviolationsmentionedabove.ABistheonlykeyforAB,andBistheonlykeyforBCD.SincethereisonlyonekeyforABCD,the3NFviolationsarethesame,andsoisthedecomposition.SolutionsforSection3.7ExerciseSinceA->->B,andallthetupleshavethesamevalueforattributeA,wecanpairtheB-valuefromanytuplewiththevalueoftheremainingattributeCfromanyothertuple.Thus,weknowthatRmusthaveatleasttheninetuplesoftheform(a,b,c),wherebisanyofb1,b2,orb3,andcisanyofc1,c2,orc3.Thatis,wecanderive,usingthedefinitionofamultivalueddependency,thateachofthetuples(a,b1,c2),(a,b1,c3),(a,b2,c1),(a,b2,c3),(a,b3,c1),and(a,b3,c2)arealsoinR.Exercise(a)First,peoplehaveuniqueSocialSecuritynumbersanduniquebirthdates.Thus,weexpectthefunctionaldependenciesssNo->nameandssNo->birthdatehold.Thesameappliestochildren,soweexpectchildSSNo->childnameandchildSSNo->childBirthdate.Finally,anautomobilehasauniquebrand,soweexpectautoSerialNo->autoMake.Therearetwomultivalueddependenciesthatdonotfollowfromthesefunctionaldependencies.First,theinformationaboutonechildofapersonisindependentofotherinformationaboutthatperson.Thatis,ifapersonwithsocialsecuritynumbershasatuplewithcn,cs,cb,thenifthereisanyothertupletforthesameperson,therewillalsobeanothertuplethatagreeswithtexceptthatithascn,cs,cbinitscomponentsforthechildname,SocialSecuritynumber,andbirthdate.ThatisthemultivalueddependencyssNo->->childSSNochildNamechildBirthdateSimilarly,anautomobileserialnumberandmakeareindependentofanyoftheotherattributes,soweexpectthemultivalueddependencyssNo->->autoSerialNoautoMakeThedependenciesaresummarizedbelow:ssNo->namebirthdatechildSSNo->childNamechildBirthdateautoSerialNo->autoMakessNo->->childSSNochildNamechildBirthdatessNo->->autoSerialNoautoMakeExercise(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.Exercise(a)Sincetherearenofunctionaldependencies,theonlykeyisallfourattributes,ABCD.Thus,eachofthenontrvialmultivalueddependenciesA->->BandA->->Cviolate4NF.Wemustseparateouttheattributesofthesedependencies,firstdecomposingintoABandACD,andthendecomposingthelatterintoACandADbecauseA->->Cisstilla4NFviolationforACD.ThefinalsetofrelationsareAB,AC,andAD.Exercise(a)LetWbethesetofattributesnotinX,Y,orZ.Considertwotuplesxyzwandxy'z'w'intherelationRinquestion.BecauseX->->Y,wecanswapthey's,soxy'zwandxyz'w'areinR.BecauseX->->Z,wecantakethepairoftuplesxyzwandxyz'w'andswapZ'stogetxyz'wandxyzw'.Similarly,wecantakethepairxy'z'w'andxy'zwandswapZ'stogetxy'zw'andxy'z'w.Inconclusion,westartedwithtuplesxyzwandxy'z'w'andshowedthatxyzw'andxy'z'wmustalsobeintherelation.ThatisexactlythestatementoftheMVDX->->Y-union-Z.NotethattheabovestatementsallmakesenseevenifthereareattributesincommonamongX,Y,andZ.Exercise(a)ConsiderarelationRwithschemaABCDandtheinstancewithfourtuplesabcd,abcd',ab'c'd,andab'c'd'.ThisinstancesatisfiestheMVDA->->BC.However,itdoesnotsatisfyA->->B.Forexample,ifitdidsatisfyA->->B,thenbecausetheinstancecontainsthetuplesabcdandab'c'd,wewouldexpectittocontainabc'dandab'cd,neitherofwhichisintheinstance.DatabaseSystems:TheCompleteBookSolutionsforChapter4SolutionsforSection4.2ExerciseclassCustomer{attributestringname;attributestringaddr;attributestringphone;attributeintegerssNo;relationshipSet<Account>ownsAcctsinverseAccount::ownedBy;}classAccount{attributeintegernumber;attributestringtype;attributerealbalance;relationshipSet<Customer>ownedByinverseCustomer::ownsAccts}ExerciseclassPerson{attributestringname;relationshipPersonmotherOfinversePerson::childrenOfFemalerelationshipPersonfatherOfinversePerson::childrenOfMalerelationshipSet<Person>childreninversePerson::parentsOfrelationshipSet<Person>childrenOfFemaleinversePerson::motherOfrelationshipSet<Person>childrenOfMaleinversePerson::fatherOfrelationshipSet<Person>parentsOfinversePerson::children}Noticethattherearesixdifferentrelationshipshere.Forexample,theinverseoftherelationshipthatconnectsapersontotheir(unique)motherisarelationshipthatconnectsamother(i.e.,afemaleperson)tothesetofherchildren.Thatrelationship,whichwecallchildrenOfFemale,isdifferentfromthechildrenrelationship,whichconnectsanyone--maleorfemale--totheirchildren.ExerciseArelationshipRisitsowninverseifandonlyifforeverypair(a,b)inR,thepair(b,a)isalsoinR.Intheterminologyofsettheory,therelationRis``symmetric.''SolutionsforSection4.3ExerciseWethinkthatSocialSecuritynumbershouldmethekeyforCustomer,andaccountnumbershouldbethekeyforAccount.HereistheODLsolutionwithkeyandextentdeclarations.classCustomer(extentCustomerskeyssNo){attributestringname;attributestringaddr;attributestringphone;attributeintegerssNo;relationshipSet<Account>ownsAcctsinverseAccount::ownedBy;}classAccount(extentAccountskeynumber){attributeintegernumber;attributestringtype;attributerealbalance;relationshipSet<Customer>ownedByinverseCustomer::ownsAccts}SolutionsforSection4.4Exercise(a)Sincetherelationshipbetweencustomersandaccountsismany-many,weshouldcreateaseparaterelationfromthatrelationship-pair.Customers(ssNo,name,address,phone)Accounts(number,type,balance)CustAcct(ssNo,number)Exercise(d)Therisonlyoneattribute,butthreepairsofrelationshipsfromPersontoitself.SincemotherOfandfatherOfaremany-one,wecanstoretheirinversesintherelationforPerson.Thatis,foreachperson,childrenOfMaleandchildrenOfFemalewillindicatethatpersons'sfatherandmother.Thechildrenrelationshipismany-many,andrequiresitsownrelation.Thisrelationactuallyturnsouttoberedundant,inthesensethatitstuplescanbededucedfromtherelationshipsstoredwithPerson.Theschema:Persons(name,childrenOfFemale,childrenOfMale)Parent-Child(parent,child)ExerciseYougetaschemalike:Studios(name,address,ownedMovie)Sincename->addressistheonlyFD,thekeyis{name,ownedMovie},andtheFDhasaleftsidethatisnotasuperkey.Exercise(a,b,c)(a)StructCard{stringrank,stringsuit};(b)classHand{attributeSettheHand;};Forpart(c)wehave:Hands(handId,rank,suit)NoticethattheclassHandhasnokey,soweneedtocreateone:handID.Eachhandhas,intherelationHands,onetupleforeachcardinthehand.Exercise(e)StructPlayerHand{stringPlayer,HandtheHand};classDeal{attributeSettheDeal;}Alternatively,PlayerHandcanbedefineddirectlywithinthedeclarationofattributetheDeal.Exercise(h)SincekeysforHandandDealarelacking,amechanicalwaytodesignthedatabaseschemaistohaveonerelationconnectingdealsandplayer-handpairs,andanothertospecifythecontentsofhands.Thatis:Deals(dealID,player,handID)Hands(handID,rank,suit)However,ifwethinkaboutit,wecangetridofhandIDandconnectthedealandtheplayerdirectlytotheplayer'scards,as:Deals(dealID,player,rank,suit)Exercise(i)First,cardisreallyapairconsistingofasuitandarank,soweneedtwoattributesinarelationschematorepresentcards.However,muchmoreimportantisthefactthattheproposedschemadoesnotdistinguishwhichcardisinwhichhand.Thus,weneedanotherattributethatindicateswhichhandwithinthedealacardbelongsto,somethinglike:Deals(dealID,handID,rank,suit)Exercise(c)Attributebisreallyabagof(f,g)pairs.Thus,associatedwitheacha-valuewillbezeroormore(f,g)pairs,eachofwhichcanoccurseveraltimes.Weshalluseanattributecounttoindicatethenumberofoccurrences,althoughifrelationsallowduplicatetupleswecouldsimplyallowduplicate(a,f,g)triplesintherelation.Theproposedschemais:C(a,f,g,count)SolutionsforSection4.5Exercise(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,theinformationaboutamovieappearsinonlyonetupleofStudios,andthereisnoredundancy.ExerciseCustomers(name,address,phone,ssNo,accts{*Accounts})Accounts(number,type,balance,owners{*Customers})SolutionsforSection4.6Exercise(a)WeneedtoaddnewnodeslabeledGeorgeLucasandGaryKurtz.Then,fromthenodesw(whichrepresentsthemovieStarWars),weaddarcstothesetwonewnodes,labeleddirectedByandproducedBy,respectively.ExerciseCreatenodesforeachaccountandeachcustomer.Fromeachcustomernodeisanarctoanoderepresentingtheattributesofthecustomer,e.g.,anarclabelednametothecustomer'sname.Likewise,thereisanarcfromeachaccountnodetoeachattributeofthataccount,e.g.,anarclabeledbalancetothevalueofthebalance.Torepresentownershipofaccountsbycustomers,weplaceanarclabeledownsfromeachcustomernodetothenodeofeachaccountthatcustomerholds(possiblyjointly).Also,weplaceanarclabeledownedByfromeachaccountnodetothecustomernodeforeachownerofthataccount.ExerciseInthesemistructuredmodel,nodesrepresentdataelements,i.e.,entitiesratherthanentitysets.IntheE/Rmodel,nodesofalltypesrepresentschemaelements,andthedataisnotrepresentedatall.SolutionsforSection4.7Exercise(a)<STARS-MOVIES><STARstarId="cf"starredIn="sw,esb,rj"><NAME>CarrieFisher</NAME><ADDRESS><STREET>123MapleSt.</STREET> <CITY>Hollywood</CITY></ADDRESS><ADDRESS><STREET>5LocustLn.</STREET> <CITY>Malibu</CITY></ADDRESS></STAR><STARstarId="mh"starredIn="sw,esb,rj"><NAME>MarkHamill</NAME><ADDRESS><STREET>456OakRd.<STREET> <CITY>Brentwood</CITY></ADDRESS></STAR><STARstarId="hf"starredIn="sw,esb,rj,wit"><NAME>HarrisonFord</NAME><ADDRESS><STREET>whatever</STREET><CITY>whatever</CITY></ADDRESS></STAR><MOVIEmovieId="sw"starsOf="cf,mh"><TITLE>StarWars</TITLE><YEAR>1977</YEAR></MOVIE><MOVIEmovieId="esb"starsOf="cf,mh"><TITLE>EmpireStrikesBack</TITLE><YEAR>1980</YEAR></MOVIE><MOVIEmovieId="rj"starsOf="cf,mh"><TITLE>ReturnoftheJedi</TITLE><YEAR>1983</YEAR></MOVIE><MOVIEmovieID="wit"starsOf="hf"><TITLE>Witness</TITLE><YEAR>1985</YEAR></MOVIE></STARS-MOVIES>Exercise<!DOCTYPEBank[<!ELEMENTBANK(CUSTOMER*ACCOUNT*)><!ELEMENTCUSTOMER(NAME,ADDRESS,PHONE,SSNO)><!ATTLISTCUSTOMERcustIdIDownsIDREFS><!ELEMENTNAME(#PCDATA)><!ELEMENTADDRESS(#PCDATA)><!ELEMENTPHONE(#PCDATA)><!ELEMENTSSNO(#PCDATA)><!ELEMENTACCOUNT(NUMBER,TYPE,BALANCE)><!ATTLISTACCOUNTacctIdIDownedByIDREFS><!ELEMENTNUMBER(#PCDATA)><!ELEMENTTYPE(#PCDATA)><!ELEMENTBALANCE(#PCDATA)>]>DatabaseSystems:TheCompleteBookSolutionsforChapter5SolutionsforSection5.2Exercise(a)PI_model(SIGMA_{speed>=1000})(PC)Exercise(f)Thetrickistotheta-joinPCwithitselfontheconditionthattheharddisksizesareequal.ThatgivesustuplesthathavetwoPCmodelnumberswiththesamevalueofhd.However,thesetwoPC'scouldinfactbethesame,sowemustalsorequireinthetheta-jointhatthemodelnumbersbeunequal.Finally,wewanttheharddisksizes,soweprojectontohd.Theexpressioniseasiesttoseeifwewriteitusingsometemporaryvalues.WestartbyrenamingPCtwicesowecantalkabouttwooccurrencesofthesameattributes.R1=RHO_{PC1}(PC)R2=RHO_{PC2}(PC)R3=R1JOIN_{PC1.hd=PC2.hdANDPC1.model<>PC2.model}R2R4=PI_{PC1.hd}(R3)Exercise(h)First,wefindR1,themodel-speedpairsfrombothPCandLaptop.Then,wefindfromR1thosecomputersthatare``fast,''atleast133Mh.Atthesametime,wejoinR1withProducttoconnectmodelnumberstotheirmanufacturersandweprojectoutthespeedtogetR2.ThenwejoinR2withitself(afterrenaming)tofindpairsofdifferentmodelsbythesamemaker.Finally,wegetouranswer,R5,byprojectingontooneofthemakerattributes.Asequenceofstepsgivingthedesiredexpressionis:R1=PI_{model,speed}(PC)UNIONPI_{model,speed}(Laptop)R2=PI_{maker,model}(SIGMA_{speed>=700}(R1)JOINProduct)R3=RHO_{T(maker2,model2)}(R2)R4=R2JOIN_{maker=maker2ANDmodel<>model2}(R3)R5=PI_{maker}(R4)ExerciseHerearefiguresfortheexpressiontreesofExercisePart(a)Part(f)Part(h).Notethatthethirdfigureisnotreallyatree,sinceitusesacommonsubexpression.Wecouldduplicatethenodestomakeitatree,butusingcommonsubexpressionsisavaluableformofqueryoptimization.Oneofthebenefitsonegetsfromconstructing``trees''forqueriesistheabilitytocombinenodesthatrepresentcommonsubexpressions.ExerciseTherelationthatresultsfromthenaturaljoinhasonlyoneattributefromeachpairofequatedattributes.Thetheta-joinhasattributesforboth,andtheircolumnsareidentical.Exercise(a)IfallthetuplesofRandSaredifferent,thentheunionhasn+mtuples,andthisnumberisthemaximumpossible.Theminimumnumberoftuplesthatcanappearintheresultoccursifeverytupleofonerelationalsoappearsintheother.SurelytheunionhasatleastasmanytuplesasthelargerofRandthatis,max(n,m)tuples.However,itispossibleforeverytupleofthesmallertoappearintheother,soitispossiblethatthereareasfewasmax(n,m)tuplesintheunion.ExerciseInthefollowingweusethenameofarelationbothasitsinstance(setoftuples)andasitsschema(setofattributes).Thecontextdeterminesuniquelywhichismeant.PI_R(RJOINS)Note,however,thatthisexpressionworksonlyforsets;itdoesnotpreservethemultipicityoftuplesinR.Thenexttwoexpressionsworkforbags.RJOINDELTA(PI_{RINTERSECTS}(S))Inthisexpression,eachprojectionofatuplefromSontotheattributesthatarealsoinRappearsexactlyonceinthesecondargumentofthejoin,soitpreservesmultiplicityoftuplesinR,exceptforthosethatdonotjoinwithS,whichdisappear.TheDELTAoperatorremovesduplicates,asdescribedinSection5.4.R-[R-PI_R(RJOINS)]Here,thestrategyistofindthedanglingtuplesofRandremovethem.SolutionsforSection5.3ExerciseAsabag,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>Exercise(a)Assets,anelementxisintheleft-sideexpression(RUNIONS)UNIONTifandonlyifitisinatleastoneofR,S,andT.Likewise,itisintheright-sideexpressionRUNION(SUNIONT)underexactlythesameconditions.Thus,thetwoexpressionshaveexactlythesamemembers,andthesetsareequal.Asbags,anelementxisintheleft-sideexpressionasmanytimesasthesumofthenumberoftimesitisinR,S,andT.Thesameholdsfortherightside.Thus,asbagstheexpressionsalsohavethesamevalue.Exercise(h)Assets,elementxisintheleftsideRUNION(SINTERSECTT)ifandonlyifxiseitherinRorinbothSandT.Elementxisintherightside(RUNIONS)INTERSECT(RUNIONT)ifandonlyifitisinbothRUNIONSandRUNIONT.IfxisinR,thenitisinbothunions.IfxisinbothSandT,thenitisinbothunion.However,ifxisneitherinRnorinbothofSandT,thenitcannotbeinbothunions.Forexample,supposexisnotinRandnotinS.ThenxisnotinRUNIONS.Thus,thestatementofwhenxisintherightsideisexactlythesameaswhenitisintheleftside:xiseitherinRorinbothofSandT.Now,considertheexpressionforbags.ElementxisintheleftsidethesumofthenumberoftimesitisinRplusthesmallerofthenumberoftimesxisinSandthenumberoftimesxisinT.Likewise,thenumberoftimesxisintherightsideisthesmallerofThesumofthenumberoftimesxisinRandinS.ThesumofthenumberoftimesxisinRandinT.Amoment'sreflectiontellsusthatthisminimumisthesumofthenumberoftimesxisinRplusthesmallerofthenumberoftimesxisinSandinT,exactlyasfortheleftside.Exercise(a)Forsets,weobservethatelementxisintheleftside(RINTERSECTS)-TifandonlyifitisinbothRandSandnotinT.ThesameholdsfortherightsideRINTERSECT(S-T)soassets,thee