中山大学软件学院本科生期末考试《数据库系统原理》(A卷)

▒▓中山大学本科生期末考试试▒▓中山大学软件学院本科生期末考试考试科目：《数据库系统原理》（A卷）学年学期：2014学年第3学期学院/系：软件学院考试方式：开卷考试时长：120分钟

姓名：学号：班别：警示以下为试题区域，共7道大题，总分100分,考生请在答题纸上作答(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.▒▓▒▓中山大学本科生期末考试试▒▓(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