?▓中山大學(xué)本科生期末考試試?▓中山大學(xué)軟件學(xué)院本科生期末考試考試科目：《數(shù)據(jù)庫(kù)系統(tǒng)原理》（A卷）學(xué)年學(xué)期：2014學(xué)年第3學(xué)期學(xué)院/系：軟件學(xué)院考試方式：開(kāi)卷考試時(shí)長(zhǎng)：120分鐘

姓名：學(xué)號(hào)：班別：警示以下為試題區(qū)域，共7道大題，總分100分,考生請(qǐng)?jiān)诖痤}紙上作答(10marks)LetR={A,B,C,D,E,F,G}andF=BC,GF}.Answerthefollowingthreequestions.(4marks)ComputetheminimalcoverofF.BCACAEEFGGF(4marks)DecomposeRinto3NFrelations.{B,C},{A,C,E},{E,F,G}and{A,B,D,F}(OR{A,B,D,G})(2marks)Isthecompositionin(b2)inBCNF?Brieflyexplainyouranswer.No.For{E,F,G}andGF,Gisnotacandidatekey.?▓?▓中山大學(xué)本科生期末考試試?▓(10marks)AssumethereisanemployeedatabaseEmployee(eid:8bytes,ename:16bytes,did:4bytes,email:12bytes),whereeidandenamearerespectivelytheidandnameofanemployeeanddidistheidofthedepartmentinwhichtheemployeeworks.Supposethereare50,000employeerecordsand500departments(i.e.eachdepartmenthas100employeesonaverage).Apagesizeis1,000bytesandapointercosts4bytes.(4marks)Assumethattheemployeefileissortedsequentiallyondidandthereisnoindex.Estimatethepageaccesscostforretrievingtherecordsofallemployeesworkinginadepartmentwithagiven did.(Youshouldshowyourargumentandthemainstepsoftheestimationclearlyintheanswer.)AnswerRecordsize=40bytes,25recordsperpage,2,000pages.Findingthefirstrecordrequires+3morepagestosearchremainingrecords(eachdepthas100employeeswhicharedistributedin4pages).(6marks)Assumeonly20pagesofmainmemoryareavailableforrunningexternalsortingoftheemployeefileondid.HowmanyPASSesareneededfortheexternalsorting?IneachPASS,howmanyrunsarecreated?Whatisthetotalcostofthesortingintermsofpages?Answer:3PASSes:PASS0:2000pages/20pagesperrun=100runsPASS1:ceil(100runs/19runsperrun)=6runsPASS2:1runTotalcost:(2000pagesreadperpass+2000pageswriteperpass)*2PASSes+2000pagesreadperpass=10000pages(Note:Outputisnotcounted!)Or: 2000*(2*2+1)=10000pagestransfer.(10marks)SupposeabookstorehasthefollowingfiverelationalBOOK(BID,TITLE,AID,SUBJECT,QUANTITY_IN_STOCK)7710152015791013151720252930AUTHOR(AID,NAME)CUSTOMER(CID,NAME)ORDER_DETAILS(OID,BID,QUANTITY)ORDER(OID,CID,ORDER_YEAR)Intheabovetables,keysareunderlinedandforeignkeysareinitalics. Eachauthorauthoredatleastonebookinthestore.Eachbookhasexactlyoneauthor.EachorderismadebyexactlyonecustomerandhasoneormoreassociatedrecordinORDER_DETAILS(e.g.,anordermaycontaindifferentbooks).Expressthefollowingqueryusing(i)SQLexpressions,(ii)therelationalalgebra(RA).FindthedistinctcustomerIDs(CID)ofcustomerswhohavepurchasedmorethan10identicalbooksinoneorderatleastonce.SELECTDISTINCTCIDFROMORDER_DETAILSod,ORDERoWHEREQUANTITY>=10ANDod.OID=CID(σQUANTITY≥10(ORDER_DETAILS OIDORDER))(10marks)AB+treewithn=5isshowninFigure1,inwhichonlysearchkeysareshownandpointerstothefilesystemarehidden.Wewanttoinsertadataentrywithsearchkey“23”.Figure1.AB+TreeStructureWhichofthefollowingdescriptionsabouttheinsertionoperationiscorrect?TheB+treecontains2levelsafterinsertion.2nodesplitsareneededduringinsertion.Therootnodecontainssearchkey“15”.TheB+treecontains3levelsafterinsertion.1nodesplitisneededduringinsertion.Therootnodecontainssearchkey“20”.TheB+treecontains3levelsafterinsertion.2nodesplitsareneededduringinsertion.Therootnodecontainssearchkey“15”.TheB+treecontains3levelsafterinsertion.2nodesplitsareneededduringinsertion. Therootnodecontainssearchkey“20”.Answer:CWewanttodeletethedataentrywithsearchkey“7”.Howmanyleafnodesstoreonlytwodatavaluesafterdeletion?2345Answer:(20marks)Youaregivenaninitialhashstructurewiththreekeysalreadyinsertedasbelow.Thehashfunctionish(x)=xmod16.DrawfiveextendablehashstructurescorrespondingforeachinsertionofthefollowingsearchkeyvaluesK:7,15,20,37,18.Assumeeachbucketcanholdtwokeysandthesearchkeyvaluesarriveinthegivenorder(i.e.7beingthefirstcomingkeyand18beingthelastone).Youshouldfollowtheconventionusedbylectureslides:binaryhashindicesstartingfromtheleastsignificantbit.(E.g.1istheleastsignificantbitofthe4digitbinarynumber0001.)11101411172521002100140110211172527Insert15and2021001420011021117252715Insert373310001420001010301117251003101371101112715Insert183320002000120100111418100310117251101113372715(25Marks)ConsideradatabaseconsistingofthefollowingthreerelationSAILORS(sid,sname,rating,age)BOATS(bid,bname,color)RESERVES(sid,bid,date,rname)Themeaningoftheattributesintheaboveschemasisself-explanatory.Forexample,sidisthesailoridentitynumberandbnameisthenameoftheboat.Theprimarykeysoftherelationsareunderlined.TheattributesidinRESERVESisaforeignkeyreferencingSAILORS.TheattributebidinRESERVESisaforeignkeyreferencingBOATS.TherelationSAILORShas100,000tuplesand100tuplesofSAILORSfitintoonepage.relationBOATShas50,000tuplesand25tuplesofBOATSfitintoone page.TheRESERVEShas10,000tuplesand20tuplesofRESERVESfitononepage.Weassumeallattributevaluesandpointersin thesethreerelations,ifneededto beconsidered,areofsamesize.(10marks)AssumethatweuseIndexedNestedLoopJointocomputeSAILORSRESERVESusingSAILORSastheouterrelation.RESERVEShaveprimaryB+-treeindexwith2levelsonthejoinattribute.Estimatethecostofthejoinintermsofpages.NumberofSAILORSpages:br=100,000/100=1,000NumberofSAILORSTuples:nr=100,000.Thecostisbr+c*nr=1,000+(2+1)*100,000=301,000.(5mark)Assumethat26%ofthesailorshavetheratingbiggerthan5.Estimateresultsizeof sid(σrating>5SAILORS)intermsofpages.Size=26%*100,000/100/4=65pages260dividedby4,forthereisprojectionandalltheattributeshavesamesize(10marks)ConsiderthefollowingtwostrategiestocomputethejoinoperationSAILORS BOATS RESERVES.Strategy1:(SAILORSBOATS)RESERVESStrategy2:(SAILORSRESERVES) Whichstrategyisbetter?Explainthereason(s)ofyourchoicebasedonthesizeoftheintermediateresultusingtheabovestrategies.Strategy2isbetter.BecauseinStrategy1,SAILORSBOATSisequaltothecross-productoftherelationsandthesizeofthejoinresultwillbecomeaslargeas100,000*50,000=5,000,000,000tuples.ThisintermediateresultisverylargeandlaterwhenjoiningintermediateresultwithRESERVES,thecostisalsolarge.Incomparison,inStrategy2,SAILORSRESERVEShasonly10,000tuples.AndlaterwhenjoiningthisintermediateresultwithBOATS,thecostisalsosmall.(15Marks)ConsiderascheduleSwhichconsistsoffourtransactionsasfollows:S=<T3_R(U),T2_R(X),T2_W(X),T3_R(X),T1_R(Y),T1_W(Y),T3_W(X),T1_R(Z),T4_R(Z),T4_W(Z),T2_W(Y),T3_R(Y)>Thenotationisself-explanatory.Forexample,T1_R(X)meansthattransactionT1readsitemX.(5marks)FillinthefollowingtablerepresentingSwiththeusualnotationsinlectureslides.ThefirstoperationR(U)hasbeenshowninthetable.Showclearlyallconflictingpairswithdownwardarrowsontheoperations.T1T1T2T3R(U)T4R(X)W(X)R(X)R(Y)W(Y)W(X)R(Z)R(Z)W(Z