数据库试卷

第-1-页，共32页中山大学本科生期末考试考试科目：《数据库系统》（A卷）学年学期：2015学年第三学期姓名：学院/系：数据科学与计算机学院学号：考试方式：开卷年级专业：考试时长：120分钟班别：警示《中山大学授予学士学位工作细则》第八条：“考试作弊者，不授予学士学位。”--------------以下为试题，共七道大题，总分100分,考生请在答题纸上作答--------------Question1.(15marks)Considerthefollowingrelationalschema:Likes(drinker,beer)Frequents(drinker,bar)Serves(bar,beer)(i)(5marks)Foreachbar,countthenumberofdrinkersthatfrequentthatbarandthatlikeboth'zhujiang'and'haerbing'.AnswerSELECTx.bar,count(distinctx.drinker)FROMfrequentsx,likesy,likeszWHEREx.drinker=y.drinkerANDx.drinker=z.drinkerANDy.beer='zhujiang'ANDz.beer='haerbing'GROUPBYx.bar(ii)(5marks)Findalldrinkersthatfrequentsomebarthatservessomebeerthattheylike.AnswerSELECTDISTINCTx.drinkerFROMfrequentsx,servesy,likeszWHEREx.bar=y.barANDy.beer=z.beerANDx.drinker=z.drinker(iii)(5marks)Giveanexpressionintherelationalalgebratoformulatethequeryin(ii).第-2-页，共32页AnswerOnepossiblesolution:πx.drinker(x.bar=y.barANDy.beer=z.beerANDx.drinker=z.drinker(xyz))Question2.(15marks)Astoremaintainsthefollowingrelationsforitsemployeerecords:employee(officeNum,SSN,phone,managerName,deptNum)Giventhefollowingfunctionaldependencies:officeNumphoneSSNofficeNum,deptNumdeptNummanagerName(i)(5marks)Listonekeyoftheemployeerelation,andcomputetheattributeclosureofthekeyyouhavelisted.Youarerequiredtoshowthemajorstepsofcomputingtheattributeclosure.AnswerSSN+=SSN=SSNofficeNumdeptNum=SSNofficeNumdeptNumphone=SSNofficeNumdeptNumphonemanagerName(ii)(10marks)IstheemployeerelationinBCNF?Ifso,write“Yes”below.Otherwise,decomposeitintoBCNFandunderlineallkeysandforeignkeysinthefinalrelations.AnswerOnepossiblesolution:TherelationisnotinBCNF.FromofficeNumphone,R1={officeNum,phone},R2={officeNum,SSN,deptNum,managerName}R1isinBCNF.FromdeptNummanagerName,R21={deptNum,managerName},R22={deptNum,SSN,officeNum}R21isinBCNF.第-3-页，共32页FromSSNofficeNum,deptNum,R22isinBCNF.Thefinalrelationsare:R1={officeNum,phone},R21={deptNum,managerName},R22={deptNum,SSN,officeNum},wheredeptNumandofficeNuminR22areforeignkeystoR21(deptNum)andR1(officeNum)respectively.Question3.(10marks)ConsiderthefollowingtwoschedulesS1andS2,wherethenotationisself-explanatory(Forexample,R2(Y)meansthattransactionT2readsdataitemY).Drawtheprecedencegraphforeachscheduleanddecideiftheschedule(S1orS2)isconflictserializable.Ifitis,giveanequivalentserialscheduleoftransactions(e.g.,T2,T1,T3–youdon’tneedtolisttheindividualread/writestepsintheserialschedule).Ifthescheduleisnotconflictserializable,explainwhynot.Labeltheedgesoftheprecedencegraphswiththedataitemthatcausestheconflict(e.g.,X,Y,orZ).(i)(5marks)ScheduleS1:R2(Y);W2(Y);R3(Y);R1(X);W1(X);W3(Y);R2(X);R1(Y);W1(Y)AnswerThisisnotconflict-serializablebecauseofthecyclesintheprecedencegraph.第-4-页，共32页(ii)(5marks)ScheduleS2:R3(Y);R3(Z);R1(X);W1(X);W3(Y);R2(Z);R1(Y);R2(X);W1(Y);W2(X)AnswerThisisconflict-serializablebecauseofnocyclesintheprecedencegraph.TheequivalentserialscheduleisT3;T1;T2.Question4.(10marks)ConsiderthefollowingschedulesS,wherethenotationisself-explanatory(Forexample,R1(X)meansthattransactionT1readsdataitemX;similarly,L1_S(X)andL1_X(X)meanthattransactionT1locksdataitemXinsharedlockandexclusivelockrespectively;U1(X)meansthattransactionT1removesthelockondataitemX.)ScheduleS2:R1(X);W1(X);R2(X);R1(Y);W1(Y);R2(Y);W2(Y);W2(X)CouldthisschedulebeproducedbyaschedulerthatisusingtheTwo-PhaseLockingprotocol(2PL)?Explainwhyorwhynot.(Ifitispossible,aneasywaytodemonstratethatistorewrite(copy)theschedulewithlockandunlockoperationsinsertedintheappropriateplaces.)AnswerYes,thisispossible.Oneequivalentschedulewith2PLinsertedis:L1_X(X);L1_X(Y);R1(X);W1(X);U1(X);L2_X(X);R2(X);R1(Y);W1(Y);U1(Y);L2_X(Y);R2(Y);W2(Y);W2(X)Question5.(10marks)Considerslottedpagesthatareusedtostorevariable-lengthrecords.第-5-页，共32页AssumeanewlycreatedpagenumberedP,whereweallocateaslotintheslotdirectorywhenarecordcomes.Thefirstslotisnumbered1,thesecondslotisnumbered2,andetc.Considerthefollowingsequenceofactions:InsertrecordAoflength10bytes.InsertrecordBoflength20.InsertrecordCoflength15.InsertrecordDoflength25.DeleterecordB.DeleterecordD.Whenwedeletearecord,wechangethelengthtobe-1intherecord’sslot,andreduceby1thenumberofslotsintheslotdirectory.Compactthepage(thatis,moveallrecordstobecontiguoustooneanotherwithoutchangingthepositionofthecorrespondingslotsintheslotdirectory,startingfromthebeginningofthepage,tofreeupspacefornewrecords).(i)(6marks)DrawthepagePaftertheabovesequenceofactionshasbeenfinished.Youdonotneedtodrawthepointersfordeletedrecords.AnswerPagePAC154321-1-1102(ii)(4marks)ListRIDs(recordid)ofrecordAandrecordC,respectively.AnswerRIDofA=P,1RIDofC=P,3第-6-页，共32页Question6.(20marks)Considerthedatabaseconsistingofthefollowingrelations,whichisusedastherunningexampleinthetextbook:Sailors(sid:integer,sname:string,rating:integer,age:real)Reserves(sid:integer,bid:integer,day:dates,rname:string)TherelationReserveshas1000pagesintotal,with100tuplesperpage,wherethereare100differentboatsintherangeof[1,100].TherelationSailorshas500pagesintotal,with80tuplesperpage,wherethereare10differentratingsint