中山大学软件学院《SE304数据库系统原理》期末考试试卷(B)

中山大学软件学院2009级软件工程专业(2010学年春天学期)《SE-304数据库系统原理》期末考试一试卷(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