数据库系统概念 第五版 (西尔伯沙茨 著) 机械工业出版社 课后答案 Exercises 课后答案 116页

'课后答案网，用心为你服务！大学答案---中学答案---考研答案---考试答案最全最多的课后习题参考答案，尽在课后答案网（www.khdaw.com）！Khdaw团队一直秉承用心为大家服务的宗旨，以关注学生的学习生活为出发点，旨在为广大学生朋友的自主学习提供一个分享和交流的平台。爱校园（www.aixiaoyuan.com）课后答案网（www.khdaw.com）淘答案（www.taodaan.com） INSTRUCTORSMANUALTOACCOMPANYDatabaseSystemConceptsFifthEditionAbrahamSilberschatzYaleUniversityHenryF.KorthLehighUniversityS.SudarshanIndianInstituteofTechnology,BombayCopyrightc2005A.Silberschatz,H.Korth,andS.Sudarshan ContentsPreface1Chapter1IntroductionExercises3Chapter2RelationalModelExercises7Chapter3SQLExercises11Chapter4AdvancedSQLExercises19Chapter5OtherRelationalLanguagesExercises23Chapter6DatabaseDesignandtheE-RModelExercises33iii ivContentsChapter7RelationalDatabaseDesignExercises41Chapter8ApplicationDesignandDevelopmentExercises47Chapter9Object-BasedDatabasesExercises51Chapter10XMLExercises55Chapter11StorageandFileStructureExercises61Chapter12IndexingandHashingExercises65Chapter13QueryProcessingExercises69Chapter14QueryOptimizationExercises75Chapter15TransactionsExercises79Chapter16ConcurrencyControlExercises83Chapter17RecoverySystemExercises89 ContentsvChapter18DataAnalysisandMiningExercises93Chapter19InformationRetrievalExercises99Chapter20Database-SystemArchitecturesExercises101Chapter21ParallelDatabasesExercises105Chapter22DistributedDatabasesExercises109Chapter23AdvancedApplicationDevelopmentExercises115Chapter24AdvancedDataTypesandNewApplicationsExercises119Chapter25AdvancedTransactionProcessingExercises123 PrefaceThisvolumeisaninstructorsmanualforthe5theditionofDatabaseSystemConceptsbyAbrahamSilberschatz,HenryF.KorthandS.Sudarshan.Itcontainsanswerstotheexercisesattheendofeachchapterofthebook.Beforeprovidinganswerstotheexercisesforeachchapter,weincludeafewremarksaboutthechapter.Thenatureoftheseremarksvary.Theyincludeexplanationsoftheinclusionoromissionofcertainmaterial,andremarksonhowweteachthechapterinourowncourses.Theremarksalsoincludesuggestionsonmaterialtoskipiftimeisatapremium,andtipsonsoftwareandsupplementarymaterialthatcanbeusedforprogrammingexercises.TheWebhomepageofthebook,athttp://www.db-book.com,containsavarietyofusefulinformation,includingup-to-dateerrata,onlineappendicesdescribingthenetworkdatamodel,thehierarchicaldatamodel,andadvancedrelationaldatabasedesign,andmodelcoursesyllabi.Wewillperiodicallyupdatethepagewithsupple-mentarymaterialthatmaybeofusetoteachersandstudents.Weprovideamailinglistthroughwhichuserscancommunicateamongthem-selvesandwithus.Ifyouwishtousethisfacility,pleasevisitthefollowingURLandfollowtheinstructionstheretosubscribe:http://mailman.cs.yale.edu/mailman/listinfo/db-book-listThemailmanmailinglistsystemprovidesmanybenefits,suchasanarchiveofpost-ings,andseveralsubscriptionoptions,includingdigestandWebonly.Tosendmes-sagestothelist,sende-mailto:db-book-list@cs.yale.eduWewouldappreciateitifyouwouldnotifyusofanyerrorsoromissionsinthebook,aswellasintheinstructorsmanual.Internetelectronicmailshouldbead-dressedtodb-book@cs.yale.edu.PhysicalmailmaybesenttoAviSilberschatz,YaleUniversity,51ProspectStreet,NewHaven,CT,06520,USA.1 2PrefaceAlthoughwehavetriedtoproduceaninstructorsmanualwhichwillaidalloftheusersofourbookasmuchaspossible,therecanalwaysbeimprovements.Thesecouldincludeimprovedanswers,additionalquestions,sampletestquestions,pro-grammingprojects,suggestionsonalternativeordersofpresentationofthematerial,additionalreferences,andsoon.Ifyouwouldliketosuggestanysuchimprove-mentstothebookortheinstructorsmanual,wewouldbegladtohearfromyou.Allcontributionsthatwemakeuseofwill,ofcourse,beproperlycreditedtotheircontributor.Thismanualisderivedfromthemanualsfortheearliereditions.Themanualforthe4theditionwaspreparedbyNileshDalvi,SumitSanghai,GauravBhalotiaandArvindHulgeri.Themanualforthe3rdeditionwaspreparedbyK.V.RaghavanwithhelpfromPrateekR.Kapadia.SaraStrandtmanhelpedwiththeinstructormanualforthe2ndand3rdeditions,whileGregSpeegleandDawnBezvinerhelpedustopreparetheinstructorsmanualforthe1stedition.A.S.H.F.K.S.S.InstructorManualVersion5.0.0 CHAPTER1IntroductionExercises1.5Listfourapplicationswhichyouhaveused,thatmostlikelyusedadatabasesystemtostorepersistentdata.Answer:Noanswer1.6Listfoursignificantdifferencesbetweenafile-processingsystemandaDBMS.Answer:Somemaindifferencesbetweenadatabasemanagementsystemandafile-processingsystemare:•Bothsystemscontainacollectionofdataandasetofprogramswhichaccessthatdata.Adatabasemanagementsystemcoordinatesboththephysicalandthelogicalaccesstothedata,whereasafile-processingsystemcoordi-natesonlythephysicalaccess.•Adatabasemanagementsystemreducestheamountofdataduplicationbyensuringthataphysicalpieceofdataisavailabletoallprogramsauthorizedtohaveaccesstoit,whereasdatawrittenbyoneprograminafile-processingsystemmaynotbereadablebyanotherprogram.•Adatabasemanagementsystemisdesignedtoallowflexibleaccesstodata(i.e.,queries),whereasafile-processingsystemisdesignedtoallowpre-determinedaccesstodata(i.e.,compiledprograms).•Adatabasemanagementsystemisdesignedtocoordinatemultipleusersaccessingthesamedataatthesametime.Afile-processingsystemisusuallydesignedtoallowoneormoreprogramstoaccessdifferentdatafilesatthesametime.Inafile-processingsystem,afilecanbeaccessedbytwoprogramsconcurrentlyonlyifbothprogramshaveread-onlyaccesstothefile.1.7Explainthedifferencebetweenphysicalandlogicaldataindependence.Answer:3 4Chapter1Introduction•Physicaldataindependenceistheabilitytomodifythephysicalschemewithoutmakingitnecessarytorewriteapplicationprograms.Suchmodifi-cationsincludechangingfromunblockedtoblockedrecordstorage,orfromsequentialtorandomaccessfiles.•Logicaldataindependenceistheabilitytomodifytheconceptualschemewithoutmakingitnecessarytorewriteapplicationprograms.Suchamodi-ficationmightbeaddingafieldtoarecord;anapplicationprogramsviewhidesthischangefromtheprogram.1.8Listfiveresponsibilitiesofadatabasemanagementsystem.Foreachresponsi-bility,explaintheproblemsthatwouldariseiftheresponsibilitywerenotdis-charged.Answer:Ageneralpurposedatabasemanager(DBM)hasfiveresponsibilities:a.interactionwiththefilemanager.b.integrityenforcement.c.securityenforcement.d.backupandrecovery.e.concurrencycontrol.IftheseresponsibilitieswerenotmetbyagivenDBM(andthetextpointsoutthatsometimesaresponsibilityisomittedbydesign,suchasconcurrencycontrolonasingle-userDBMforamicrocomputer)thefollowingproblemscanoccur,respectively:a.NoDBMcandowithoutthis,ifthereisnofilemanagerinteractionthennothingstoredinthefilescanberetrieved.b.Consistencyconstraintsmaynotbesatisfied,accountbalancescouldgobe-lowtheminimumallowed,employeescouldearntoomuchovertime(e.g.,hours>80)or,airlinepilotsmayflymorehoursthanallowedbylaw.c.Unauthorizedusersmayaccessthedatabase,orusersauthorizedtoaccesspartofthedatabasemaybeabletoaccesspartsofthedatabaseforwhichtheylackauthority.Forexample,ahighschoolstudentcouldgetaccesstonationaldefensesecretcodes,oremployeescouldfindoutwhattheirsupervisorsearn.d.Datacouldbelostpermanently,ratherthanatleastbeingavailableinacon-sistentstatethatexistedpriortoafailure.e.Consistencyconstraintsmaybeviolateddespiteproperintegrityenforce-mentineachtransaction.Forexample,incorrectbankbalancesmightbereflectedduetosimultaneouswithdrawalsanddeposits,andsoon.1.9ListatleasttworeasonswhydatabasesystemssupportdatamanipulationusingadeclarativequerylanguagesuchasSQL,insteadofjustprovidingaalibraryofCorC++functionstocarryoutdatamanipulation.Answer:Noanswer1.10ExplainwhatproblemsarecausedbythedesignofthetableinFigure1.5.Answer:Noanswer Exercises51.11Whatarefivemainfunctionsofadatabaseadministrator?Answer:Fivemainfunctionsofadatabaseadministratorare:•Tocreatetheschemedefinition•Todefinethestoragestructureandaccessmethods•Tomodifytheschemeand/orphysicalorganizationwhennecessary•Tograntauthorizationfordataaccess•Tospecifyintegrityconstraints CHAPTER2RelationalModelExercises2.4Describethedifferencesinmeaningbetweenthetermsrelationandrelationschema.Answer:Arelationschemaisatypedefinition,andarelationisaninstanceofthatschema.Forexample,student(ss#,name)isarelationschemaandss#name123-45-6789TomJones456-78-9123JoeBrownisarelationbasedonthatschema.2.5ConsidertherelationaldatabaseofFigure2.35,wheretheprimarykeysareun-derlined.Giveanexpressionintherelationalalgebratoexpresseachofthefol-lowingqueries:a.FindthenamesofallemployeeswhoworkforFirstBankCorporation.b.FindthenamesandcitiesofresidenceofallemployeeswhoworkforFirstBankCorporation.c.Findthenames,streetaddress,andcitiesofresidenceofallemployeeswhoworkforFirstBankCorporationandearnmorethan$10,000perannum.d.Findthenamesofallemployeesinthisdatabasewholiveinthesamecityasthecompanyforwhichtheywork.e.Assumethecompaniesmaybelocatedinseveralcities.FindallcompanieslocatedineverycityinwhichSmallBankCorporationislocated.Answer:a.Πperson-name(σcompany-name=FirstBankCorporation(works))7 8Chapter2RelationalModelemployee(person-name,street,city)works(person-name,company-name,salary)company(company-name,city)manages(person-name,manager-name)Figure2.35.RelationaldatabaseforExercises2.1,2.3and2.9.b.Πperson-name,city(employee(σ(works)))company-name=FirstBankCorporationc.Πperson-name,street,city(σ(company-name=FirstBankCorporation∧salary>10000)worksemployee)d.Πperson-name(employeeworkscompany)e.Note:SmallBankCorporationwillbeincludedineachanswer.Πcompany-name(company÷(Πcity(σ(company))))company-name=SmallBankCorporation2.6ConsidertherelationofFigure2.20,whichshowstheresultofthequery“Findthenamesofallcustomerswhohavealoanatthebank.”Rewritethequerytoincludenotonlythename,butalsothecityofresidenceforeachcustomer.ObservethatnowcustomerJacksonnolongerappearsintheresult,eventhoughJacksondoesinfacthavealoanfromthebank.a.ExplainwhyJacksondoesnotappearintheresult.b.SupposethatyouwantJacksontoappearintheresult.Howwouldyoumodifythedatabasetoachievethiseffect?c.Again,supposethatyouwantJacksontoappearintheresult.Writeaqueryusinganouterjointhataccomplishesthisdesirewithoutyourhavingtomodifythedatabase.Answer:TherewrittenqueryisΠcustomer-name,customer-city,amount(borrowerloancustomer)a.AlthoughJacksondoeshavealoan,noaddressisgivenforJacksoninthecustomerrelation.SincenotupleincustomerjoinswiththeJacksontupleofborrower,Jacksondoesnotappearintheresult.b.ThebestsolutionistoinsertJacksonsaddressintothecustomerrelation.Iftheaddressisunknown,nullvaluesmaybeused.Ifthedatabasesystemdoesnotsupportnulls,aspecialvaluemaybeused(suchasunknown)forJacksonsstreetandcity.Thespecialvaluechosenmustnotbeaplausiblenameforanactualcityorstreet.c.Πcustomer-name,customer-city,amount((borrowerloan)customer)2.7ConsidertherelationaldatabaseofFigure2.35.Giveanexpressionintherela-tionalalgebraforeachrequest:a.GiveallemployeesofFirstBankCorporationa10percentsalaryraise. Exercises9b.Giveallmanagersinthisdatabasea10percentsalaryraise,unlessthesalarywouldbegreaterthan$100,000.Insuchcases,giveonlya3percentraise.c.DeletealltuplesintheworksrelationforemployeesofSmallBankCorpora-tion.Answer:a.works←Πperson-name,company-name,1.1∗salary(σ(works))(company-name=FirstBankCorporation)∪(works−σ(works))company-name=FirstBankCorporationb.Thesamesituationariseshere.Asbefore,t1,holdsthetuplestobeupdatedandt2holdsthesetuplesintheirupdatedform.t1←Πworks.person-name,company-name,salary(σworks.person-name=manager-name(works×manages))t2←Πworks.person-name,company-name,salary∗1.03(σt1.salary∗1.1>100000(t1))t2←t2∪(Πworks.person-name,company-name,salary∗1.1(σt1.salary∗1.1≤100000(t1)))works←(works−t1)∪t2c.works←works−σ(works)company−name=SmallBankCorporation2.8Usingthebankexample,writerelational-algebraqueriestofindtheaccountsheldbymorethantwocustomersinthefollowingways:a.Usinganaggregatefunction.b.Withoutusinganyaggregatefunctions.Answer:a.t1←account-numberGcountcustomer-name(depositor)Πaccount-numberσnum-holders>2ρaccount-holders(account-number,num-holders)(t1)b.t1←(ρd1(depositor)×ρd2(depositor)×ρd3(depositor))t2←σ(d1.account-number=d2.account-number=d3.account-number)(t1)Πd1.account-number(σ(d1.customer-name=d2.customer-name∧d2.customer-name=d3.customer-name∧d3.customer-name=d1.customer-name)(t2))2.9ConsidertherelationaldatabaseofFigure2.35.Givearelational-algebraexpres-sionforeachofthefollowingqueries:a.Findthecompanywiththemostemployees.b.Findthecompanywiththesmallestpayroll.c.Findthosecompanieswhoseemployeesearnahighersalary,onaverage,thantheaveragesalaryatFirstBankCorporation.Answer: 10Chapter2RelationalModela.t1←company-nameGcount-distinctperson-name(works)t2←maxnum-employees(ρcompany-strength(company-name,num-employees)(t1))Πcompany-name(ρt3(company-name,num-employees)(t1)ρt4(num-employees)(t2))b.t1←company-nameGsumsalary(works)t2←minpayroll(ρcompany-payroll(company-name,payroll)(t1))Πcompany-name(ρt3(company-name,payroll)(t1)ρt4(payroll)(t2))c.t1←company-nameGavgsalary(works)t2←σcompany-name=FirstBankCorporation(t1)Πt3.company-name((ρt3(company-name,avg-salary)(t1))t3.avg-salary>first-bank.avg-salary(ρfirst-bank(company-name,avg-salary)(t2)))2.10Listtworeasonswhynullvaluesmightbeintroducedintothedatabase.Answer:Nullsmaybeintroducedintothedatabasebecausetheactualvalueiseitherunknownordoesnotexist.Forexample,anemployeewhoseaddresshaschangedandwhosenewaddressisnotyetknownshouldberetainedwithanulladdress.Ifemployeetupleshaveacompositeattributedependents,andaparticularemployeehasnodependents,thenthattuplesdependentsattributeshouldbegivenanullvalue.2.11Considerthefollowingrelationalschemaemployee(empno,name,office,age)books(isbn,title,authors,publisher)loan(empno,isbn,date)Writethefollowingqueriesinrelationalalgebra.a.FindthenamesofemployeeswhohaveborrowedabookpublishedbyMcGraw-Hill.b.FindthenamesofemployeeswhohaveborrowedallbookspublishedbyMcGraw-Hill.c.FindthenamesofemployeeswhohaveborrowedmorethanfivedifferentbookspublishedbyMcGraw-Hill.d.Foreachpublisher,findthenamesofemployeeswhohaveborrowedmorethanfivebooksofthatpublisher.Answer:Noanswer CHAPTER3SQLExercises3.8ConsidertheinsurancedatabaseofFigure3.11,wheretheprimarykeysareun-derlined.ConstructthefollowingSQLqueriesforthisrelationaldatabase.a.Findthenumberofaccidentsinwhichthecarsbelongingto“JohnSmith”wereinvolved.b.Updatethedamageamountforthecarwithlicensenumber“AABB2000”intheaccidentwithreportnumber“AR2197”to$3000.Answer:Note:Theparticipatedrelationrelatesdrivers,cars,andaccidents.a.SQLquery:selectcount(distinct*)fromaccidentwhereexists(select*fromparticipated,personwhereparticipated.driverid=person.driveridandperson.name=JohnSmithandaccident.reportnumber=participated.reportnumber)b.SQLquery:updateparticipatedsetdamageamount=3000wherereportnumber=“AR2197”anddriveridin(selectdriveridfromownswherelicense=“AABB2000”)11 12Chapter3SQLperson(driverid,name,address)car(license,model,year)accident(reportnumber,date,location)owns(driverid,license)participated(driverid,car,reportnumber,damageamount)Figure3.11.Insurancedatabase.employee(employeename,street,city)works(employeename,companyname,salary)company(companyname,city)manages(employeename,managername)Figure3.12.Employeedatabase.3.9ConsidertheemployeedatabaseofFigure3.12,wheretheprimarykeysareun-derlined.GiveanexpressioninSQLforeachofthefollowingqueries.a.FindthenamesofallemployeeswhoworkforFirstBankCorporation.b.Findallemployeesinthedatabasewholiveinthesamecitiesasthecom-paniesforwhichtheywork.c.Findallemployeesinthedatabasewholiveinthesamecitiesandonthesamestreetsasdotheirmanagers.d.Findallemployeeswhoearnmorethantheaveragesalaryofallemployeesoftheircompany.e.Findthecompanythathasthesmallestpayroll.Answer:a.FindthenamesofallemployeeswhoworkforFirstBankCorporation.selectemployeenamefromworkswherecompanyname=FirstBankCorporationb.Findallemployeesinthedatabasewholiveinthesamecitiesasthecom-paniesforwhichtheywork.selecte.employeenamefromemployeee,worksw,companycwheree.employeename=w.employeenameande.city=c.cityandw.companyname=c.companynamec.Findallemployeesinthedatabasewholiveinthesamecitiesandonthesamestreetsasdotheirmanagers.selectP.employeenamefromemployeeP,employeeR,managesMwhereP.employeename=M.employeenameandM.managername=R.employeenameandP.street=R.streetandP.city=R.city Exercises13d.Findallemployeeswhoearnmorethantheaveragesalaryofallemployeesoftheircompany.Thefollowingsolutionassumesthatallpeopleworkforatmostonecom-pany.selectemployeenamefromworksTwheresalary>(selectavg(salary)fromworksSwhereT.companyname=S.companyname)e.Findthecompanythathasthesmallestpayroll.selectcompanynamefromworksgroupbycompanynamehavingsum(salary)<=all(selectsum(salary)fromworksgroupbycompanyname)3.10ConsidertherelationaldatabaseofFigure3.12.GiveanexpressioninSQLforeachofthefollowingqueries.a.GiveallemployeesofFirstBankCorporationa10percentraise.b.GiveallmanagersofFirstBankCorporationa10percentraise.c.DeletealltuplesintheworksrelationforemployeesofSmallBankCorpora-tion.Answer:a.GiveallemployeesofFirstBankCorporationa10-percentraise.(thesolu-tionassumesthateachpersonworksforatmostonecompany.)updateworkssetsalary=salary*1.1wherecompanyname=FirstBankCorporationb.GiveallmanagersofFirstBankCorporationa10-percentraise.updateworkssetsalary=salary*1.1whereemployeenamein(selectmanagernamefrommanages)andcompanyname=FirstBankCorporationc.DeletealltuplesintheworksrelationforemployeesofSmallBankCorpora-tion.deleteworkswherecompanyname=SmallBankCorporation3.11Letthefollowingrelationschemasbegiven: 14Chapter3SQLR=(A,B,C)S=(D,E,F)Letrelationsr(R)ands(S)begiven.GiveanexpressioninSQLthatisequivalenttoeachofthefollowingqueries.a.ΠA(r)b.σB=17(r)c.r×sd.ΠA,F(σC=D(r×s))Answer:a.ΠA(r)selectdistinctAfromrb.σB=17(r)select*fromrwhereB=17c.r×sselectdistinct*fromr,sd.ΠA,F(σC=D(r×s))selectdistinctA,Ffromr,swhereC=D3.12LetR=(A,B,C),andletr1andr2bothberelationsonschemaR.GiveanexpressioninSQLthatisequivalenttoeachofthefollowingqueries.a.r1∪r2b.r1∩r2c.r1−r2d.ΠAB(r1)ΠBC(r2)Answer:a.r1∪r2(select*fromr1)union(select*fromr2)b.r1∩r2Wecanwritethisusingtheintersectoperation,whichisthepreferredapproach,butforvarietywepresentansolutionusinganestedsubquery. Exercises15select*fromr1where(A,B,C)in(select*fromr2)c.r1−r2select∗fromr1where(A,B,C)notin(select∗fromr2)Thiscanalsobesolvedusingtheexceptclause.d.ΠAB(r1)ΠBC(r2)selectr1.A,r2.B,r3.Cfromr1,r2wherer1.B=r2.B3.13Showthat,inSQL,<>allisidenticaltonotin.Answer:LetthesetSdenotetheresultofanSQLsubquery.Wecompare(x<>allS)with(xnotinS).Ifaparticularvaluex1satisfies(x1<>allS)thenforallelementsyofSx1=y.Thusx1isnotamemberofSandmustsatisfy(x1notinS).Similarly,supposethereisaparticularvaluex2whichsatisfies(x2notinS).ItcannotbeequaltoanyelementwbelongingtoS,andhence(x2<>allS)willbesatisfied.Thereforethetwoexpressionsareequivalent.3.14ConsidertherelationaldatabaseofFigure3.12.UsingSQL,defineaviewcon-sistingofmanagernameandtheaveragesalaryofallemployeeswhoworkforthatmanager.Explainwhythedatabasesystemshouldnotallowupdatestobeexpressedintermsofthisview.Answer:createviewsalinfoasselectmanagername,avg(salary)frommanagesm,workswwherem.employeename=w.employeenamegroupbymanagernameUpdatesshouldnotbeallowedinthisviewbecausethereisnowaytode-terminehowtochangetheunderlyingdata.Forexample,supposetherequestis“changetheaveragesalaryofemployeesworkingforSmithto$200”.ShouldeverybodywhoworksforSmithhavetheirsalarychangedto$200?Orshouldthefirst(ormore,ifnecessary)employeefoundwhoworksforSmithhavetheirsalaryadjustedsothattheaverageis$200?Neitherapproachreallymakessense.3.15WriteanSQLquery,withoutusingawithclause,tofindallbrancheswherethetotalaccountdepositislessthantheaveragetotalaccountdepositatallbranches, 16Chapter3SQLa.Usinganestedqueryinthefromclauser.b.Usinganestedqueryinahavingclause.Answer:Weoutputthebranchnamesalongwiththetotalaccountdepositatthebranch.a.Usinganestedqueryinthefromclauser.selectbranchname,totbalancefrom(selectbranchname,sum(balance)fromaccountgroupbybranchname)asbranchtotal(branchname,totbalance)wheretotbalance¡(selectavg(totbalance)from(selectbranchname,sum(balance)fromaccountgroupbybranchname)asbranchtotal(branchname,totbalance))b.Usinganestedqueryinahavingclause.selectbranchname,sum(balance)fromaccountgroupbybranchnamehavingsum(balance)¡(selectavg(totbalance)from(selectbranchname,sum(balance)fromaccountgroupbybranchname)asbranchtotal(branchname,totbalance))3.16Listtworeasonswhynullvaluesmightbeintroducedintothedatabase.Answer:NoAnswer3.17ShowhowtoexpressthecoalesceoperationfromExercise3.4usingthecaseoperation.Answer:NoAnswer.3.18GiveanSQLschemadefinitionfortheemployeedatabaseofFigure3.12.Chooseanappropriatedomainforeachattributeandanappropriateprimarykeyforeachrelationschema.Answer:createdomaincompanynameschar(20)createdomaincitynameschar(30)createdomainpersonnameschar(20)createtableemployee Exercises17(employeenamepersonnames,streetchar(30),citycitynames,primarykey(employeename))createtableworks(employeenamepersonnames,companynamecompanynames,salarynumeric(8,2),primarykey(employeename))createtablecompany(companynamecompanynames,citycitynames,primarykey(companyname))createtablemanages(employeenamepersonnames,managernamepersonnames,primarykey(employeename))3.19Usingtherelationsofoursamplebankdatabase,writeSQLexpressionstodefinethefollowingviews:a.Aviewcontainingtheaccountnumbersandcustomernames(butnotthebalances)forallaccountsattheDeerParkbranch.b.Aviewcontainingthenamesandaddressesofallcustomerswhohaveanaccountwiththebank,butdonothavealoan.c.AviewcontainingthenameandaverageaccountbalanceofeverycustomeroftheRockRidgebranch.Answer:NoAnswer.3.20ForeachoftheviewsthatyoudefinedinExercise3.19,explainhowupdateswouldbeperformed(iftheyshouldbeallowedatall).Answer:NoAnswer.3.21Considerthefollowingrelationalschemaemployee(empno,name,office,age)books(isbn,title,authors,publisher)loan(empno,isbn,date)WritethefollowingqueriesinSQL.a.PrintthenamesofemployeeswhohaveborrowedanybookpublishedbyMcGraw-Hill. 18Chapter3SQLb.PrintthenamesofemployeeswhohaveborrowedallbookspublishedbyMcGraw-Hill.c.Foreachpublisher,printthenamesofemployeeswhohaveborrowedmorethanfivebooksofthatpublisher.Answer:NoAnswer.3.22Considertherelationalschemastudent(studentid,studentname)registered(studentid,courseid)WriteanSQLquerytolistthestudent-idandnameofeachstudentalongwiththetotalnumberofcoursesthatthestudentisregisteredfor.Studentswhoarenotregisteredforanycoursemustalsobelisted,withthenumberofregisteredcoursesshownas0.Answer:NoAnswer.3.23Supposethatwehavearelationmarks(studentid,score).WriteanSQLquerytofindthedenserankofeachstudent.Thatis,allstudentswiththetopmarkgetarankof1,thosewiththenexthighestmarkgetarankof2,andsoon.Hint:Splitthetaskintoparts,usingthewithclause.Answer:NoAnswer. CHAPTER4AdvancedSQLExercises4.7Referential-integrityconstraintsasdefinedinthischapterinvolveexactlytworelations.Consideradatabasethatincludesthefollowingrelations:salaried-worker(name,office,phone,salary)hourly-worker(name,hourly-wage)address(name,street,city)Supposethatwewishtorequirethateverynamethatappearsinaddressappearineithersalaried-workerorhourly-worker,butnotnecessarilyinboth.a.Proposeasyntaxforexpressingsuchconstraints.b.Discusstheactionsthatthesystemmusttaketoenforceaconstraintofthisform.Answer:a.Forsimplicity,wepresentavariantoftheSQLsyntax.Aspartofthecreatetableexpressionforaddressweincludeforeignkey(name)referencessalaried-workerorhourly-workerb.Toenforcethisconstraint,wheneveratupleisinsertedintotheaddressrela-tion,alookuponthenamevaluemustbemadeonthesalaried-workerrelationand(ifthatlookupfailed)onthehourly-workerrelation(orvice-versa).4.8WriteaJavafunctionusingJDBCmetadatafeaturesthattakesaResultSetasaninputparameter,andprintsouttheresultintabularform,withappropriatenamesascolumnheadings.Answer:NoAnswer.19 20Chapter4AdvancedSQL4.9WriteaJavafunctionusingJDBCmetadatafeaturesthatprintsalistofallre-lationsinthedatabase,displayingforeachrelationthenamesandtypesofitsattributes.Answer:NoAnswer.4.10Consideranemployeedatabasewithtworelationsemployee(employee-name,street,city)works(employee-name,company-name,salary)wheretheprimarykeysareunderlined.Writeaquerytofindcompanieswhoseemployeesearnahighersalary,onaverage,thantheaveragesalaryatFirstBankCorporation.a.UsingSQLfunctionsasappropriate.b.WithoutusingSQLfunctions.Answer:a.createfunctionavg-salary(cnamevarchar(15))returnsintegerdeclareresultinteger;selectavg(salary)intoresultfromworkswhereworks.company-name=cnamereturnresult;endselectcompany-namefromworkswhereavg-salary(company-name)>avg-salary(FirstBankCorporation)b.selectcompany-namefromworksgroupbycompany-namehavingavg(salary)>(selectavg(salary)fromworkswherecompany-name=FirstBankCorporation)4.11RewritethequeryinSection4.6.1thatreturnsthename,streetandcityofallcustomerswithmorethanoneaccount,usingthewithclauseinsteadofusingafunctioncall.Answer:NoAnswer.4.12ComparetheuseofembeddedSQLwiththeuseinSQLoffunctionsdefinedinageneral-purposeprogramminglanguage.Underwhatcircumstanceswouldyouuseeachofthesefeatures?Answer:SQLfunctionsareprimarilyamechanismforextendingthepowerofSQLtohandleattributesofcomplexdatatypes(likeimages),ortoperformcomplexandnon-standardoperations.EmbeddedSQLisusefulwhenimper-ativeactionslikedisplayingresultsandinteractingwiththeuserareneeded. Exercises21ThesecannotbedoneconvenientlyinanSQLonlyenvironment.EmbeddedSQLcanbeusedinsteadofSQLfunctionsbyretrievingdataandthenperform-ingthefunctionsoperationsontheSQLresult.Howeveradrawbackisthatalotofquery-evaluationfunctionalitymayendupgettingrepeatedinthehostlanguagecode.4.13ModifytherecursivequeryinFigure4.14todefinearelationempldepth(employeename,managername,depth)wheretheattributedepthindicateshowmanylevelsofintermediatemanagersaretherebetweentheemployeeandthemanager.Employeeswhoaredirectlyunderamanagerwouldhaveadepthof0.Answer:NoAnswer.4.14Considertherelationalschemapart(partid,name,cost)subpart(partid,subpartid,count)Atuple(p1,p2,3)inthesubpartrelationdenotesthatthepartwithpart-idp2isadirectsubpartofthepartwithpart-idp1,andp1has3copiesofp2Notethatp2mayitselfhavefurthersubparts.WritearecursiveSQLquerythatoutputsthenamesofallsubpartsofthepartwithpart-id“P-100”.Answer:NoAnswer.4.15ConsideragaintherelationalschemafromExercise4.14.WriteaJDBCfunctionusingnon-recursiveSQLtofindthetotalcostofpart“P-100”,includingthecostsofallitssubparts.Besuretotakeintoaccountthefactthatapartmayhavemultipleoccurrencesofasubpart.YoumayuserecursioninJavaifyouwish.Answer:NoAnswer. CHAPTER5OtherRelationalLanguagesExercises5.6ConsidertheemployeedatabaseofFigure5.14.Giveexpressionsintuplerela-tionalcalculusanddomainrelationalcalculusforeachofthefollowingqueries:a.FindthenamesofallemployeeswhoworkforFirstBankCorporation.b.FindthenamesandcitiesofresidenceofallemployeeswhoworkforFirstBankCorporation.c.Findthenames,streetaddresses,andcitiesofresidenceofallemployeeswhoworkforFirstBankCorporationandearnmorethan$10,000peran-num.d.Findallemployeeswholiveinthesamecityasthatinwhichthecompanyforwhichtheyworkislocated.e.Findallemployeeswholiveinthesamecityandonthesamestreetastheirmanagers.f.FindallemployeesinthedatabasewhodonotworkforFirstBankCorpo-ration.g.FindallemployeeswhoearnmorethaneveryemployeeofSmallBankCor-poration.h.Assumethatthecompaniesmaybelocatedinseveralcities.Findallcom-panieslocatedineverycityinwhichSmallBankCorporationislocated.Answer:a.FindthenamesofallemployeeswhoworkforFirstBankCorporation:i.{t|∃s∈works(t[personname]=s[personname]∧s[companyname]=FirstBankCorporation)}ii.{

|∃c,s(∈works∧c=FirstBankCorporation)}23 24Chapter5OtherRelationalLanguagesb.FindthenamesandcitiesofresidenceofallemployeeswhoworkforFirstBankCorporation:i.{t|∃r∈employee∃s∈works(t[personname]=r[personname]∧t[city]=r[city]∧r[personname]=s[personname]∧s[companyname]=FirstBankCorporation)}ii.{|∃co,sa,st(∈works∧∈employee∧co=FirstBankCorporation)}c.Findthenames,streetaddress,andcitiesofresidenceofallemployeeswhoworkforFirstBankCorporationandearnmorethan$10,000perannum:i.{t|t∈employee∧(∃s∈works(s[personname]=t[personname]∧s[companyname]=FirstBankCorporation∧s[salary]>10000))}ii.{|∈employee∧∃co,sa(∈works∧co=FirstBankCorporation∧sa>10000)}d.Findthenamesofallemployeesinthisdatabasewholiveinthesamecityasthecompanyforwhichtheywork:i.{t|∃e∈employee∃w∈works∃c∈company(t[personname]=e[personname]∧e[personname]=w[personname]∧w[companyname]=c[companyname]∧e[city]=c[city])}ii.{

|∃st,c,co,sa(∈employee∧∈works∧∈company)}e.Findthenamesofallemployeeswholiveinthesamecityandonthesamestreetasdotheirmanagers:i.{t|∃l∈employee∃m∈manages∃r∈employee(l[personname]=m[personname]∧m[managername]=r[personname]∧l[street]=r[street]∧l[city]=r[city]∧t[personname]=l[personname])}ii.{|∃s,c,m(∈employee∧∈manages∧∈employee)}f.FindthenamesofallemployeesinthisdatabasewhodonotworkforFirstBankCorporation:Ifoneallowspeopletoappearinthedatabase(e.g.inemployee)butnotap-pearinworks,theproblemismorecomplicated.Wegivesolutionsforthismorerealisticcaselater.i.{t|∃w∈works(w[companyname]=FirstBankCorporation∧t[personname]=w[personname])}ii.{

|∃c,s(∈works∧c=FirstBankCorporation)} Exercises25Ifpeoplemaynotworkforanycompany:i.{t|∃e∈employee(t[personname]=e[personname]∧¬∃w∈works(w[companyname]=FirstBankCorporation∧w[personname]=t[personname]))}ii.{

|∃s,c(∈employee)∧¬∃x,y(y=FirstBankCorporation∧∈works)}g.FindthenamesofallemployeeswhoearnmorethaneveryemployeeofSmallBankCorporation:i.{t|∃w∈works(t[personname]=w[personname]∧∀s∈works(s[companyname]=SmallBankCorporation⇒w[salary]>s[salary]))}ii.{

|∃c,s(∈works∧∀p2,c2,s2(∈works∨c2=SmallBankCorporation∨s>s2))}h.Assumethecompaniesmaybelocatedinseveralcities.FindallcompanieslocatedineverycityinwhichSmallBankCorporationislocated.Note:SmallBankCorporationwillbeincludedineachanswer.i.{t|∀s∈company(s[companyname]=SmallBankCorporation⇒∃r∈company(t[companyname]=r[companyname]∧r[city]=s[city]))}ii.{|∀co2,ci2(∈company∨co2=SmallBankCorporation∨∈company)}5.7LetR=(A,B)andS=(A,C),andletr(R)ands(S)berelations.Writerelational-algebraexpressionsequivalenttothefollowingdomain-relational-calculusexpressions:a.{|∃b(∈r∧b=17)}b.{|∈r∧∈s}c.{|∃b(∈r)∨∀c(∃d(∈s)⇒∈s)}d.{|∃c(∈s∧∃b1,b2(∈r∧∈r∧b1>b2))}Answer:a.ΠA(σB=17(r))b.rsc.ΠA(r)∪(r÷σB(ΠC(s)))d.Πr.A((rs)c=r2.A∧r.B>r2.B(ρr2(r))) 26Chapter5OtherRelationalLanguagesItisinterestingtonotethat(d)isanabstractionofthenotoriousqueryFindallemployeeswhoearnmorethantheirmanager.LetR=(emp,sal),S=(emp,mgr)toobservethis.5.8RepeatExercise5.7,writingSQLqueriesinsteadofrelational-algebraexpres-sions.Answer:Noanswer.5.9LetR=(A,B)andS=(A,C),andletr(R)ands(S)berelations.Usingthespecialconstantnull,writetuple-relational-calculusexpressionsequivalenttoeachofthefollowing:a.rsb.rsc.rsAnswer:a.{t|∃r∈R∃s∈S(r[A]=s[A]∧t[A]=r[A]∧t[B]=r[B]∧t[C]=s[C])∨∃s∈S(¬∃r∈R(r[A]=s[A])∧t[A]=s[A]∧t[C]=s[C]∧t[B]=null)}b.{t|∃r∈R∃s∈S(r[A]=s[A]∧t[A]=r[A]∧t[B]=r[B]∧t[C]=s[C])∨∃r∈R(¬∃s∈S(r[A]=s[A])∧t[A]=r[A]∧t[B]=r[B]∧t[C]=null)∨∃s∈S(¬∃r∈R(r[A]=s[A])∧t[A]=s[A]∧t[C]=s[C]∧t[B]=null)}c.{t|∃r∈R∃s∈S(r[A]=s[A]∧t[A]=r[A]∧t[B]=r[B]∧t[C]=s[C])∨∃r∈R(¬∃s∈S(r[A]=s[A])∧t[A]=r[A]∧t[B]=r[B]∧t[C]=null)}5.10ConsidertheinsurancedatabaseofFigure5.15,wheretheprimarykeysareun-derlined.ConstructthefollowingGQBEqueriesforthisrelationaldatabase.a.Findthetotalnumberofpeoplewhoownedcarsthatwereinvolvedinac-cidentsin1989.b.Findthenumberofaccidentsinwhichthecarsbelongingto“JohnSmith”wereinvolved.Answer:Noanswer.5.11Giveatuple-relational-calculusexpressiontofindthemaximumvalueinrela-tionr(A).Answer:Noanswer.5.12RepeatExercise5.6usingQBEandDatalog.Answer:a.FindthenamesofallemployeeswhoworkforFirstBankCorporation.i.worksperson_namecompany_namesalaryP._xFirstBankCoii.query(X):-works(X,“FirstBankCorporation”,Y) Exercises27b.FindthenamesandcitiesofresidenceofallemployeeswhoworkforFirstBankCorporation.i.employeeperson_namestreetcityP._xP._yworksperson_namecompany_namesalary_xFirstBankCorporationii.query(X,Y):-employee(X,Z,Y),works(X,FirstBankCorporation,W)c.Findthenames,streetaddresses,andcitiesofresidenceofallemployeeswhoworkforFirstBankCorporationandearnmorethan$10,000peran-num. 28Chapter5OtherRelationalLanguagesIfpeoplemayworkforseveralcompanies,thefollowingsolutionswillonlylistthosewhoearnmorethan$10,000perannumfromFirstBankCorporationalone.i.employeeperson_namestreetcityP._xP._yP._zworksperson_namecompany_namesalary_xFirstBankCorporation>10000ii.query(X,Y,Z):-lives(X,Y,Z),works(X,FirstBankCorporation,W),W>10000d.Findallemployeeswholiveinthecitywherethecompanyforwhichtheyworkislocated.i.employeeperson_namestreetcityP._x_yworksperson_namecompany_namesalary_x_ccompanycompany_namecity_c_yii.query(X):-employee(X,Y,Z),works(X,V,W),company(V,Z)e.Findallemployeeswholiveinthesamecityandonthesamestreetastheirmanagers.i.employeeperson_namestreetcityP._x_s_c_y_s_cmanagesperson_namemanager_name_x_yii.query(X):-lives(X,Y,Z),manages(X,V),lives(V,Y,Z) Exercises29f.FindallemployeesinthedatabasewhodonotworkforFirstBankCorpo-ration.Thefollowingsolutionsassumethatallpeopleworkforexactlyonecom-pany.i.worksperson_namecompany_namesalaryP._xFirstBankCoii.query(X):-works(X,Y,Z),Y=FirstBankCorporationIfoneallowspeopletoappearinthedatabase(e.g.inemployee)butnotap-pearinworks,orifpeoplemayhavejobswithmorethanonecompany,thesolutionsareslightlymorecomplicated.Theyaregivenbelow:i.employeeperson_namestreetcityP._xworksperson_namecompany_namesalary¬_xFirstBankCorporationii.query(X):-employee(X,Y,Z),¬p1(X)p1(X):-works(X,FirstBankCorporation,W)g.FindallemployeeswhoearnmorethaneveryemployeeofSmallBankCor-poration.Thefollowingsolutionsassumethatallpeopleworkforatmostonecom-pany.i.worksperson_namecompany_namesalarySmallBankCo–yP._xMAX.All._yorworksperson_namecompany_namesalaryP._x–y¬SmallBankCo>–yii.query(X):-works(X,Y,Z),¬p(X)p(X):-works(X,C,Y1),works(V,SmallBankCorporation,Y),Y>Y1h.Assumethatthecompaniesmaybelocatedinseveralcities.Findallcom-panieslocatedineverycityinwhichSmallBankCorporationislocated. 30Chapter5OtherRelationalLanguagesNote:SmallBankCorporationwillbeincludedineachanswer.i.located_incompany_namesalarySmallBankCorporation–xP.–c–ySmallBankCorporation–yconditionCNT.ALL._y=CNT.ALL._x=ii.query(X):-company(X,C),notp(X)p(X):-company(X,C1),company(“SmallBankCorporation”,C2),notcompany(X,C2)5.13LetR=(A,B,C),andletr1andr2bothberelationsonschemaR.Giveexpres-sionsinQBE,andDatalogequivalenttoeachofthefollowingqueries:a.r1∪r2b.r1∩r2c.r1−r2d.ΠAB(r1)ΠBC(r2)Answer:a.r1∪r2i.resultABCP._a_b_cP._d_e_fr1ABC_a_b_cr2ABC_d_e_fii.query(X,Y,Z):-r1(X,Y,Z)query(X,Y,Z):-r2(X,Y,Z)b.r1∩r2i. Exercises31r1ABC_a_b_cr2ABC_d_e_fii.query(X,Y,Z):-r1(X,Y,Z),r2(X,Y,Z)c.r1−r2i.r1ABC_a_b_cr2ABC_d_e_fii.query(X,Y,Z):-r1(X,Y,Z),notr2(X,Y,Z)d.ΠAB(r1)ΠBC(r2)i.resultBCP._a_b_cr1ABC_a_br2ABC_b_cii.query(X,Y,Z):-r1(X,Y,V),r2(W,Y,Z)5.14Writeanextendedrelational-algebraviewequivalenttotheDatalogrulep(A,C,D):q1(A,B),q2(B,C),q3(4,B),D=B+1.Answer:Letusassumethatq1,q2andq3areinstancesoftheschema(A1,A2).TherelationalalgebraviewiscreateviewPasΠq1.A1,q2.A2,q1.A2+1(σq3.A1=4∧q1.A2=q2.A1∧q1.A2=q3.A2(q1×q2×q3)) 32Chapter5OtherRelationalLanguagesemployee(personname,street,city)works(personname,companyname,salary)company(companyname,city)manages(personname,managername)Figure5.14.Employeedatabase.person(driverid,name,address)car(license,model,year)accident(reportnumber,date,location)owns(driverid,license)participated(driverid,car,reportnumber,damageamount)Figure5.15.Insurancedatabase. CHAPTER6DatabaseDesignandtheE-RModelExercises6.14Explainthedistinctionsamongthetermsprimarykey,candidatekey,andsu-perkey.Answer:Asuperkeyisasetofoneormoreattributesthat,takencollectively,al-lowsustoidentifyuniquelyanentityintheentityset.Asuperkeymaycontainextraneousattributes.IfKisasuperkey,thensoisanysupersetofK.Asuperkeyforwhichnopropersubsetisalsoasuperkeyiscalledacandidatekey.Itispos-siblethatseveraldistinctsetsofattributescouldserveascandidatekeys.Theprimarykeyisoneofthecandidatekeysthatischosenbythedatabasedesignerastheprincipalmeansofidentifyingentitieswithinanentityset.6.15ConstructanE-Rdiagramforahospitalwithasetofpatientsandasetofmedi-caldoctors.Associatewitheachpatientalogofthevarioustestsandexamina-tionsconducted.Answer:SeeFigure6.16.16ConstructappropriatetablesforeachoftheE-RdiagramsinPracticeExercises6.1and6.2.Answer:a.Carinsurancetables:person(driver-id,name,address)car(license,year,model)accident(report-number,date,location)participated(driver-id,license,report-number,damage-amount)b.Hospitaltables:33 34Chapter6DatabaseDesignandtheE-RModelinsurancedate-admittednamedate-checked-outss#patientstest_logDr-Patienttest_idtestperformed_bydoctorstest_namedatetimeresultdss#namespecializationFigure6.1E-Rdiagramforahospital.patients(patient-id,name,insurance,date-admitted,date-checked-out)doctors(doctor-id,name,specialization)test(testid,testname,date,time,result)doctor-patient(patient-id,doctor-id)test-log(testid,patient-id)performed-by(testid,doctor-id)c.Universityregistrarstables:student(student-id,name,program)course(courseno,title,syllabus,credits)course-offering(courseno,secno,year,semester,time,room)instructor(instructor-id,name,dept,title)enrols(student-id,courseno,secno,semester,year,grade)teaches(courseno,secno,semester,year,instructor-id)requires(maincourse,prerequisite)6.17ExtendtheE-RdiagramofPracticeExercise6.4totrackthesameinformationforallteamsinaleague.Answer:SeeFigure6.2Notethataplayercanstayinonlyoneteamduringaseason.6.18Explainthedifferencebetweenaweakandastrongentityset.Answer:Astrongentitysethasaprimarykey.Alltuplesinthesetaredistin-guishablebythatkey.Aweakentitysethasnoprimarykeyunlessattributesofthestrongentitysetonwhichitdependsareincluded.Tuplesinaweakentitysetarepartitionedaccordingtotheirrelationshipwithtuplesinastrongentityset.Tupleswithineachpartitionaredistinguishablebyadiscriminator,whichisasetofattributes.6.19Wecanconvertanyweakentitysettoastrongentitysetbysimplyaddingap-propriateattributes.Why,then,dowehaveweakentitysets?Answer:Wehaveweakentitiesforseveralreasons: Exercises35matchidstadiumscorenameagedatematchplayedplayerscason_scoredscoreteam_playedplayer_ofresultteamnamerankingFigure6.2E-Rdiagramforallteamsstatistics.•Wewanttoavoidthedataduplicationandconsequentpossibleinconsis-tenciescausedbyduplicatingthekeyofthestrongentity.•Weakentitiesreflectthelogicalstructureofanentitybeingdependentonanotherentity.•Weakentitiescanbedeletedautomaticallywhentheirstrongentityisdeleted.•Weakentitiescanbestoredphysicallywiththeirstrongentities.6.20Definetheconceptofaggregation.Givetwoexamplesofwherethisconceptisuseful.Answer:Aggregationisanabstractionthroughwhichrelationshipsaretreatedashigher-levelentities.ThustherelationshipbetweenentitiesAandBistreatedasifitwereanentityC.Someexamplesofthisare:a.Employeesworkforprojects.Anemployeeworkingforaparticularprojectusesvariousmachinery.SeeFigure6.3b.Manufacturershavetie-upswithdistributorstodistributeproducts.Eachtie-uphasspecifiedforitthesetofproductswhicharetobedistributed.SeeFigure6.46.21ConsidertheE-RdiagraminFigure6.31,whichmodelsanonlinebookstore.a.Listtheentitysetsandtheirprimarykeys.b.Supposethebookstoreaddsmusiccassettesandcompactdiskstoitscol-lection.Thesamemusicitemmaybepresentincassetteorcompactdiskformat,withdifferingprices.ExtendtheE-Rdiagramtomodelthisaddi-tion,ignoringtheeffectonshoppingbaskets.c.NowextendtheE-Rdiagram,usinggeneralization,tomodelthecasewhereashoppingbasketmaycontainanycombinationofbooks,musiccassettes,orcompactdisks. 36Chapter6DatabaseDesignandtheE-RModelnamedeadlinenameemployeeworksinprojectrequiresmachinerynameFigure6.3E-Rdiagram:Example1ofaggregation.nametieupdatenamemanufacturertieupdistributordistributeproductnameFigure6.4E-Rdiagram:Example2ofaggregation.Answer:6.22InSection6.5.3,werepresentedaternaryrelationship(repeatedinFigure6.29a)usingbinaryrelationships,asshowninFigure6.29b.ConsiderthealternativeshowninFigure6.29c.Discusstherelativemeritsofthesetwoalternativerep-resentationsofaternaryrelationshipbybinaryrelationships.Answer:ThemodelofFigure6.29cwillnotbeabletorepresentallternaryrelationships.ConsidertheABCrelationshipsetbelow. Exercises37ABC123427483IfABCisbrokenintothreerelationshipssetsAB,BCandAC,thethreewillimplythattherelation(4,2,3)isapartofABC.6.23ConsidertherelationschemasshowninSection6.9.7,whichweregeneratedfromtheE-RdiagraminFigure6.25.Foreachschema,specifywhatforeign-keyconstraints,ifany,shouldbecreated.Answer:NoAnswer.6.24Designageneralizationspecializationhierarchyforamotor-vehiclesalescom-pany.Thecompanysellsmotorcycles,passengercars,vans,andbuses.Justifyyourplacementofattributesateachlevelofthehierarchy.Explainwhytheyshouldnotbeplacedatahigherorlowerlevel.Answer:Figure6.5givesonepossiblehierarchy,therecouldbemanydiffer-entsolutions.Thegeneralizationspecializationhierarchyforthemotor-vehiclecompanyisgiveninthefigure.model,sales-tax-rateandsales-volumeareattributesnecessaryforalltypesofvehicles.Commercialvehiclesattractcommercialvehi-cletax,andeachkindofcommercialvehiclehasapassengercarryingcapacityspecifiedforit.Somekindsofnon-commercialvehiclesattractluxuryvehicletax.Carsalonecanbeofseveraltypes,suchassports-car,sedan,wagonetc.,hencetheattributetype.6.25Explainthedistinctionbetweencondition-definedanduser-definedconstraints.Whichoftheseconstraintscanthesystemcheckautomatically?Explainyouran-swer.Answer:Inageneralizationspecializationhierarchy,itmustbepossibletode-cidewhichentitiesaremembersofwhichlowerlevelentitysets.Inacondition-defineddesignconstraint,membershipinthelowerlevelentity-setsisevalu-atedonthebasisofwhetherornotanentitysatisfiesanexplicitconditionorpredicate.User-definedlower-levelentitysetsarenotconstrainedbyamember-shipcondition;rather,entitiesareassignedtoagivenentitysetbythedatabaseuser.Condition-definedconstraintsalonecanbeautomaticallyhandledbythesys-tem.Wheneveranytupleisinsertedintothedatabase,itsmembershipinthevariouslowerlevelentity-setscanbeautomaticallydecidedbyevaluatingtherespectivemembershippredicates.Similarlywhenatupleisupdated,itsmem-bershipinthevariousentitysetscanbere-evaluatedautomatically.6.26Explainthedistinctionbetweendisjointandoverlappingconstraints.Answer:Inadisjointnessdesignconstraint,anentitycanbelongtonotmorethanonelower-levelentityset.Inoverlappinggeneralizations,thesameen-titymaybelongtomorethanonelower-levelentitysets.Forexample,intheemployee-workteamexampleofthebook,amanagermayparticipateinmorethanonework-team. 38Chapter6DatabaseDesignandtheE-RModelsales-tax-modelsales-volumeratecommercial-vehiclevehicle-tax-rateisamax-luxury-vehicle-passengerstax-ratecommercial-non-commercial-vehiclevehicleisaisamotor-busvancarcycletypeFigure6.5E-Rdiagramofmotor-vehiclesalescompany.customerloancustomer_idloan_numbercustomer_name1..1borrower0..1amountcustomer_streetcustomer_cityFigure6.6UMLequivalentofFigure6.8c.6.27Explainthedistinctionbetweentotalandpartialconstraints.Answer:Inatotaldesignconstraint,eachhigher-levelentitymustbelongtoalower-levelentityset.Thesameneednotbetrueinapartialdesignconstraint.Forinstance,someemployeesmaybelongtonowork-team.6.28DrawtheUMLequivalentsoftheE-RdiagramsoftextFigures6.8c,6.9,6.11,6.12and6.20.Answer:SeeFigures6.6to6.10 Exercises39customeraccountcustomer_idaccount_numbercustomer_name1..10..1balancecustomer_streetcustomer_citydepositoraccess_dateFigure6.7UMLequivalentofFigure6.9employeeemployee_name0..1manageremployee_idworksfortelephone_number1..*workerFigure6.8UMLequivalentofFigure6.11jobtitlelevelworkjobemployeeloanemployee_nameworksonloan_numberemployee_idempworkwork_idworkbranchamountstreetcityFigure6.9UMLequivalentofFigure6.12 40Chapter6DatabaseDesignandtheE-RModelpersonnamestreetcityemployeecustomersalarycredit_ratingofficertellersecretaryofficer_numberstation_numberhours_workedhours_workedFigure6.10UMLequivalentofFigure6.20 CHAPTER7RelationalDatabaseDesignExercises7.17Explainwhatismeantbyrepetitionofinformationandinabilitytorepresentin-formation.Explainwhyeachofthesepropertiesmayindicateabadrelational-databasedesign.Answer:•Repetitionofinformationisaconditioninarelationaldatabasewherethevaluesofoneattributearedeterminedbythevaluesofanotherattributeinthesamerelation,andbothvaluesarerepeatedthroughouttherelation.Thisisabadrelationaldatabasedesignbecauseitincreasesthestoragere-quiredfortherelationanditmakesupdatingtherelationmoredifficult.•Inabilitytorepresentinformationisaconditionwherearelationshipexistsamongonlyapropersubsetoftheattributesinarelation.Thisisbadre-lationaldatabasedesignbecausealltheunrelatedattributesmustbefilledwithnullvaluesotherwiseatuplewithouttheunrelatedinformationcan-notbeinsertedintotherelation.•Lossofinformationisaconditionofarelationaldatabasewhichresultsfromthedecompositionofonerelationintotworelationsandwhichcannotbecombinedtorecreatetheoriginalrelation.Itisabadrelationaldatabasedesignbecausecertainqueriescannotbeansweredusingthereconstructedrelationthatcouldhavebeenansweredusingtheoriginalrelation.7.18Whyarecertainfunctionaldependenciescalledtrivialfunctionaldependen-cies?Answer:Certainfunctionaldependenciesarecalledtrivialfunctionaldepen-denciesbecausetheyaresatisfiedbyallrelations.7.19UsethedefinitionoffunctionaldependencytoarguethateachofArmstrongsaxioms(reflexivity,augmentation,andtransitivity)issound.41 42Chapter7RelationalDatabaseDesignAnswer:Thedefinitionoffunctionaldependencyis:α→βholdsonRifinanylegalrelationr(R),forallpairsoftuplest1andt2inrsuchthatt1[α]=t2[α],itisalsothecasethatt1[β]=t2[β].Reflexivityrule:ifαisasetofattributes,andβ⊆α,thenα→β.Assume∃t1andt2suchthatt1[α]=t2[α]t1[β]=t2[β]sinceβ⊆αα→βdefinitionofFDAugmentationrule:ifα→β,andγisasetofattributes,thenγα→γβ.Assume∃t1,t2suchthatt1[γα]=t2[γα]t1[γ]=t2[γ]γ⊆γαt1[α]=t2[α]α⊆γαt1[β]=t2[β]definitionofα→βt1[γβ]=t2[γβ]γβ=γ∪βγα→γβdefinitionofFDTransitivityrule:ifα→βandβ→γ,thenα→γ.Assume∃t1,t2suchthatt1[α]=t2[α]t1[β]=t2[β]definitionofα→βt1[γ]=t2[γ]definitionofβ→γα→γdefinitionofFD7.20Considerthefollowingproposedruleforfunctionaldependencies:Ifα→βandγ→β,thenα→γ.Provethatthisruleisnotsoundbyshowingarelationrthatsatisfiesα→βandγ→β,butdoesnotsatisfyα→γ.Answer:Considerthefollowingrule:ifA→BandC→B,thenA→C.Thatis,α=A,β=B,γ=C.Thefollowingrelationrisacounterexampletotherule.r:ABCa1b1c1a1b1c2Note:A→BandC→B,(sinceno2tupleshavethesameCvalue,C→Bistruetrivially).However,itisnotthecasethatA→CsincethesameAvalueisintwotuples,buttheCvalueinthosetuplesdisagree.7.21UseArmstrongsaxiomstoprovethesoundnessofthedecompositionrule.Answer:Thedecompositionrule,anditsderivationfromArmstrongsaxiomsaregivenbelow:ifα→βγ,thenα→βandα→γ.α→βγgivenβγ→βreflexivityruleα→βtransitivityruleβγ→γreflexiveruleα→γtransitiverule Exercises437.22UsingthefunctionaldependenciesofPracticeExercise7.6,computeB+.Answer:ComputingB+bythealgorithminFigure7.9westartwithresult={B}.ConsideringFDsoftheformβ→γinF,wefindthattheonlydepen-denciessatisfyingβ⊆resultareB→BandB→D.Thereforeresult={B,D}.NomoredependenciesinFapplynow.ThereforeB+={B,D}7.23ShowthatthefollowingdecompositionoftheschemaRofPracticeExercise7.1isnotalossless-joindecomposition:(A,B,C)(C,D,E).Hint:GiveanexampleofarelationronschemaRsuchthatΠA,B,C(r)ΠC,D,E(r)=rAnswer:Followingthehint,usethefollowingexampleofr:ABCDEa1b1c1d1e1a2b2c1d2e2WithR1=(A,B,C),R2=(C,D,E):a.ΠR1(r)wouldbe:ABCa1b1c1a2b2c1b.ΠR2(r)wouldbe:CDEc1d1e1c1d2e2c.ΠR1(r)ΠR2(r)wouldbe:ABCDEa1b1c1d1e1a1b1c1d2e2a2b2c1d1e1a2b2c1d2e2Clearly,ΠR1(r)ΠR2(r)=r.Therefore,thisisalossyjoin.7.24Listthethreedesigngoalsforrelationaldatabases,andexplainwhyeachisde-sirable.Answer:Thethreedesigngoalsarelossless-joindecompositions,dependencypreservingdecompositions,andminimizationofrepetitionofinformation.They 44Chapter7RelationalDatabaseDesignresult:=∅;/*fdcountisanarraywhoseithelementcontainsthenumberofattributesontheleftsideoftheithFDthatarenotyetknowntobeinα+*/fori:=1to|F|dobeginletβ→γdenotetheithFD;fdcount[i]:=|β|;end/*appearsisanarraywithoneentryforeachattribute.TheentryforattributeAisalistofintegers.EachintegerionthelistindicatesthatAappearsontheleftsideoftheithFD*/foreachattributeAdobeginappears[A]:=NIL;fori:=1to|F|dobeginletβ→γdenotetheithFD;ifA∈βthenadditoappears[A];endendaddin(α);return(result);procedureaddin(α);foreachattributeAinαdobeginifA∈resultthenbeginresult:=result∪{A};foreachelementiofappears[A]dobeginfdcount[i]:=fdcount[i]−1;iffdcount[i]:=0thenbeginletβ→γdenotetheithFD;addin(γ);endendendendFigure7.19.Analgorithmtocomputeα+. Exercises45aredesirablesowecanmaintainanaccuratedatabase,checkcorrectnessofup-datesquickly,andusethesmallestamountofspacepossible.7.25Givealossless-joindecompositionintoBCNFofschemaRofExercise7.1.Answer:FromExercise7.6,weknowthatB→Disnontrivialandthelefthandsideisnotasuperkey.BythealgorithmofFigure7.12wederivetherelations{(A,B,C,E),(B,D)}.ThisisinBCNF.7.26Indesigningarelationaldatabase,whymightwechooseanon-BCNFdesign?Answer:BCNFisnotalwaysdependencypreserving.Therefore,wemaywanttochooseanothernormalform(specifically,3NF)inordertomakecheckingde-pendencieseasierduringupdates.Thiswouldavoidjoinstocheckdependen-ciesandincreasesystemperformance.7.27Givealossless-join,dependency-preservingdecompositioninto3NFofschemaRofPracticeExercise7.1.Answer:FirstwenotethatthedependenciesgiveninPracticeExercise7.1formacanonicalcover.GeneratingtheschemafromthealgorithmofFigure7.13wegetR={(A,B,C),(C,D,E),(B,D),(E,A)}.Schema(A,B,C)containsacandidatekey.ThereforeRisathirdnormalformdependency-preservinglossless-joindecomposition.NotethattheoriginalschemaR=(A,B,C,D,E)isalreadyin3NF.Thus,itwasnotnecessarytoapplythealgorithmaswehavedoneabove.Thesingleoriginalschemaistriviallyalosslessjoin,dependency-preservingdecomposi-tion.7.28Giventhethreegoalsofrelational-databasedesign,isthereanyreasontodesignadatabaseschemathatisin2NF,butisinnohigher-ordernormalform?(SeePracticeExercise7.15forthedefinitionof2NF.)Answer:Thethreedesigngoalsofrelationaldatabasesaretoavoid•Repetitionofinformation•Inabilitytorepresentinformation•Lossofinformation.2NFdoesnotprohibitasmuchrepetitionofinformationsincetheschema(A,B,C)withdependenciesA→BandB→Cisallowedunder2NF,althoughthesame(B,C)paircouldbeassociatedwithmanyAvalues,needlesslydupli-catingCvalues.Toavoidthiswemustgoto3NF.Repetitionofinformationisallowedin3NFinsomebutnotallofthecaseswhereitisallowedin2NF.Thus,ingeneral,3NFreducesrepetitionofinformation.Sincewecanalwaysachievealosslessjoin3NFdecomposition,thereisnolossofinformationneededingoingfrom2NFto3NF.Notethatthedecomposition{(A,B),(B,C)}isadependency-preservingandlossless-loin3NFdecompositionoftheschema(A,B,C).However,incasewechoosethisdecomposition,retrievinginformationabouttherelationshipbe- 46Chapter7RelationalDatabaseDesigntweenA,BandCrequiresajoinoftworelations,whichisavoidedinthecor-responding2NFdecomposition.Thus,thedecisionofwhichnormalformtochoosedependsuponhowthecostofdependencycheckingcompareswiththecostofthejoins.Usually,the3NFwouldbepreferred.Dependencychecksneedtobemadewitheveryinsertorupdatetotheinstancesofa2NFschema,whereas,onlysomequerieswillrequirethejoinofinstancesofa3NFschema.7.29Givenarelationalschemar(A,B,C,D),doesAMVDBClogicallyimplyAMVDBandAMVDC?Ifyesproveit,elsegiveacounterexample.Answer:Noanswer7.30Explainwhy4NFisanormalformmoredesirablethanBCNF.Answer:4NFismoredesirablethanBCNFbecauseitreducestherepetitionofin-formation.IfweconsideraBCNFschemanotin4NF(seePracticeExercise7.16),weobservethatdecompositioninto4NFdoesnotloseinformationprovidedthatalosslessjoindecompositionisused,yetredundancyisreduced. CHAPTER8ApplicationDesignandDevelopmentExercises8.8WriteaservletandassociatedHTMLcodeforthefollowingverysimpleappli-cation:Auserisallowedtosubmitaformcontainingavalue,sayn,andshouldgetaresponsecontainingn“*”symbols.Answer:Noanswer.8.9WriteaservletandassociatedHTMLcodeforthefollowingsimpleapplication:Auserisallowedtosubmitaformcontaininganumber,sayn,andshouldgetaresponsesayinghowmanytimesthevaluenhasbeensubmittedpreviously.Thenumberoftimeseachvaluehasbeensubmittedpreviouslyshouldbestoredinadatabase.Answer:Noanswer.8.10Writeaservletthatauthenticatesauser(basedonusernamesandpasswordsstoredinadatabaserelation),andsetsasessionvariablecalleduseridafterau-thentication.Answer:Noanswer.8.11WhatisanSQLinjectionattack?Explainhowitworks,andwhatprecautionsmustbetakentopreventSQLinjectionattacks.Answer:Noanswer.8.12Writepseudocodetomanageaconnectionpool.Yourpseudocodemustincludeafunctiontocreateapool(providingadatabaseconnectionstring,databaseusernameandpasswordasparameters),afunctiontorequestaconnectionfromthepool,aconnectiontoreleaseaconnectiontothepool,andafunctiontoclosetheconnectionpool.Answer:Noanswer.47 48Chapter8ApplicationDesignandDevelopment8.13Supposetherearetworelationsrands,suchthattheforeignkeyBofrrefer-encestheprimarykeyAofs.Describehowthetriggermechanismcanbeusedtoimplementtheondeletecascadeoption,whenatupleisdeletedfroms.Answer:Wedefinetriggersforeachrelationwhoseprimary-keyisreferredtobytheforeign-keyofsomeotherrelation.Thetriggerwouldbeactivatedwhen-everatupleisdeletedfromthereferred-torelation.Theactionperformedbythetriggerwouldbetovisitallthereferringrelations,anddeleteallthetuplesinthemwhoseforeign-keyattributevalueisthesameastheprimary-keyattributevalueofthedeletedtupleinthereferred-torelation.Thesesetoftriggerswilltakecareoftheondeletecascadeoperation.8.14Theexecutionofatriggercancauseanotheractiontobetriggered.Mostdatabasesystemsplacealimitonhowdeepthenestingcanbe.Explainwhytheymightplacesuchalimit.Answer:Noanswer.8.15Explainwhy,whenamanager,sayMary,grantsanauthorization,thegrantshouldbedonebythemanagerrole,ratherthanbytheuserMary.Answer:Noanswer.8.16SupposeuserA,whohasallauthorizationsonarelationr,grantsselectonrelationrtopublicwithgrantoption.SupposeuserBthengrantsselectonrtoA.Doesthiscauseacycleintheauthorizationgraph?Explainwhy.Answer:Noanswer.8.17Makealistofsecurityconcernsforabank.Foreachitemonyourlist,statewhetherthisconcernrelatestophysicalsecurity,humansecurity,operating-systemsecurity,ordatabasesecurity.Answer:Noanswer.8.18Databasesystemsthatstoreeachrelationinaseparateoperating-systemfilemayusetheoperatingsystemssecurityandauthorizationscheme,insteadofdefiningaspecialschemethemselves.Discussanadvantageandadisadvantageofsuchanapproach.Answer:Noanswer.8.19OraclesVPDmechanismimplementsrow-levelsecuritybyaddingpredicatestothewhereclauseofeachquery.Giveanexampleofapredicatethatcouldbeusedtoimplementrow-levelsecurity,andthreequerieswiththefollowingproperties:a.Forthefirstquery,thequerywiththeaddedpredicategivesthesameresultasthesameastheoriginalquery.b.Forthesecondquery,thequerywiththeaddedpredicatesgivesaresultthatisalwaysasubsetoftheoriginalqueryresult.c.Forthethirdquery,thequerywiththeaddedpredicategiveincorrectan-swers. Exercises49Answer:Noanswer.8.20Whataretwoadvantagesofencryptingdatastoredinthedatabase?Answer:Noanswer.8.21Supposeyouwishtocreateanaudittrailofchangestotheaccountrelation.a.Definetriggerstocreateanaudittrail,loggingtheinformationintoare-lationcalled,forexample,accounttrail.Theloggedinformationshouldin-cludetheuser-id(assumeafunctionuserid()providesthisinformation)andatimestamp,inadditiontooldandnewvalues.Youmustalsoprovidetheschemaoftheaccounttrailrelation.b.Cantheaboveimplementationguaranteethatupdatesmadebyamaliciousdatabaseadministrator(orsomeonewhomanagestogettheadministra-torspassword)willbeintheaudittrail?Explainyouranswer.Answer:Noanswer.8.22HackersmaybeabletofoolyouintobelievingthattheirWebsiteisactuallyaWebsite(suchasabankorcreditcardWebsite)thatyoutrust.Thismaybedonebymisleadingemail,orevenbybreakingintothenetworkinfrastructureandre-routingnetworktrafficdestinedfor,saymybank.com,tothehackerssite.Ifyouenteryourusernameandpasswordonthehackerssite,thesitecanrecordit,anduseitlatertobreakintoyouraccountattherealsite.WhenyouuseaURLsuchashttps://mybank.com,thetheHTTPSprotocolisusedtopreventsuchattacks.Explainhowtheprotocolmightusedigitalcertificatestoverifyauthenticityofthesite.Answer:Noanswer.8.23Explainwhatisachallenge-responsesystemforauthentication.Whyisitmoresecurethanatraditionalpassword-basedsystem?Answer:Noanswer. CHAPTER9Object-BasedDatabasesExercises9.7RedesignthedatabaseofExercise9.2intofirstnormalformandfourthnormalform.Listanyfunctionalormultivalueddependenciesthatyouassume.Alsolistallreferential-integrityconstraintsthatshouldbepresentinthefirst-andfourth-normal-formschemas.Answer:Toputtheschemaintofirstnormalform,weflattenalltheattributesintoasinglerelationschema.Employee-details=(ename,cname,bday,bmonth,byear,stype,xyear,xcity)Werenametheattributesforthesakeofclarity.cnameisChildren.name,andbday,bmonth,byeararetheBirthdayattributes.stypeisSkills.type,andxyearandxcityaretheExamsattributes.TheFDsandmultivalueddependenciesweassumeare:-ename,cname→bday,bmonth,byearename→→cname,bday,bmonth,byearename,stype→→xyear,xcityTheFDcapturesthefactthatachildhasauniquebirthday,undertheassump-tionthatoneemployeecannothavetwochildrenofthesamename.TheMVDscapturethefactthereisnorelationshipbetweenthechildrenofanemployeeandhisorherskills-information.Theredesignedschemainfourthnormalformis:-Employee=(ename)Child=(ename,cname,bday,bmonth,byear)Skill=(ename,stype,xyear,xcity)51 52Chapter9Object-BasedDatabasesenamewillbetheprimarykeyofEmployee,and(ename,cname)willbethepri-marykeyofChild.TheenameattributeisaforeignkeyinChildandinSkill,referringtotheEmployeerelation.9.8ConsidertheschemafromPracticeExercise9.2.a.GiveSQL:2003DDLstatementstocreatearelationEmpAwhichhasthesameinformationasEmp,butwheremultisetvaluedattributesChildrenSet,Skills-SetandExamsSetarereplacedbyarrayvaluedattributesChildrenArray,Skill-sArrayandExamsArray.b.WriteaquerytoconvertdatafromtheschemaofEmptothatofEmpA,withthearrayofchildrensortedbybirthday,thearrayofskillsbytheskilltypeandthearrayofexamsbytheyear.c.WriteanSQLstatementtoupdatetheEmprelationbyaddingachildJeb,withabirthdateofFebruary5,2001,totheemployeenamedGeorge.d.WriteanSQLstatementtoperformthesameupdateasabovebutontheEmpArelation.Makesurethatthearrayofchildrenremainssortedbyyear.Answer:Noanswer9.9Considertheschemasforthetablepeople,andthetablesstudentsandteachers,whichwerecreatedunderpeople,inSection9.4.Givearelationalschemainthirdnormalformthatrepresentsthesameinformation.Recalltheconstraintsonsub-tables,andgiveallconstraintsthatmustbeimposedontherelationalschemasothateverydatabaseinstanceoftherelationalschemacanalsoberepresentedbyaninstanceoftheschemawithinheritance.Answer:Acorrespondingrelationalschemainthirdnormalformisgivenbelow:-People=(name,address)Students=(name,degree,student-department)Teachers=(name,salary,teacher-department)nameistheprimarykeyforallthethreerelations,anditisalsoaforeignkeyreferringtoPeople,forbothStudentsandTeachers.InsteadofplacingonlythenameattributeofPeopleinStudentsandTeachers,bothitsattributescanbeincluded.Inthatcase,therewillbeaslightchange,namely(name,address)willbecometheforeignkeyinStudentsandTeachers.Theprimarykeyswillremainthesameinalltables.9.10Explainthedistinctionbetweenatypexandareferencetyperef(x).Underwhatcircumstanceswouldyouchoosetouseareferencetype?Answer:Ifthetypeofanattributeisx,thenineachtupleofthetable,corre-spondingtothatattribute,thereisanactualobjectoftypex.Ifitstypeisref(x),thenineachtuple,correspondingtothatattribute,thereisareferencetosomeobjectoftypex.Wechooseareferencetypeforanattribute,ifthatattributesintendedpurposeistorefertoanindependentobject. Exercises539.11GiveanSQL:1999schemadefinitionoftheE-RdiagraminFigure9.7,whichcon-tainsspecializations,usingsubtypesandsubtables.Answer:createtypePerson(namevarchar(30),streetvarchar(15),cityvarchar(15))createtypeEmployeeunderPerson(salaryinteger)createtypeCustomerunderPerson(credit-ratinginteger)createtypeOfficerunderEmployee(office-numberinteger)createtypeTellerunderEmployee(station-numberinteger,hours-workedinteger)createtypeSecretaryunderEmployee(hours-workedinteger)createtablepersonofPersoncreatetableemployeeofEmployeeunderpersoncreatetablecustomerofCustomernunderpersoncreatetableofficerofOfficerunderemployeecreatetabletellerofTellerunderemployeecreatetablesecretaryofSecretaryunderemployee9.12SupposeaJDOdatabasehadanobjectA,whichreferencesobjectB,whichinturnreferencesobjectC.Assumeallobjectsareondiskinitially.SupposeaprogramfirstdereferencesA,thendereferencesBbyfollowingthereferencefromA,andthenfinallydereferencesC.Showtheobjectsthatarerepresentedinmemoryaftereachdereference,alongwiththeirstate(holloworfilled,andvaluesintheirreferencefields).Answer:Noanswer. CHAPTER10XMLExercises10.10Show,bygivingaDTD,howtorepresenttheNon-1NFbooksrelationfromSec-tion9.2,usingXML.Answer:]>10.11WritethefollowingqueriesinXQuery,assumingtheDTDfromPracticeExer-cise10.2.a.FindthenamesofallemployeeswhohaveachildwhohasabirthdayinMarch.b.Findthoseemployeeswhotookanexaminationfortheskilltype“typing”inthecity“Dayton”.c.ListallskilltypesinEmp.Answer:a.FindthenamesofallemployeeswhohaveachildwhohasabirthdayinMarch.55 56Chapter10XMLfor$ein/db/emp,$mindistinct($e/children/birthday/month)where$m=Marchreturn$e/enameb.Findthoseemployeeswhotookanexaminationfortheskilltype“typing”inthecity“Dayton”.for$ein/db/emp$sin$e/skills[type=typing]$examin$s/examswhere$exam/city=Daytonreturn$e/enamec.ListallskilltypesinEmp.for$tindistinct(/db/emp/skills/type)return$t10.12ConsidertheXMLdatashowninFigure10.2.Supposewewishtofindpurchaseordersthatorderedtwoormorecopiesofthepartwithidentifier123.Considerthefollowingattempttosolvethisproblem:for$pinpurchaseorderwhere$p/part/id=123and$p/part/quantity>=2return$pExplainwhythequerymayreturnsomepurchaseordersthatorderlessthantwocopiesofpart123.Giveacorrectversionoftheabovequery.Answer:Noanswer10.13GiveaqueryinXQuerytoflipthenestingofdatafromExercise10.10.Thatis,attheoutermostlevelofnestingtheoutputmusthaveelementscorrespondingtoauthors,andeachsuchelementmusthavenestedwithinititemscorrespond-ingtoallthebookswrittenbytheauthor.Answer:Noanswer10.14GivetheDTDforanXMLrepresentationoftheinformationinFigure6.31.Cre-ateaseparateelementtypetorepresenteachrelationship,butuseIDandIDREFtoimplementprimaryandforeignkeys.Answer:TheanswerisgiveninFigure10.1.10.15GiveanXMLSchemarepresentationoftheDTDfromExercise10.14.Answer:Noanswer10.16WritequeriesinXQueryonthebibliographyDTDfragmentinFigure10.15,todothefollowing.a.Findallauthorswhohaveauthoredabookandanarticleinthesameyear.b.Displaybooksandarticlessortedbyyear.c.Displaybookswithmorethanoneauthor.d.Findallbooksthatcontaintheword“database”intheirtitleandtheword“Hank”inanauthorsname(whetherfirstorlast). Exercises57]>Figure10.1XMLDTDforBookstore 58Chapter10XML···similarPCDATAdeclarationsforyear,publisher,place,journal,year,number,volume,pages,last-nameandfirst-name]>Figure10.15.DTDforbibliographicaldata.Answer:a.Findallauthorswhohaveauthoredabookandanarticleinthesameyear.for$aindistinct(/bib/book/author),$yin/bib/book[author=$a]/year,$artin/bib/article[author=$aandyear=$y]return$ab.Displaybooksandarticlessortedbyyear.for$ain((/bib/book)|(/bib/article))return$asortby(year)c.Displaybookswithmorethanoneauthor.for$bin((/bib/book[author/count()>1])return$bd.Findallbooksthatcontaintheword“database”intheirtitleandtheword“Hank”inanauthorsname(whetherfirstorlast).NoAnswer.10.17GivearelationalmappingoftheXMLpurchaseorderschemaillustratedinFigure10.2,usingtheapproachdescribedinSection10.6.2.3.Suggesthowtoremoveredundancyintherelationalschema,ifitemidenti-fiersfunctionallydeterminethedescriptionandpurchaseandsuppliernamesfunctionallydeterminethepurchaseandsupplieraddress,respectively.Answer:Noanswer10.18WritequeriesinSQL/XMLtoconvertbankdatafromtherelationalschemawehaveusedinearlierchapterstothebank-1andbank-2XMLschemas.(Forthebank-2schema,youmayassumethatthecustomerrelationhasanextraattributecustomerid.)Answer:Noanswer10.19AsinExercise10.18,writequeriestoconvertbankdatatothebank-1andbank-2XMLschemas,butthistimebywritingXQueryqueriesonthedefaultSQL/XML Exercises59databasetoXMLmapping.Answer:Noanswer10.20OnewaytoshredanXMLdocumentistouseXQuerytoconverttheschematoanSQL/XMLmappingofthecorrespondingrelationalschema,andthenusetheSQL/XMLmappinginthebackwarddirectiontopopulatetherelation.Asanillustration,giveanXQueryquerytoconvertdatafromthebank-1XMLschematotheSQL/XMLschemashowninFigure10.14.Answer:Noanswer10.21ConsidertheexampleXMLschemafromSection10.3.2,andwriteXQueryque-riestocarryoutthefollowingtasks.a.CheckifthekeyconstraintshowninSection10.3.2holds.b.CheckifthekeyrefconstraintshowninSection10.3.2holds.Answer:Noanswer10.22ConsiderPracticeExercise10.7,andsupposethatauthorscouldalsoappearastop-levelelements.Whatchangewouldhavetobedonetotherelationalschema?Answer:Noanswer CHAPTER11StorageandFileStructureExercises11.8Listthephysicalstoragemediaavailableonthecomputersyouuseroutinely.Givethespeedwithwhichdatacanbeaccessedoneachmedium.Answer:Youranswerwillbebasedonthecomputersandstoragemediathatyouuse.Typicalexampleswouldbeharddisk,floppydisksandCD-ROMdrives.11.9Howdoestheremappingofbadsectorsbydiskcontrollersaffectdata-retrievalrates?Answer:Remappingofbadsectorsbydiskcontrollersdoesreducedatare-trievalratesbecauseofthelossofsequentialityamongstthesectors.Butthatisbetterthanthelossofdataincaseofnoremapping!11.10RAIDsystemstypicallyallowyoutoreplacefaileddiskswithoutstoppingac-cesstothesystem.Thus,thedatainthefaileddiskmustberebuiltandwrittentothereplacementdiskwhilethesystemisinoperation.WithwhichoftheRAIDlevelsistheamountofinterferencebetweentherebuildandongoingdiskaccessesleast?Explainyouranswer.Answer:RAIDlevel1(mirroring)istheonewhichfacilitatesrebuildingofafaileddiskwithminimuminterferencewiththeon-goingdiskaccesses.Thisisbecauserebuildinginthiscaseinvolvescopyingdatafromjustthefaileddisksmirror.IntheotherRAIDlevels,rebuildinginvolvesreadingtheentirecontentsofalltheotherdisks.11.11Explainwhytheallocationofrecordstoblocksaffectsdatabase-systemperfor-mancesignificantly.Answer:Ifweallocaterelatedrecordstoblocks,wecanoftenretrievemost,orall,oftherequestedrecordsbyaquerywithonediskaccess.Diskaccesses61 62Chapter11StorageandFileStructuretendtobethebottlenecksindatabases;sincethisallocationstrategyreducesthenumberofdiskaccessesforagivenoperation,itsignificantlyimprovesperformance.11.12Ifpossible,determinethebuffer-managementstrategyusedbytheoperatingsystemrunningonyourlocalcomputersystem,andwhatmechanismsitpro-videstocontrolreplacementofpages.Discusshowthecontrolonreplacementthatitprovideswouldbeusefulfortheimplementationofdatabasesystems.Answer:ThetypicalOSusesLRUforbufferreplacement.Thisisoftenabadstrategyfordatabases.AsexplainedinSection11.5.2ofthetext,MRUisthebeststrategyfornestedloopjoin.Ingeneralnosinglestrategyhandlesallsce-narioswell,andideallythedatabasesystemshouldbegivenitsownbuffercacheforwhichthereplacementpolicytakesintoaccountalltheperformancerelatedissues.11.13Inthesequentialfileorganization,whyisanoverflowblockusedevenifthereis,atthemoment,onlyoneoverflowrecord?Answer:Anoverflowblockisusedinsequentialfileorganizationbecauseablockisthesmallestspacewhichcanbereadfromadisk.Therefore,usinganysmallerregionwouldnotbeusefulfromaperformancestandpoint.Thespacesavedbyallocatingdiskstorageinrecordunitswouldbeovershadowedbytheperformancecostofallowingblockstocontainrecordsofmultiplefiles.11.14Listtwoadvantagesandtwodisadvantagesofeachofthefollowingstrategiesforstoringarelationaldatabase:a.Storeeachrelationinonefile.b.Storemultiplerelations(perhapseventheentiredatabase)inonefile.Answer:a.Advantagesofstoringarelationasafileincludeusingthefilesystempro-videdbytheOS,thussimplifyingtheDBMS,butincursthedisadvantageofrestrictingtheabilityoftheDBMStoincreaseperformancebyusingmoresophisticatedstoragestructures.b.Byusingonefilefortheentiredatabase,thesecomplexstructurescanbeimplementedthroughtheDBMS,butthisincreasesthesizeandcomplexityoftheDBMS.11.15GiveanormalizedversionoftheIndex-metadatarelation,andexplainwhyus-ingthenormalizedversionwouldresultinworseperformance.Answer:TheIndex-metadatarelationcanbenormalizedasfollowsIndex-metadata(index-name,relation-name,index-type,attrib-set)Attribset-metadata(relation-name,attrib-set,attribute-name)Thoughthenormalizedversionwillhavelessspacerequirements,itwillre-quireextradiskaccessestoreadAttribset-metadataeverytimeanindexhastobeaccessed.Thus,itwillleadtoworseperformance. Exercises6311.16Ifyouhavedatathatshouldnotbelostondiskfailure,andthedataarewriteintensive,howwouldyoustorethedata?Answer:Noanswer.11.17Inearliergenerationdisksthenumberofsectorspertrackwasthesameacrossalltracks.Currentgenerationdiskshavemoresectorspertrackonoutertracks,andfewersectorspertrackoninnertracks(sincetheyareshorterinlength).Whatistheeffectofsuchachangeoneachofthethreemainindicatorsofdiskspeed?Answer:Noanswer.11.18Standardbuffermanagersassumeeachpageisofthesamesizeandcoststhesametoread.Considerabuffermanagerthat,insteadofLRU,usestherateofreferencetoobjects,thatis,howoftenanobjecthasbeenaccessedinthelastnseconds.Supposewewanttostoreinthebufferobjectsofvaryingsizes,andvaryingreadcosts(suchasWebpages,whosereadcostdependsonthesitefromwhichtheyarefetched).Suggesthowabuffermanagermaychoosewhichpagetoevictfromthebuffer.Answer:Noanswer. CHAPTER12IndexingandHashingExercises12.13Whenisitpreferabletouseadenseindexratherthanasparseindex?Explainyouranswer.Answer:Itispreferabletouseadenseindexinsteadofasparseindexwhenthefileisnotsortedontheindexedfield(suchaswhentheindexisasecondaryindex)orwhentheindexfileissmallcomparedtothesizeofmemory.12.14Whatisthedifferencebetweenaclusteringindexandasecondaryindex?Answer:Theclusteringindexisonthefieldwhichspecifiesthesequentialorderofthefile.Therecanbeonlyoneclusteringindexwhiletherecanbemanysecondaryindices.12.15ForeachB+-treeofPracticeExercise12.3,showthestepsinvolvedinthefol-lowingqueries:a.Findrecordswithasearch-keyvalueof11.b.Findrecordswithasearch-keyvaluebetween7and17,inclusive.Answer:WiththestructureprovidedbythesolutiontoPracticeExercise12.3a:a.Findrecordswithavalueof11i.Searchthefirstlevelindex;followthefirstpointer.ii.Searchnextlevel;followthethirdpointer.iii.Searchleafnode;followfirstpointertorecordswithkeyvalue11.b.Findrecordswithvaluebetween7and17(inclusive)i.Searchtopindex;followfirstpointer.ii.Searchnextlevel;followsecondpointer.65 66Chapter12IndexingandHashingiii.Searchthirdlevel;followsecondpointertorecordswithkeyvalue7,andafteraccessingthem,returntoleafnode.iv.Followfourthpointertonextleafblockinthechain.v.Followfirstpointertorecordswithkeyvalue11,thenreturn.vi.Followsecondpointertorecordswithwithkeyvalue17.WiththestructureprovidedbythesolutiontoPracticeExercise12.3b:a.Findrecordswithavalueof11i.Searchtoplevel;followsecondpointer.ii.Searchnextlevel;followsecondpointertorecordswithkeyvalue11.b.Findrecordswithvaluebetween7and17(inclusive)i.Searchtoplevel;followsecondpointer.ii.Searchnextlevel;followfirstpointertorecordswithkeyvalue7,thenreturn.iii.Followsecondpointertorecordswithkeyvalue11,thenreturn.iv.Followthirdpointertorecordswithkeyvalue17.WiththestructureprovidedbythesolutiontoPracticeExercise12.3c:a.Findrecordswithavalueof11i.Searchtoplevel;followsecondpointer.ii.Searchnextlevel;followfirstpointertorecordswithkeyvalue11.b.Findrecordswithvaluebetween7and17(inclusive)i.Searchtoplevel;followfirstpointer.ii.Searchnextlevel;followfourthpointertorecordswithkeyvalue7,thenreturn.iii.Followeighthpointertonextleafblockinchain.iv.Followfirstpointertorecordswithkeyvalue11,thenreturn.v.Followsecondpointertorecordswithkeyvalue17.12.16hesolutionpresentedinSection12.5.3todealwithnon-uniquesearchkeysaddedanextraattributetothesearchkey.WhateffectdoesthischangehaveontheheightoftheB+-tree?Answer:Noanswer.12.17Explainthedistinctionbetweenclosedandopenhashing.Discusstherelativemeritsofeachtechniqueindatabaseapplications.Answer:Openhashingmayplacekeyswiththesamehashfunctionvalueindifferentbuckets.Closedhashingalwaysplacessuchkeystogetherinthesamebucket.Thusinthiscase,differentbucketscanbeofdifferentsizes,thoughtheimplementationmaybebylinkingtogetherfixedsizebucketsusingoverflowchains.Deletionisdifficultwithopenhashingasallthebucketsmayhavetoinspectedbeforewecanascertainthatakeyvaluehasbeendeleted,whereasinclosedhashingonlythatbucketwhoseaddressisobtainedbyhashingthekeyvalueneedbeinspected.Deletionsaremorecommonindatabasesandhenceclosedhashingismoreappropriateforthem.Forasmall,staticsetofdatalookupsmaybemoreefficientusingopenhashing.Thesymboltableofacompilerwouldbeagoodexample. Exercises6712.18Whatarethecausesofbucketoverflowinahashfileorganization?Whatcanbedonetoreducetheoccurrenceofbucketoverflows?Answer:Thecausesofbucketoverfloware:-a.Ourestimateofthenumberofrecordsthattherelationwillhavewastoolow,andhencethenumberofbucketsallottedwasnotsufficient.b.Skewinthedistributionofrecordstobuckets.Thismayhappeneitherbe-causetherearemanyrecordswiththesamesearchkeyvalue,orbecausethethehashfunctionchosendidnothavethedesirablepropertiesofuni-formityandrandomness.Toreducetheoccurrenceofoverflows,wecan:-a.Choosethehashfunctionmorecarefully,andmakebetterestimatesoftherelationsize.b.Iftheestimatedsizeoftherelationisnrandnumberofrecordsperblockisfr,allocate(nr/fr)∗(1+d)bucketsinsteadof(nr/fr)buckets.Heredisafudgefactor,typicallyaround0.2.Somespaceiswasted:About20percentofthespaceinthebucketswillbeempty.Butthebenefitisthatsomeoftheskewishandledandtheprobabilityofoverflowisreduced.12.19Whyisahashstructurenotthebestchoiceforasearchkeyonwhichrangequeriesarelikely?Answer:Arangequerycannotbeansweredefficientlyusingahashindex,wewillhavetoreadallthebuckets.Thisisbecausekeyvaluesintherangedonotoccupyconsecutivelocationsinthebuckets,theyaredistributeduniformlyandrandomlythroughoutallthebuckets.12.20SupposethereisarelationR(A,B,C),withaB+-treeindexwithsearchkey(A,B).a.Whatistheworstcasecostoffindingrecordssatisfying10(selectmax(balance)fromaccount)and1.5∗balance<=(selectmax(balance)fromaccount))union(select3,count(∗)fromaccountwhere1.5∗balance>(selectmax(balance)fromaccount))18.12Constructadecisiontreeclassifierwithbinarysplitsateachnode,usingtu-plesinrelationr(A,B,C)shownbelowastrainingdata;attributeCdenotestheclass.Showthefinaltree,andwitheachnodeshowthebestsplitforeachattributealongwithitsinformationgainvalue.(1,2,a),(2,1,a),(2,5,b),(3,3,b),(3,6,b),(4,5,b),(5,5,c),(6,3,b),(6,7,c)Answer:Noanswer.18.13Supposehalfofallthetransactionsinaclothesshoppurchasejeans,andonethirdofalltransactionsintheshoppurchaseT-shirts.SupposealsothathalfofthetransactionsthatpurchasejeansalsopurchaseT-shirts.Writedownallthe(nontrivial)associationrulesyoucandeducefromtheaboveinformation,givingsupportandconfidenceofeachrule. 96Chapter18DataAnalysisandMiningAnswer:Therulesareasfollows.Thelastrulecanbededucedfromtheprevi-ousones.RuleSupportConf.∀transactionsT,true⇒buys(T,jeans)50%50%∀transactionsT,true⇒buys(T,t-shirts)33%33%∀transactionsT,buys(T,jeans)⇒buys(T,t-shirts)25%50%∀transactionsT,buys(T,t-shirts)⇒buys(T,jeans)25%75%18.14Considertheproblemoffindinglargeitemsets.a.Describehowtofindthesupportforagivencollectionofitemsetsbyusingasinglescanofthedata.Assumethattheitemsetsandassociatedinforma-tion,suchascounts,willfitinmemory.b.Supposeanitemsethassupportlessthanj.Showthatnosupersetofthisitemsetcanhavesupportgreaterthanorequaltoj.Answer:a.Let{S1,S2,...,Sn}bethecollectionofitem-setsforwhichwewanttofindthesupport.Associateacountercount(Si)witheachitem-setSi.Initializeeachcountertozero.Nowexaminethetransactionsone-by-one.LetS(T)betheitem-setforatransactionT.Foreachitem-setSithatisasubsetofS(T),incrementthecorrespondingcountercount(Si).Whenallthetransactionshavebeenscanned,thevaluesofcount(Si)foreachiwillgivethesupportforitem-setSi.b.LetAbeanitem-set.Consideranyitem-setBwhichisasupersetofA.LetτAandτBbethesetsoftransactionsthatpurchaseallitemsinAandallitemsinB,respectively.Forexample,supposeAis{a,b,c},andBis{a,b,c,d}.AtransactionthatpurchasesallitemsfromBmustalsohavepurchasedallitemsfromA(sinceA⊆B).Thus,everytransactioninτBisalsoinτA.ThisimpliesthatthenumberoftransactionsinτBisatmostthenumberoftransactionsinτA.Inotherwords,thesupportforBisatmostthesupportforA.Thus,ifanyitem-sethassupportlessthanj,allsupersetsofthisitem-sethavesupportlessthanj.18.15Createasmallexampleofasetoftransactionsshowingthatthatalthoughmanytransactionscontaintwoitems,thatistheitemsetcontainingthetwoitemshasahighsupport,purchaseofoneoftheitemsmayhaveanegativecorrelationwithpurchaseoftheother.Answer:Noanswer.18.16Theorganizationofparts,chapters,sectionsandsubsectionsinabookisre-latedtoclustering.Explainwhy,andtowhatformofclustering.Answer:Noanswer. Exercises9718.17Suggesthowpredictiveminingtechniquescanbeusedbyasportsteam,usingyourfavoritesportasanexample.Answer:Noanswer. CHAPTER19InformationRetrievalExercises19.6Usingasimpledefinitionoftermfrequencyasthenumberofoccurrencesoftheterminadocument,givetheTF-IDFscoresofeachterminthesetofdocumentsconsistingofthisandthenextexercise.Answer:Noanswer.19.7Createasmallexampleofa4smalldocumentseachwithaPageRank,andcreateinvertedlistsforthedocumentssortedbythePageRank.YoudonotneedtocomputePageRank,justassumesomevaluesforeachpage.Answer:Noanswer.19.8Supposeyouwishtoperformkeywordqueryingonasetoftuplesinadatabase,whereeachtuplehasonlyafewattributes,eachcontainingonlyafewwords.Doestheconceptoftermfrequencymakesenseinthiscontext?Andthatofinversedocumentfrequency?Explainyouranswer.AlsosuggesthowyoucandefinethesimilarityoftwotuplesusingTF-IDFconcepts.Answer:Noanswer.19.9WebsitesthatwanttogetsomepublicitycanjoinaWebring,wheretheycreatelinkstoothersitesinthering,inexchangeforothersitesintheringcreatinglinkstotheirsite.Whatistheeffectofsuchringsonpopularityrankingtech-niquessuchasPageRank?Answer:Noanswer.19.10TheGooglesearchengineprovideafeaturewherebyWebsitescandisplayad-vertisementssuppliedbyGoogle.Theadvertisementssuppliedarebasedonthecontentsofthepage.SuggesthowGooglemightchoosewhichadvertise-mentstosupplyforapage,giventhepagecontents.Answer:Noanswer.99 100Chapter19InformationRetrieval19.11Onewaytocreateakeyword-specificversionofPageRankistomodifytheran-domjumpsuchthatajumpisonlypossibletopagescontainingthekeyword.Thuspagesthatdonotcontainthekeywordbutareclose(intermsoflinks)topagesthatcontainthekeywordalsogetanon-zerorankforthatkeyword.a.Giveequationsdefiningsuchakeyword-specificversionofPageRank.b.Giveaformulaforcomputingtherelevanceofapagetoaquerycontainingmultiplekeywords.Answer:Noanswer.19.12TheideaofpopularityrankingusinghyperlinkscanbeextendedtorelationalandXMLdata,usingforeignkeyandIDREFedgesinplaceofhyperlinks.Sug-gesthowsucharankingschememaybeofvalueinthefollowingapplications.a.Abibliographicdatabase,whichhaslinksfromarticlestoauthorsofthearticlesandlinksfromeacharticletoeveryarticlethatitreferences.b.Asalesdatabasewhichhaslinksfromeachsalesrecordtotheitemsthatweresold.Alsosuggestwhyprestigerankingcangivelessthanmeaningfulresultsinamoviedatabasethatrecordswhichactorhasactedinwhichmovies.Answer:Noanswer.19.13Whatisthedifferencebetweenafalsepositiveandafalsedrop?Ifitisessentialthatnorelevantinformationbemissedbyaninformationretrievalquery,isitacceptabletohaveeitherfalsepositivesorfalsedrops?Why?Answer:Noanswer. CHAPTER20Database-SystemArchitecturesExercises20.6Whyisitrelativelyeasytoportadatabasefromasingleprocessormachinetoamultiprocessormachineifindividualqueriesneednotbeparallelized?Answer:Portingisrelativelyeasytoasharedmemorymultiprocessorma-chine.Databasesdesignedforsingle-processormachinesalreadyprovidemul-titasking,allowingmultipleprocessestorunonthesameprocessorinatime-sharedmanner,givingaviewtotheuserofmultipleprocessesrunninginpar-allel.Thus,coarse-granularityparallelmachineslogicallyappeartobeidenti-caltosingle-processormachines,makingtheportingrelativelyeasy.Portingadatabasetoashareddiskorsharednothingmultiprocessorarchi-tectureisalittleharder.20.7Transactionserverarchitecturesarepopularforclient-serverrelationaldata-bases,wheretransactionsareshort.Ontheotherhand,dataserverarchitec-turesarepopularforclient-serverobject-orienteddatabasesystems,wheretrans-actionsareexpectedtoberelativelylong.Givetworeasonswhydataserversmaybepopularforobject-orienteddatabasesbutnotforrelationaldatabases.Answer:Dataserversaregoodifdatatransferissmallwithrespecttocom-putation,whichisoftenthecaseinapplicationsofOODBssuchascomputeraideddesign.Incontrast,intypicalrelationaldatabaseapplicationssuchastransactionprocessing,atransactionperformslittlecomputationbutmaytouchseveralpages,whichwillresultinalotofdatatransferwithlittlebenefitinadataserverarchitecture.Anotherreasonisthatstructuressuchasindicesareheavilyusedinrelationaldatabases,andwillbecomespotsofcontentioninadataserverarchitecture,requiringfrequentdatatransfer.Therearenosuchpointsoffrequentcontentionintypicalcurrent-dayOODBapplicationssuchascomputeraideddesign.101 102Chapter20Database-SystemArchitectures20.8Whatislockde-escalation,andunderwhatconditionsisitrequired?Whyisitnotrequirediftheunitofdatashippingisanitem?Answer:Inaclient-serversystemwithpageshipping,whenaclientrequestsanitem,theservertypicallygrantsalocknotontherequesteditem,butonthepagehavingtheitem,thusimplicitlygrantinglocksonalltheitemsinthepage.Theotheritemsinthepagearesaidtobeprefetched.Ifsomeotherclientsub-sequentlyrequestsoneoftheprefetcheditems,theservermayasktheownerofthepagelocktotransferbackthelockonthisitem.Ifthepagelockownerdoesntneedthisitem,itde-escalatesthepagelockthatitholds,toitemlocksonalltheitemsthatitisactuallyaccessing,andthenreturnsthelocksontheunwanteditems.Theservercanthengrantthelatterlockrequest.Iftheunitofdatashippingisanitem,therearenocoarsergranularitylocks;evenifprefetchingisused,itistypicallyimplementedbygrantingindividuallocksoneachoftheprefetcheditems.Thuswhentheserverasksforareturnofalock,thereisnoquestionofde-escalation,therequestedlockisjustreturnediftheclienthasnouseforit.20.9Supposeyouwereinchargeofthedatabaseoperationsofacompanywhosemainjobistoprocesstransactions.Supposethecompanyisgrowingrapidlyeachyear,andhasoutgrownitscurrentcomputersystem.Whenyouarechoos-inganewparallelcomputer,whatmeasureismostrelevantspeedup,batchscaleup,ortransactionscaleup?Why?Answer:Withincreasingscaleofoperations,weexpectthatthenumberoftransactionssubmittedperunittimeincreases.Ontheotherhand,wewouldntexpectmostoftheindividualtransactionstogrowlonger,norwouldwere-quirethatagiventransactionshouldexecutemorequicklynowthanitdidbe-fore.Hencetransactionscale-upisthemostrelevantmeasureinthisscenario.20.10Databasesystemsaretypicallyimplementedasasetofprocesses(orthreads)sharingasharedmemoryarea.a.Howisaccesstothesharedmemoryareacontrolled?b.Istwo-phaselockingappropriateforserializingaccesstothedatastruc-turesinsharedmemory?Explainyouranswer.Answer:Noanswer.20.11Whatarethefactorsthatcanworkagainstlinearscaleupinatransactionpro-cessingsystem?Whichofthefactorsarelikelytobethemostimportantineachofthefollowingarchitectures:sharedmemory,shareddisk,andsharednoth-ing?Answer:Increasingcontentionforsharedresourcespreventslinearscale-upwithincreasingparallelism.Inasharedmemorysystem,contentionformem-ory(whichimpliesbuscontention)willresultinfallingscale-upwithincreas-ingparallelism.Inashareddisksystem,itiscontentionfordiskandbusaccesswhichaffectsscale-up.Inashared-nothingsystem,inter-processcommunica-tionoverheadswillbethemainimpedingfactor.Sincethereisnosharedmem- Exercises103ory,acquiringlocks,andotheractivitiesrequiringmessagepassingbetweenprocesseswilltakemoretimewithincreasedparallelism.20.12Processorspeedshavebeenincreasingmuchfasterthanmemoryaccessspeeds.Whatimpactdoesthishaveonthenumberofprocessorsthatcaneffectivelyshareacommonmemory?Answer:Noanswer.20.13Considerabankthathasacollectionofsites,eachrunningadatabasesystem.Supposetheonlywaythedatabasesinteractisbyelectronictransferofmoneybetweenoneanother.Wouldsuchasystemqualifyasadistributeddatabase?Why?Answer:Inadistributedsystem,allthesitestypicallyrunthesamedatabasemanagementsoftware,andtheyshareaglobalschema.Eachsiteprovidesanenvironmentforexecutionofbothglobaltransactionsinitiatedatremotesitesandlocaltransactions.Thesystemdescribedinthequestiondoesnothavetheseproperties,andhenceitcannotqualifyasadistributeddatabase. CHAPTER21ParallelDatabasesExercises21.7Foreachofthethreepartitioningtechniques,namelyround-robin,hashpar-titioning,andrangepartitioning,giveanexampleofaqueryforwhichthatpartitioningtechniquewouldprovidethefastestresponse.Answer:Roundrobinpartitioning:Whenrelationsarelargeandqueriesreadentirerelations,round-robingivesgoodspeed-upandfastresponsetime.HashpartitioningForpointqueries,thisgivesthefastestresponse,aseachdiskcanpro-cessaquerysimultaneously.Ifthehashpartitioningisuniform,evenentirerelationscanscanbeperformedefficiently.RangepartitioningForrangequerieswhichaccessafewtuples,thisgivesfastresponse.21.8Whatfactorscouldresultinskewwhenarelationispartitionedononeofitsattributesby:a.Hashpartitioningb.RangepartitioningIneachcase,whatcanbedonetoreducetheskew?Answer:a.Hash-partitioning:Toomanyrecordswiththesamevalueforthehashingattribute,orapoorlychosenhashfunctionwithoutthepropertiesofrandomnessanduniformity,canresultinaskewedpartition.Toimprovethesituation,weshouldexperimentwithbetterhashingfunctionsforthatrelation.105 106Chapter21ParallelDatabasesb.Range-partitioning:Non-uniformdistributionofvaluesforthepartitioningattribute(in-cludingduplicatevaluesforthepartitioningattribute)whicharenottakenintoaccountbyabadpartitioningvectoristhemainreasonforskewedpartitions.Sortingtherelationonthepartitioningattributeandthendi-vidingitintonrangeswithequalnumberoftuplesperrangewillgiveagoodpartitioningvectorwithverylowskew.21.9Giveanexampleofajointhatisnotasimpleequi-joinforwhichpartitionedparallelismcanbeused.Whatattributesshouldbeusedforpartitioning?Answer:Wegivetwoexamplesofsuchjoins.a.r(r.A=s.B)∧(r.A