中山大學軟件學院2009級軟件工程專業(yè)(2010學年春天學期)《SE-304數(shù)據(jù)庫系統(tǒng)原理》期末考試一試卷(B)(考試形式：開卷考試時間:2小時)《中山大學授與學士學位工作細則》第六條警示考試舞弊不授與學士學位方向：姓名：學號：Question1LogicalDatabases(20marks)YouarerequiredtoconstructanERDiagramforarestaurantwhichmaintainsdataaboutthefollowingthreeentities:dish,staffandtransaction.Thethreerelationshipsarebill,cookandprocessed-byandthedetailsoftherelationshipsaredescribedasfollows:?Arecordindishisuniquelyidentifiedbyafive-digitdish-code,andcontainstheinformationforthenameofthedish,thepriceofthedish;Astaffmemberhasstaff-id,name,andworking-time-info;Eachdishiscookedbyexactlyonestaffmember,butastaffmembercancookmorethanonedishes,assumethatallthestaffmemberscancookforsimplicity;Atransactioncanbeuniquelyidentifiedbythefollowinginformation:date,time,andtheresponsiblestaffwhohasprocessedthetransaction.Morethanoneunitsofthesamedishcouldbesoldandshouldberecordedbyadistincttransaction,thisrelationshipiscalledbill.(15marks)DrawtheERdiagramthatconsistsofthethreeentitiesandthethreerelationships.YoushouldwritedowntheassumptionsclearlyifyouthinkthattheabovedescriptionofthethreeentitiesandthreerelationshipsisnotadequatefordrawingtheERDiagram.YoushouldalsoindicateallimportantinformationoftheERDiagramsuchaskeys,weakentitiesandcardinalities.(5marks)ConverttheaboveERDiagramintothecorrespondingrelationalschemas.Underlinealltheattribute(s)oftheprimarykey.Specifyclearlywhetheraschemaisobtainedfromanentity,aweakentityorarelationship.第1頁，共5頁Question2IndexingStructure(18marks)Supposethatweareusingextendablehashingindexthatcontainsthefollowingsearch-keyvaluesK:2,10,10,12,15,15,3,13.Assumingthesearch-keyvaluesarriveinthegivenorder(i.e.2beingthefirstcomingkeyand13beingthelastone).Showtheextendablehashstructureforeachcaseofinsertingagroupoftheabovekeyvaluesifthehashfunctionish(x)=xmod16andbucketscanholdtwokeys.Theinitialconfigurationofthestructureandthebinaryformofallkeysaregiveninthediagrambelow.Conventionrequirement:Youshouldusethebitsstartingfromthemost-significantoneorMSB(theleft-handside)asthehashingindex.InitialhashtableEmptybucketBinaryvaluesofallkeysKAfterinserting2,10,10;Afterinserting12;Afterinserting15,15,3,13.第2頁，共5頁Question3(22marks)JoinAlgorithmsConsiderthefollowingtworelationsRandS.ThenumberofrecordsinRandSisalsogiven.R(A,B,C,D):5,000recordsS(A,E,F,G):18,000recordsThesizesofallattributevaluesaregiveninthetable.ABCDEFG10bytes20bytes30bytes20bytes50bytes20bytes20bytesAssumethesizeofeachmemorypageis4Kbytesandthememorybufferhas25pages.Allthecomputationsshouldshowthesteps.ConsiderthefollowingSQLquery:Query:SELECTC,EFROMR,SWHERER.A=S.A(4marks)WhatisthesizeofRandSintermsofpages?(18marks)Assumeusingsort-mergejointoprocessthequeryasfollows:Step1:SortRonR.Aandstorethesortedrelationindisk,assumingwediscardirrelevantattributesassoonaspossible.(Note:Youmayneedtorounduptowholepageafterremovingtheirrelevantattributesinthefirstpass.)Step2:SortSonS.AbutcomparewithR(sortedalreadyinStep1)onceasortedpageofSisgeneratedinthefinalpass,assumingagainwediscardirrelevantattributesassoonaspossible.(Note:Spagesgeneratedinthefinalpassdonotneedtowritebacktodisk.)Sept3:TransfersortedRpagebypagefromdisktomemorybuffertocomparethesortedpagesofSonceasortedpageisgeneratedinStep.2Estimatethecostofeachstepandthencomputethetotalcostofsort-mergejoin.第3頁，共5頁Question4(20marks)PhysicalDatabaseDesignConsiderthefollowingschemaswithusualmeaning:Studentsandprofessorsbelongtosomedepartments.Studentsareenrolledinthecoursesofferedbysomeprofessors.Thesizeofalltheattributevaluesisassumedtobethesameineachschema.TABLES:NoofrecordsNoofpagesDEPARTMENT(D_ID,D_NAME,HEAD_ID)10020PROFESSOR(P_ID,P_NAME,SALARY,D_ID)1,000100STUDENT(S_ID,S_NAME,D_ID)10,0001,000COURSE(C_ID,C_NAME,D_ID)1,000100OFFERING(O_ID,C_ID,YEAR,SEMESTER,P_ID)10,0001,000ENROLL(S_ID,O_ID,GRADE)100,00010,000Generalinformation:Thereare500differentprofessornames,1,000differentstudentnames,and100differentdepartmentnames.Ontheaverage,eachstudentisenrolledin10offeringsandeachofferinghas10students.Eachdepartmentoffers10courses.Assumethatprofessorsalariesareuniformlydistributedintherangefrom10,000to110,000.Indexinformation:Allindexpagesarestoredindisk.WeassumeB-treeswithheight3forclusteredindexstoredandtherearenooverflowbucketsforhashindex.Forindexesonanon-candidatekey,youmayhavemultipleentrieswiththesamesearchkeyentry.Wealsoignorethecrossfactorformultiplerecordswithsamesearchkeyinafileifthenumberofrecordsiswithinthepagelimit.Weoptimizethequeriesin(a)and(b)asfollows.Query1:Displaythenamesofallprofessorswhosesalaryisintherangefrom30,000to35,000.Approach1:Buildaclusteredindexonprofessor.salary.Approach2:Buildamulti-attributeindexon<salary,p_name>anddoindex-onlyscan.Whichapproachisbetter?Youranswershouldbebasedonthecostestimationwithclearexplanations.(b)Query2:Givenaprofessor’name,sfindthenameofthedepartmentthattheprofessorbelongsto.Approach1:Buildonehashindexonprofessor.p_nameandanotherhashindexondepartment.d_id.Approach2:Buildonehashindexonprofessor.p_nameandahashfileorganizationondepartment.d_idwherethedepartmentrecordsarepartitionedin5buckets.Whichapproachisbetter?Youranswershouldbebasedonthecostestimationwithclearexplanations.第4頁，共5頁Question5TransactionManagement(20marks)(2marks)GivetworeasonswhyaserialschedulefordatabasetransactionsisnotpracticalforcommercialDBMSs.Inthefollowingquestions,thenotationisself-explanatory.Forexample,R1(X)meanstransactionT1readsitemX.Similarly,“W”meansWRITEand“C”means“Commit”.(18marks)Foreachofthefollowingschedules,indicatewhetheritisconflictserializableandrecoverable.Ifitisconflictserializable,thenwriteoutoneequivalentserialschedule.Thefollowingisanexampleo