中山大學軟件學院2010級軟件工程專業(yè)《SE304數(shù)據(jù)庫系統(tǒng)》期末試題

1、中山大學軟件學院2010級軟件工程專業(yè)(2011春天學期)SE-304數(shù)據(jù)庫系統(tǒng)期末試題答案(A)(考試形式：開卷考試時間:2小時)中山大學授與學士學位工作細則第六條考試舞弊不授與學士學位方向：姓名：學號：出卷：馮劍琳、鄭貴鋒審查：注意：答案必定要寫在答卷中，寫在本試題卷中不給分。本試卷要和答卷一同交回。Question1.(20marks)Assumeasimplecaseofnon-1NFrelationsdefinedasfollows:allvaluesarenon-emptysetsofintegers.Forexample,thefollowingisaschemaofA,B,Ca

2、ndD.ABCD1,22,41,21,42,34,52,32,31,31,32,32,3SupposeanFDXY(XandYaresetsofattributes)isnewlydefinedasfollows:anypairoftuplest1andt2,ifforallattributesAinX,t1Aandt2Ahavecommonelements(假如全部下性均有公共元素)thenthereexistsanattributeBinYsuchthatt1Bandt2Bhavecommonelements.Forexample,wehaveACintheabovetablebutnot

3、AB.舉例來說，1,22,41,21,4這一行就是一個tuple，1,2是一個attribute，1,2里面的1和2就是兩個elements。ABCD1,22,41,21,42,34,52,32,31,31,32,32,3(i)(5marks)Proveordisproveifdecompositionrule(IfXYZ,thenXYandXZ)ofFDsholdsinthenewsetting.分解定律不建立。在題目所給的例子中，ABC建立，AC也建立，但AB不建立。再看另一個例子。這個例子中ABC建立，AB也建立。但AC不建立.ABCD11111122第1頁，共6頁(ii)(5marks

4、)Proveordisproveiftransitivityrule(IfXYandYZ,thenXZ)ofFDsholdsinthenewsetting.傳達律不建立。反比以下：ABCD11111122ABC和BCD均建立?？墒茿D不建立。（BCD建立的原由可由“包含a=b中若a為假，則a=b為真”推出）(iii)(10marks)Proveordisproveifunionrule(IfXYandXZ,thenXYZ)ofFDsholdsintheabovesetting.標準答案：Unionruleholds.Toproveunionrule:IfXYandXZ,thenXYZForan

5、ytwotuplest1andt2,suchthatt1Aforallt2AinXSinceXYholds,wehavet1At2AforsomeAinY.AisinYZandthusXYZalsoholds.由于XY，因此關(guān)于X里面的全部下性，它們都有公共元素；且關(guān)于Y里面存在某些屬性擁有公共元素。同原由于XZ，因此關(guān)于X里面的全部下性，它們都有公共元素；且對于Z里面存在某些屬性擁有公共元素。因此我們能夠得出結(jié)論：“關(guān)于X里面的全部下性，它們都有公共元素；關(guān)于YZ里面存在某些屬性互相之間是有公共元素的”，這就能夠推出XYZ了。Question2.(20marks)Considerconstr

6、uctingaB+treeoforderd=1(i.e.,everynodecontainsmentries,whered=m=2d).(a)(10marks)Showtheresultingtreeafterinsertingkeys10,20,30,40,50,60inthisorder,onebyone.Drawtheinitialtreeandthetreesaftereverynodesplit.(初始樹、每次節(jié)點分裂后的樹).(b)(10marks)Isitpossible,withthesamesetofkeys,toconstructai.e.,“shorter”treeone

7、thathasasmallerheight?Ifno,explainwhynot.Ifyes,showanorderofinsertingthekeysandtheresultingtree.Sol:(a)第2頁，共6頁第3頁，共6頁(b)輸入碼的次序（此中一種）：10，30，50，60，40，20第4頁，共6頁第5頁，共6頁Question3.(25marks)ConsiderthefollowingtworelationsRandS.ThenumberofrecordsinRandSisalsogiven.R(A,B,C,D):20,000recordsS(A,E):36,000recor

8、dsAssumingthesizeofeachmemorypageis4Kbytesandthememorybufferhas30pages.Forsimplicity,wetake4Kas4000;weassumeallattributevaluesandpointers,ifneededtobeconsidered,are10bytes.ConsiderthefollowingSQLquery:Query:SELECTB,EFROMR,SWHERER.A=S.AGiveestimationofthefollowingquestions.Allthecomputationsstepsandt

9、heirreasoningshouldbeclearlyexplained.(a)(10marks)WhatisthesizeofRandSintermsofpages?EachRrecordis(10 x4)=40bytesandeachSrecordis(10 x2)=20bytes.Thereare4000/40=100Rrecordsperpageand4000/20=200Srecordsperpage.Therefore,Rcontains20000/100=200pagesandScontains36000/200=180pages.(b)(15marks)Assumeusing

10、sort-mergejointoprocessthequeryasfollows:Step1:SortRonR.Aandstorethesortedrelationindisk,assumingwediscardirrelevantattributesassoonaspossible.Step2:SortSonS.AbutcomparewithR(sortedalreadyinStep1)onceasortedpageofSisgeneratedinthefinalpass,assumingwediscardirrelevantattributesassoonaspossible.Sept3:

11、TransfersortedRpagebypagefromdisktomemorybuffertocomparethesortedpagesofSgeneratedinStep2.Estimatethecostofeachstepandthencomputethetotalcostofsort-mergejoin.Step1:Wehave200/30=7sortedruns.Ateachsortedrun30Rpagesarereadand15pagesarewrittenduetodiscardingattributeCandD.Onemorepasscanmergeall.Costofso

12、rtingR=200+100(firstpass)+100+100(finalpass)=500pages.Step2:Wehave180/30=6sortedruns.Ateachsortedrun30Spagesarereadand30pagesarewritten(noattributecanbediscarded).Onemorepasscanmergeallandthegeneratedpagesareusedfordirectcomparison.CostofsortingR=180+180(firstpass)+180(halfofthefinalpassduetoimmedia

13、temergingwithRpages)=540Step3:CostoftransfersortedR=100Totalcost=500+540+100=1140pagesQuestion4.(15marks)ConsiderthescheduleSthatconsistsoffourtransactionsasfollows:S=.Thenotationisself-explanatory.Forexample,T2_R(X)meansthattransactionT2readsitemX.第6頁，共6頁T1T2T3T4R(X)W(X)R(Z)R(Z)R(Y)W(Z)R(X)W(X)W(Y)

14、W(Z)R(Y)(9marks)ConstructtheprecedencegraphofS.Explainwhyorwhynotthescheduleisconflict-serializable.Itconflicts-serializable,nocircle.(6marks)IfyoufindthatSisserializablein(a),writedownallequivalentserialschedulesofS.T2,T3,T1,T4Question5(20marks)TherelationaldatabaseschemaforaCar-insurancecompanyisg

15、ivenbelow:person(driver-id,name,address)car(license,year,model)accident(report-number,location,date)owns(driver-id,license)participated(report-number,driver-id,license,damage-amount)employee(person-name,street,city)works(person-name,company-name,salary)company(company-name,city)manages(person-name,m

16、anager-name)(10marks)Giveanexpressionintherelationalalgebratoformulateeachofthefollowingqueries:a.FindthenamesofallemployeeswhoworkforthecompanyChina”“.Bankperson-name(company-name=BankChina(works)b.Findthenamesandcitiesofresidenceofallemployeeswhoworkfor“BankChina”.(employee(works)person-name,citycompany-name=BankChina第7頁，共6頁“WaiHuan