1、中山大學(xué)軟件學(xué)院2010級(jí)軟件工程專業(yè)(2011春天學(xué)期)SE-304數(shù)據(jù)庫系統(tǒng)期末試題答案(A)(考試形式：開卷考試時(shí)間:2小時(shí))中山大學(xué)授與學(xué)士學(xué)位工作細(xì)則第六條考試舞弊不授與學(xué)士學(xué)位方向：姓名：學(xué)號(hào)：出卷：馮劍琳、鄭貴鋒審查：注意：答案必定要寫在答卷中，寫在本試題卷中不給分。本試卷要和答卷一同交回。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這一行就是一個(gè)tuple，1,2是一個(gè)attribute，1,2里面的1和2就是兩個(gè)elements。ABCD1,22,41,21,42,34,52,32,31,31,32,32,3(i)(5marks)Proveordisproveifdecompositionrule(IfXYZ,thenXYandXZ)ofFDsholdsinthenewsetting.分解定律不建立。在題目所給的例子中，ABC建立，AC也建立，但AB不建立。再看另一個(gè)例子。這個(gè)例子中ABC建立，AB也建立。但AC不建立.ABCD11111122第1頁，共6頁(ii)(5marks

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

5、ytwotuplest1andt2,suchthatt1Aforallt2AinXSinceXYholds,wehavet1At2AforsomeAinY.AisinYZandthusXYZalsoholds.由于XY，因此關(guān)于X里面的全部下性，它們都有公共元素；且關(guān)于Y里面存在某些屬性擁有公共元素。同原由于XZ，因此關(guān)于X里面的全部下性，它們都有公共元素；且對(duì)于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é)點(diǎn)分裂后的樹).(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