数据库系统实现第二版英文版部分答案

数据库系统实现第二版英文版部分答案Chapter13Thecapacityofthedisk?Thediskhas8×100,000=800,000tracks.Theaveragetrackhas2000×1024=2048,000bytes.Thus,thecapacityis214×108bytes

Themaximumseektime?Themaximumseektimeoccurswhentheheadshavetomoveacrossallthetracks.Thus,substitute100,000tracts(really99999)fornintheformula1+.0003n

toget31(30.9997)ms.

Themaximumrotationallatency?Themaximumrotationallatencyisonefullrevolution.Sincethediskrotatesat6,000rpm,ittakes1/6000ofaminute,ortorotate.Exercise13.2.1(2.2.1)Transfertimeofablock?Sinceatrackhas2000sectorsand2000gaps,and10%ofatrackisusedforgaps,thereare36oforgapsand324oforsectorsofatrackcircle.Sothereare36o/2000foreachgapand324o/2000foreachsector.Thisblockis65546bytes(i.e.64sectors),theheadsmustthereforepassover63gapsand64gaps,i.e.63×36o/2000+64×324o/2000.Asthemaximumrotationallatencyis0.01s,wecanhavethetransfertimeoftheblockis(63×36o/2000+64×324oo=0.0003195sor0.3195ms.

Exercise13.2.1(2.2.1)Theaverageseektime?Theaveragenistracks/3ofasurface,i.e.100,000/3.Sotheaverageseektimeis1+.0003×n=1+.0003×100,000/3=11ms.Theaveragerotationallatency?TheaveragerotationallatencyisTheaveragedensityofbitsinthesectorsofaoutertrack？Atrackhas2000sectors,eachsectorholds1024bytes,andeverybytetakes8bits,soatrackis2000×1024×8bits.Forthe3.5inchdisk,thedensityoftheoutertrackis2000×1024×8/(3.5×π×90%)=1655615.6394bit/inch.Exercise13.2.1(2.2.1)Theaveragetrackstheheadshavetomove:[(1+2+……+4095)+(1+2+……(65536-4096)]/65536≈28928Averageseektime+averagerotationallatency+averageExercise13.2.4(2.2.2)4096655361Seektime=1+tracks/4000Completetime=dealtime+seektime+transfertime+rotationallatencyExercise13.3.1(2.4.1)CylinderofrequestFirsttimeavailableESeektimeElevatorERankFSeektimeFCFSFCFSRank8,000037.3137.3148,00011122.621122.624,00010329.941238.9340,000201044.231053.24块传输时间为，平均旋转等待时间为，平均寻道时间为，所以平均读取一个块的时间为无约束的megatron镜像平均速度提高1倍，所以平均读取时间约为该系统缺陷主要在于无法同时处理同侧柱面的读取请求，大量同侧请求到来时会导致一边队列累积而另一边空闲Exercise13.4.9(2.6.7)DatadisksRedundantDisk1Disk2Disk3Disk4Disk5Disk6Disk7111010011010101011001DiskContents1234567DiskContents1234567Modulo-2sumofthenewvalue01111111

andtheoldvalue01010101is00101010Exercise13.5.3(3.2.2)8+25+1+10=44bytes8+32+8+16=64bytes8+28+4+12=52bytesExercise13.6.5(3.3.4)IPaddress4×8=32bits=4BDevicenumber14bits=2B(as213<10,000<214)Blockaddress4+16+6=26bits=4B(becausethereare24surfaces,216tracksand26blocks,seeP564.)So,totallyrequire10B.Thefirstthreefieldsneed9×3=27Byte.Andthefirstvariable-lengthfielddoesnotneedapointer,whilethesecondoneandthethirdoneneedpointers.Sothereare8×2=16Byteforpointers,andeveryrecordtakes

27+16=43Byte.Sincethelengthofarecordisa2-byteinteger,therecordhas45Byte.Chapter14Exercise14.1.2(4.1.2)⌈n/(50×80%)⌉blocksareneededforthedatafile,and⌈n/(500×80%)⌉fortheindex,foratotalof⌈n/40⌉+⌈n/400⌉

blocks.Weagainneed⌈n/(50×80%)⌉forthedatafile,butnowneedonlyroomfor⌈n/(50×80%)/(500×80%)⌉pointersintheindexfile.Thelattertakes⌈n/16000⌉blocks,foratotalof⌈n/40⌉+⌈n/16000⌉

blocks.Exercise14.1.7(4.2.8)Obtainallthebucketentriesfor“cat”and“dog”.Sortthesebytype,andwithintype,byposition.Scantherecords,keepinga“window”withrecordsofthecurrenttype,extendinguptofivepositionspriortothecurrenttype.Compareeachnewrecordwiththerecordsinthewindow.Ifwefindonethat:(1)Hastheoppositeword,e.g.“dog”ifthecurrentbucketrecordhas“cat”,and(2)Haveidenticaldocumententries.Thenthecommondocumentisoneofthosewewanttoretrieve.Exercise14.1.7(4.2.8)Obtainallthebucketentriesfor“dog”.Sortthesebyposition.Scantherecords,keepinga“window”withrecordsofonepositionpriortothecurrentposition.Compareeachnewrecordwiththerecordsinthewindow.Ifwefindonethat:(1)hastheoppositeword“cat”,and(2)haveidenticaldocumententries.Thenthecommondocumentisoneofthosewewanttoretrieve.Wefollowthepointerassociatedwith“cat”tofindtheoccurrencesofthisword.Selectfromthebucketpointerstodocumentsassociatedwithoccurrencesof“cat”wherethetypeis“title”.Thenwefindthebucketentriesfor“dog”,andSelectfromthebucketpointerstodocumentsassociatedwithoccurrencesof“cat”wherethetypeis“title”intersectthistwosetsofpointers,wecanhavethedocumentsthatmeettheconditions.Exercise14.2.1(4.3.1)Thesequential100000records,and20records/block.First,thereare5000datablocks.Ifthereareof69keysperblockonaverageinthebottom-levelnodesoftheB-tree,thenthereare1450B-treeblocksatthatlevel.ThenextleveloftheB-treerequires1/70thofthat,or21blocks.Thethreelevelhasonlytherootblock.Thenumberofblocksneededis5000+1450+21+1=6472blocks.SincetheB-treehasthreelevels,wemustmakeatotalof4diskreadstogothroughtheB-treetothedesireddatablock.as(a)Exercise14.2.1(4.3.1)Thesequential100000records,and20records/block.First,thereare5000datablocks.Withthesparseindex,ablockhasanindex,andthenthereare5000/69=73B-treeblocksatthatlevel.ThenextleveloftheB-treerequires1/70thofthat,or2blocks,andthethirdlevelhasonlytherootblock.Thenumberofblocksneededistherefore50000+73+2+1=5076blocks.SincetheB-treehas3levels,wemustmakeatotalof4diskreadstogothroughtheB-treetothedesireddatablock.Exercise14.2.1(4.3.1)Ifoneprimaryblockhas20recordswithitsoverflowblockshaving10records,100000recordsneed100000/30or3334primaryblocks,andthesamenumberofoverflowblocks.Thenumberoffirst-levelB-treeblocksis3334/69=49.Andthesecondlevelhasonlytheroot,foratotalof3334+3334+49+1=6718blocks.AsearchrequirestwodiskI/O'stogothroughtheB-treetothedatafile.Oncethere,wesurelyneedtoreadtheprimaryblock,and1/3ofthetimeweshallneedtoseetheoverflowblockaswell.Thus,theaveragenumberofdiskI/O'sis10/3(as3×2/3+4×1/3).Exercise14.2.1(4.3.1)Tobegin,thereare100000/7,or14286primaryblocks.Thenumberoffirst-levelB-treeblocksis14286/70=205.Atthesecondlevelthereare205/70=3,andthethirdlevelhasonlytheroot,foratotalof14286+205+3+1=14495blocks.SincetheB-treehas3levels,wemustmakeatotalof4diskreadstogothroughtheB-treetothedesireddatablock以下情况会出现递归处理：该块可能存储的数据条数>2n，例如散列键值为四位数，且某块j值为1，存储第一位为0的数据，但n=3，而可能存储的数据为0000-0111共有8条数据。分裂后每个子块最多有4条数据，仍然>n，如果分裂前的数据为0000-0011，则分裂后数据仍全归于前两位为00的块，仍需递归分裂Exercise14.3.5(4.4.6)

Exercise14.3.5(4.4.6)

Exercise14.5.1(5.2.1)若同一条线上多于两个点，则必须分开。180,280,2.15,2.5,3Exercise14.5.5(5.2.5)4×6=24Thedistancebetween(110,245)and(115,230)issqrt(250),i.e.(15,16)Lowleftcorner(80,200)(80,250)(100,250)(120,250)(120,200)Showamultiple-keyindexforthedataofthetableiftheindexesareon：Ram,thenhard-disk.Speed,thenramSpeed,thenhard-disk,thenram型号速度内存硬盘10012.66102425010022.1051225010031.425128010042.80102425010053.2051225010063.20102432010072.20102420010082.20204825010092.00102425010102.80204830010111.86204816010122.801024160Ram,thenhard-disk5121024204880250160200250320160250300b)Speed,thenram51220481024512102420481024102420485121024Speed,thenhard-disk,thenram51280160250250200250250160250300250320204810245121024204810241024102420485121024Exercise14.6.2(5.3.2)SpeedRamHd2.6610242502.105122501.42512802.8010242503.205122503.2010243202.2010242002.2020482502.0010242502.8020483001.8620481602.801024160Speed2.70Ram1500Ram1500Speed3.00Speed2.152.105121.425122.6610242.202048Ram8002.0010242.2020481.8620482.8020482.8010242.8010243.205123.201024Exercise14.6.2(5.3.2)Speed2.50Ram1500Ram800hd280

hd3001.42512802.201024320Speed1.802.0010242502.105122502.2020482501.8620481603.205122502.8020483003.2010243202.661024250Speed2.702.8010242502.801024160Exercise14.7.2(5.4.2)Wefirstfindthebit-vectorsfortheagevaluesintherange[40,60],therearethreebit-vectors:0,0,1,for45,50,60,respectively.IfwetaketheirbitwiseOR,wecanhaveanewbit-vector:1,inwhich1isinpositioniifandonlyiftheithrecordhasanageinthedesiredrange.wefindthebit-vectorsforthesalariesbetween100and200thousand.Therearefourbit-vectors:0,0,0,0,correspondingtosalaries100,110,120and140.TheirbitwiseORis0.wetakethebitwiseANDofthetwobit-vectors:1and0,thenwecanhave1AND0=0,whichmeansthefourthandfifthrecords,(50,100),(50,120),arethetargets.Chapter15Exercise15.2.1(6.3.1)Open()PerformR1.Open()andinitializetoemptythesetS.

GetNext()IfCurRel=R1thenperformt=R1.GetNext().IfFound=True,theninserttintoSandreturnt.IfFound=False,thenR1isexhausted.PerformR1.Close(),R2.Open(),setCurRel=R2,andrepeatedlyperformt=R2.GetNext()untileithertisinS,inwhichcasedeletethetinS,orFound=False,inwhichcasejustreturn.Close():PerformR2.Close().Exercise15.3.2(6.4.3)SupposeB(R)=B(S)=10000,B(S)+(B(S)×B(R))/(M-1)<=200000M>=528Exercise15.4.4(6.5.3)3(B(R)+B(S))=3×20,000=60,000Exercise15.5.1(6.6.2)(3-2M/B(S))(B(R)+B(S))=(3-2×500/10000)(10000+10000)=58000.(AssumingB(S)<=B(R))Theindexisnotclustering,thecostisT(R)/V(R,a)=500000/kTheindexisclustering,thecostisB(R)/V(R,a)=10000/kRisclustered,andtheindexisnotused,thecostisB(R)=10000Two-pass,sort-basedjoinMax(B(R),B(S))<=(M/2)2=M2/4&B(R)+B(S)<=(M/2)2=M2/4Exercise15.7.1(6.8.1)Chapter16Exercise16.1.3(7.1.3)<Query>SELECT<SelList>FROM<FromList>WHERE<Condition><Attribute><RelName><Attribute>IN()aRb<Query>aRSR.bS.bSELECT<SelList>FROM<FromList>WHERE<Condition><Attribute><RelName>,<RelName><Attribute>=<Attribute>Exercise16.1.3(7.1.3)<Query>SELECT<SelList>FROM<FromList>WHERE<Condition><Attribute>,<Attribute><RelName>,<RelName><Attribute>=<Attribute>acRSR.bS.bR(a,b)={(1,2),(1,3)}dR=R,pa(dR)={(1),(1)}paR={(1),(1)},d(paR)={(1)},notequalR(a,b)={(1,2),(1,2)},S(a,b)={(1,2)}

R-BS={(1,2)},d(R-BS)={(1,2)};(dR)–B(dS)={(1,2)}–B{(1,2)}=,notequal.RBS={(1,2),(1,2),(1,2)},d(RBS)={(1,2)};(dR)B(dS)={(1,2)}B{(1,2)}={(1,2),(1,2)},notequal.R(a,b)={(1,2)},S(a,b)={(1,3)}pa(R-S)={(1)}paR-paS={(1)}-{(1)}=,notequalExercise16.2.1(7.2.2)

paRR.b=a(pa(R

S))

pa,c(R

R.b=S.bS)

Exercise16.3.1(7.3.2)pasR<Condition><Attribute>INpabR.b=S.bRSpaR.b=aRpaR.b=S.bRS(R(a,b)S(b,c))(T(c,d)U(a,d))=pR.a->a,R.b->b,S.c->c,T.d->d(RSTU)

Commutativenotassociativegroup

Exercise16.3.2(7.3.1)FornaturaljoinR(X,Y)⋈S(Y,Z),thecostis:T(R⋈S)=T(R)T(S)/max(V(R,Y),V(S,Y)) sothecostofW⋈X⋈Y⋈Z

canbeeveluatedby： T(W⋈X⋈Y⋈Z)=T(W)T(X)/max(V(W,b),V(X,b))· T(X)T(Y)/max(V(X,c),V(Y,c))· T(Y)T(Z)/max(V(Y,d),V(Z,d)) =20000T(σa=10(W))=T(W)/V(W,a)=8T(σc=20(Y))=T(Y)/V(Y,c)=4T(σc=20(Y)⋈Z) =T(σc=20(Y))T(Z)/max(V(σc=20(Y),d),V(Z,d))=40T(W×Y)=T(W)T(Y)=80000T(σd>10(Z))=T(Z)/3≈33T(σa=1ANDb=2(W)T(σa=1ANDb>2(W))=T(W)/(V(W,a)·3)≈T(X⋈Y)=T(X)T(Y)/3=20000ThefrequencyoftheothersinRis36/(20-4),inSis50/(20-4).Sotheoutputsize:5×10+4×8+10×5+5×50/16+7×36/16+15×(36/16×50/16)≈269ThesimplerestimateisT(RS)=T(R)T(S)/max(V(R,b),(S,b))=60×80/20=240269>240Exercise16.5.1(7.5.1)01234others----------------------------------------------R.b 5410536S.b1085750LeftdeeptreesonlyExercise16.6.1(7.6.1){W}{X}{Y}{Z}大小400=T(W)300200100最小代价0000最优组合WXYZ{W,X}{W,Y}{W,Z}{X,Y}{X,Z}{Y,Z}大小2000=T(W)×T(X)/max{V(W,b),V(X,b)}8000040000600300001000最小代价000000最优组合WXWYWZXYXZYZW(a,b)X(b,c)Y(c,d)Z(d,e)T(W)=400T(X)=300T(Y)=200T(Z)=100V(W,a)=50V(X,b)=60V(Y,c)=50V(Z,d)=10V(W,b)=40V(X,c)=100V(Y,d)=20V(Z,e)=50LeftdeeptreesonlyExercise16.6.1(7.6.1){W,X,Y}{W,X,Z}{W,Y,Z}{X,Y,Z}大小4000=T(W)×T(X)×T(Y)/max{V(W,b),V(X,b)}/max{V(X,c),V(Y,c)}2000004000003000最小代价600=T(X)×T(Y)/max{V(X,c),V(Y,c)}20001000600最优组合(XY)W(WX)Z(YZ)W(XY)Z代价((XY)W)Z4600=T(X)×T(Y)/max{V(X,c),V(Y,c)}+T(W)×T(X)×T(Y)/max{V(W,b),V(X,b)}/max{V(X,c),V(Y,c)}((WX)Z)Y202000((YZ)W)X401000((XY)Z)W3600AlltreesLeft-deeptreeshavebeendiscussedRight-deeptreesbushyExercise16.6.1(7.6.1)TheExampleofGroupsCostX(Y(ZW))600=T(X)+T(Y)+T(Z)X(Y(WZ))900=T(X)+T(Y)+T(W)X(Z(WY))800=T(X)+T(Z)+T(W)Y(Z(WX))700=T(Y)+T(Z)+T(W)GroupsCost(WX)(YZ)3000=T(W)×T(X)/max{V(W,b),V(X,b)}+T(Y)×T(Z)/max{V(Y,d),V(Z,d)}(ZX)(YW)110000=T(Z)×T(X)+T(Y)×T(W)(XY)(ZW)40600=T(X)×T(Y)/max{V(X,c),V(Y,c)}+T(Z)×T(W)1.tablescan:B(R)=5002.aindex.a=1:B(R)/V(R,a)=103.cb=2:T(R)/V(R,b)=54.cindex.c>=3:T(R)/3=1667故最佳查询计划为第三种。即搜索所有b=2的元组，另外两个条件过滤，代价为5次I/O1.tablescan:B(R)=5002.aindex.a=1:B(R)/V(R,a)=103.aindex.b<=2:T(R)/3=16674.cindex.c>=3:T(R)/3=1667

故最佳查询计划为第二种。即搜索所有a=1的元组，另外两个条件过滤，代价为10次I/OExercise16.7.1(7.7.1)Chapter17i.Sistheonlyactivetransaction,sothelogrecordis<STARTCKPT(S)>.Wecanwritethe<ENDCKPT>recordafterthe<COMMITS>record.ii.Ifthecrashoccursafterthattime,wehavetosearchbackonlytothe<STARTCKPT(S)>.Thesearchmustcontinuebackasfarasthe<STARTS>record.i.Tistheonlyactivetransaction,sothelogrecordis<STARTCKPT(T)>.Wecanwritethe<ENDCKPT>recordafterthe<COMMITT>record.ii.Ifthecrashoccursafterthattime,wehavetosearchbackonlytothe<STARTCKPT(T)>.However,forcrashespriortothe<COMMITT>record,thesearchmustcontinuebackasfarasthe<STARTT>record,sincethatisthe(lone)transactionthatwasactiveatthestartofthecheckpoint.Exercise17.2.7(8.2.7)Thereareseveneventsofinterest,whichweshallcall:A:databaseelementAiswrittentodisk.B:databaseelementBiswrittentodisk.C:databaseelementCiswrittentodisk.LA:thelogrecordforAiswrittentodisk.LB:thelogrecordforBiswrittentodisk.LC:thelogrecordforCiswrittentodisk.D:thecommitrecordiswrittentodisk.Withredologging,thewritingoftheelementsAandBmustoccurafteralllogrecordsarewritten.Thus,theonlyoptioniswhichelementgetswrittenfirst,andthelegalsequencesofeventsareLA,LB,D,A,BandLA,LB,D,B,A.Exercise17.3.3(8.3.2)Legalsequencesofeventsare: LA,LB,LC,D,A,B,C LA,LB,LC,D,B,A,C LA,LB,LC,D,C,B,A LA,LB,LC,D,C,A,B LA,LB,LC,D,A,C,B LA,LB,LC,D,B,C,AExercise17.3.3(8.3.2)

i.TheENDCKPTrecordcouldappearanywhereaftertherecord<S,A,60,61>.Thereasonisthatthewritingofdirtyblockscanbeperformedindependentofwhateveractionsthetransactionsareperformingintheinterrumii.TheonlyactivetransactionwhenthecheckpointbeganwasS.IfthecrashoccursaftertheENDCKPT,thenweneedonlygobackasfarasthe<STARTCKPT(S)>.However,ifthecrashoccursbetweenthe<COMMITS>andthe<ENDCKPT>,weneedgobacktothe<STARTCKPT(S)>,whileweneedgobacktothe<STARTS>,ifthecrashoccursbefore<COMMITS>.

Exercise17.4.4(8.4.5)

i.TheENDCKPTrecordcouldappearanywhereaftertherecord<T,E,50,51>.Thereasonisthatthewritingofdirtyblockscanbeperformedindependentofwhateveractionsthetransactionsareperformingintheinterrumii.TheactivetransactionswhenthecheckpointbeganwereTandV.IfthecrashoccursaftertheENDCKPT,thenweneedonlygobackasfarasthe<STARTCKPT(T,V)>.However,ifthecrashoccursbeforethecheckpointended,thenwemustlookbacktothe<STARTT>.Exercise17.4.4(8.4.5)Chapter18(T1,T2)R(A,t);t:=t+2;W(A,t);R(A,s);s:=s+3;W(A,s);R(B,t);t:=t*3;W(B,t);R(B,s);s:=s*2;W(B,s)2serialschedulesand402serializableschedules

Exercise18.2.1(9.2.1)(T1,T2):T1:R(A,t);t:=t+2;W(A,t);|R(B,t);t:=t*3;W(B,t);A0+23B0T2:R(B,s);s:=s*2;W(B,s);|R(A,s);s:=s+3;W(A,s);6B0A0+5(T2,T1):T2:R(B,s);s:=s*2;W(B,s);|R(A,s);s:=s+3;W(A,s);2B0A0+3T1:R(A,t);t:=t+2;W(A,t);|R(B,t);t:=t*3;W(B,t);A0+56B0

ThethreewritescreatethreeversionsofA.WhenT2triestoreadA,itisgiventhevaluethatititselfwrote,sincethatistheversionwiththegreatesttimestampthatdoesnotexceedthetimestampofT2.Thatmakessense,althoughinpractice,wedoubtthatawellwrittentransactionwouldreaditsownvaluethroughthedatabasestoragesystem.WhenT4triestoreadAthesystemfindsthatT4'stimestampislargerthanthatofanyversionofAwritten.Thus,T4getstheversionwiththelargestofthetimestamps,theonewrittenbyT3.Thatmakessense,becauseinthehypotheticalserialorderbasedonthetimestampsofthetransactions,T3wouldbethelasttowriteA.Exercise18.8.3(9.8.2)

AsT1isthefirsttovalidate,thereisnothingtocheck;T1validatessuccessfully.T3validatesnext.TheonlyothervalidatedtransactionisT1,andT1hasnotyetfinished.Thus,boththeread-andwrite-setsofT3mustbecomparedwiththewrite-setofT1.However,T1writesonlyA,andT3neitherreadsnorwritesA,soT3'svalidationsucceeds.Last,T2validates.BothT1andT3finishafterT2started,sowemustcomparetheread-setofT2withthewrite-setsofbothT1andT3.SinceBisinbothW3andR2,wecannotvalidateT2.NotethatsinceT3(butnotT1)finishesafterT2validates,wewouldalsocomparethewritesetofT2withthewritesetofT3,hadwenotalreadyfoundareasonnottovalidateT2.Exercise18.9.1(9.9.1)

T1validates(noothervalidatedtransaction).WriteA.T3.(T1isvalidated,butnotfinished.RS(T3)&WS(T3)VSWS(T1))RS(T3)={C,D};WS(T3)={D}.WS(T1)={A};Exercise18.9.1(9.9.1)T1RS={A,B}WS={A}T3

RS={C,D};WS={D}T2RS={B,C}WS={A}RS(T3)∩WS(T1)=Ф&WS(T3)∩WS(T1)=ФSo,T3validates.WriteD.iii>T2.(T1finished,butT2startsbeforet1finished,soRS(T2)shouldbecomparedagainstWS(T1).AndRS(T3)&WS(T3)mustbecomparedwithWS(T2))RS(T2)={B,C};WS(T2)={A}.WS(T1)={A};WS(T3)={D};RS(T2)∩WS(T1)=Ф&WS(T2)∩WS(T3)=Ф&RS(T2)∩WS(T3)=ФT2validates.WriteA.Chapter19Exercise19.1.2(10.1.2)

T1wroteonlyB,butthatvaluewaslaterreadbyT3.Thus,T3mustberolledback.T3wroteC,andCwaslaterreadbyT2.Thus,T2mustberolledback.T2wroteD,butnotransactionhasreadD,sonofurtherrollbacksareneeded.T1