中山大学软件学院2008《SE304数据库系统原理》期末试题

1、中山大学软件学院软件工程专业2008级(2010秋天学期)SE-304数据库系统原理期末试题参照答案(A卷)(考试形式：开卷考试时间:2小时)Question1.DatabaseDesign(18points)Abuscompanywantstokeeptrackofitsbusroutesandschedules.Answerthequestionsaccordingtothefollowingdescription:Eachbusroutehasaroutenumber,adeparturestationandadestinationstation.Foreachbusroute,ther

2、eisaschedule,whichrecordsthedeparturetimesofbuses.Foreachdeparturetimeofeachroute,adriverandabuscanbeassigned(howeverthisisnotnecessary-informationaboutthedriverorthebusmaysometimesbemissing)AdriverhasanemployeeId,anameandaphonenumber.Abusisidentifiedbyitslicensenumber.Thedatabasealsorecordstheseati

3、ngcapacityofeachbus.(a)(10points)DrawanERdiagramforthedatabase,identifyallconstraintsandkeys,andwritedownanyassumptionsyouhavemade.(8points)ConstructappropriaterelationschemasfortheERdiagramin(a),underlinetheprimarykeys.Solution:(a)10points(b)8pointsRoute(Number#,departurestation,destinationstation)

4、Schedule(Route_Number#,departuretime)Driver(id#,name,phone)Bus(licence#,capacity)Drives(Number#,departuretime,Driver_id#)Bus_In_Use(Number#,departuretime,licence#)第-1-页/共8页Question2.RAandSQL(16points)Supposeabookstorehasthefollowingfiverelationaltables:BOOK(BID,TITLE,AID,SUBJECT,QUANTITY-IN-STOCK)AU

5、THOR(AID,FIRST-NAME,LAST-NAME)CUSTOMER(CID,FIRST-NAME,LAST-NAME)ORDER-DETAILS(OID,BID,QUANTITY)ORDER(OID,CID,ORDER-YEAR)ASSUMPTIONS:Keysareunderlinedandforeignkeysareinitalics.Eachauthorhasauthoredatleastonebookinthestore.Eachbookhasexactlyoneauthor.Eachorderismadebyexactlyonecustomerandhasoneormore

6、associatedrecordinORDER-DETAILS(e.g.,anordermaycontaindifferentbooks).WritethefollowingqueriesinRA(relationalalgebra)andSQL:(a)Findalldistinctbooktitlesoftheauthorwhoselastnameis“Lee”.(b)Findthelastnameandfirstnameofallauthorswhowrotebooksinatleasttwosubjects.Solution:(a)algebra:(BOOKAUTHOR.AID=BOOK

7、.AIDAUTHOR)TITLE(LAST-NAME=“Lee”SQL:SELECTDISTINCTB.TITLEFROMBOOKB,AUTHORAWHEREA.LAST-NAME=“Lee”ANDA.AID=B.AID(b)第-2-页/共8页Question3.ConstraintsandNormalization(16points)Inreality,FDsaregivenimplicitlyintheformofconstraintswhendesigningadatabase.LetarelationR=(Title,Length,Theater,City)wheretitleisth

8、enameofamovie,lengthisthemovielength,theateristhenameofatheaterplayingthemovieandcityisthecitywherethetheaterislocated.Giventhefollowingconstraints:Thesamenamemovieshavethesamelength.Twodifferentcitiescannothavetheaterswiththesamename.Twodifferenttheatersinthesamecitycannotplaythesamemovie.Atheaterc

9、anplaymanymovies.(6points)Writethesetoffunctionaldependenciesimpliedbytheaboveassumptions.TitleLengthTheaterCityCity,TitleTheater(4points)Identifythecandidatekey(s),andisRa3NForBCNFrelation?City,TitleandTheater,Title.3NF,notBCNF(6points)IfRisnotBCNF,decomposeittoBCNF.R1Title,Length,R2Theater,City,R3

10、Theater,Title第-3-页/共8页Question4.QueryOptimization(18points)ConsidertworelationalfilesStudent(s_id,name,dept_id,address),Enroll(class_id,student_id,semester,grade).TheStudentfilecontains10,000recordsin1,000pagesandtheEnrollfilecontains50,000recordsin5,000pages.Thereare10differentdepartmentsand25diffe

11、rentclasses.Allattributeshavethesamelength.Eachindex,whereveravailable,isatreewith3levels.Fornon-clusteringindexes,eachpointerisassumedtoleadtoadifferentpage.Ourgoalistoprocessthequery:SELECTS.nameFROMStudentS,EnrollEWHERES.dept_id=COMPANDE.class_id=530andS.S_id=E.Student_idSomeusefulstatistics:Astu

12、dentenrollsontheaveragein5classesAdepartmentcontainsontheaverage1,000studentsEachclasscontainsanaverageof2000enrolmentrecords(5points)ConsiderthattheStudentfilecontainsaclusteredindexondept_id,andtheEnrollfilecontainsanon-clusteredindexonstudent_id.Describeafullypipelinedplan(i.e.,donotmaterializean

13、ything)forprocessingthequerybyusingStudentsastheouterrelationandtakingadvantageofbothindexes.(b)(4points)Estimatetheapproximatecostofyourplan.Selectionneedstoread3+100pagesofStudents(clusteredindexondept_id)andwillreturn1,000studentidsandnames.Foreach(ofthe1,000)studentweusetheindexons_id(forEnroll)

14、tofindthecorrespondingrecord:cost=1,000(3+5)=8,000(foreachs_idweretrieve5recordsinclasses).Totalcost=8103pages.(thiscostdoesnotincludeanextralevelofindirectionforthenon-clustereds_idindex-ifwealsoincludethisthecostbecomes9103)(c)(9points)Forthefollowingquestions,assumethattherearenoindexes.Usingthea

15、bovefilesizes,estimatethecostofblocknestedloopswithamainmemorybufferof102pages(foreachcaseexplainbriefly):Studentastheouterrelation:1,000+5,000*10=51,000Enrollastheouterrelation:5,000+1,000*50=55,000Whatistheminimalcostthatyoucanachieveandhowmanymemorypagesyouneedtoachieveit?第-4-页/共8页Theminimalcosti

16、sthatofreadingbothfiles(6,000pages).Itcanbeachievedusingabufferof1,002pages(assumingStudentsastheouterrelation).第-5-页/共8页Question5.IndexingandStoragestructure(18points)Supposethatweareusingextendablehashingindexthatcontainsthefollowingsearch-keyvaluesK:1,4,5,7,8,2,20.Assumingthesearch-keyvaluesarriv

17、einthegivenorder(i.e.1beingthefirstcomingkeyand20beingthelastone).Showtheextendablehashstructureforeachinsertionoftheabovekeyvaluesfileifthehashfunctionish(x)=xmod8andbucketscanholdtwokeys.Theinitialconfigurationofthestructureandthebinaryform(assumingthechoiceofbitsstartingfromLeastSignificantBit(LS

18、B)ofallkeysaregiveninthediagrambelow.InitialhashtableEmptybucketBinaryvaluesofallkeysKInsert1,4Insert5110411152100480110211152Insert7,872Insert第-6-页/共8页220048012101511222733000800130104200112100151011102111227Insert20第-7-页/共8页Question6.TransactionManagement(14points)ConsiderthescheduleSthatconsistsoffourtransactionsasfollows:S=.Thenotationisself-explanatory.Forexample,T2_R(X)meansthattransactionT