数据库系统实现(第二版_英文版)部分答案.ppt

SolutionsforDatabaseSystemImplementation,GanLinQQ:85906478Email:85906478,Chapter13,Thecapacityofthedisk?Thediskhas8100,000=800,000tracks.Theaveragetrackhas20001024=2048,000bytes.Thus,thecapacityis214108bytesThemaximumseektime?Themaximumseektimeoccurswhentheheadshavetomoveacrossallthetracks.Thus,substitute100,000tracts(really99999)fornintheformula1+.0003ntoget31(30.9997)ms.Themaximumrotationallatency?Themaximumrotationallatencyisonefullrevolution.Sincethediskrotatesat6,000rpm,ittakes1/6000ofaminute,or0.01storotate.,Exercise13.2.1(2.2.1),Transfertimeofablock?Sinceatrackhas2000sectorsand2000gaps,and10%ofatrackisusedforgaps,thereare36oforgapsand324oforsectorsofatrackcircle.Sothereare36o/2000foreachgapand324o/2000foreachsector.Thisblockis65546bytes(i.e.64sectors),theheadsmustthereforepassover63gapsand64gaps,i.e.6336o/2000+64324o/2000.Asthemaximumrotationallatencyis0.01s,wecanhavethetransfertimeoftheblockis(6336o/2000+64324o/2000)0.01/360o=0.0003195sor0.3195ms.,Exercise13.2.1(2.2.1),Theaverageseektime?Theaveragenistracks/3ofasurface,i.e.100,000/3.Sotheaverageseektimeis1+.0003n=1+.0003100,000/3=11ms.Theaveragerotationallatency?Theaveragerotationallatencyis0.01/2=0.005sTheaveragedensityofbitsinthesectorsofaoutertrack？Atrackhas2000sectors,eachsectorholds1024bytes,andeverybytetakes8bits,soatrackis200010248bits.Forthe3.5inchdisk,thedensityoftheoutertrackis200010248/(3.590%)=1655615.6394bit/inch.,Exercise13.2.1(2.2.1),Theaveragetrackstheheadshavetomove:(1+2+4095)+(1+2+(65536-4096)/6553628928Seektime:1+28928/4000=8.232msTransfertime=0.13msRotationallatency=4.17msAverageseektime+averagerotationallatency+averagetransfertime=12.532ms,Exercise13.2.4(2.2.2),Seektime=1+tracks/4000Transfertime=0.13Rotationallatency=4.17Completetime=dealtime+seektime+transfertime+rotationallatency,Exercise13.3.1(2.4.1),块传输时间为0.13ms，平均旋转等待时间为4.17ms，平均寻道时间为1+65536/(340002)=3.72ms，所以平均读取一个块的时间为8.02ms无约束的megatron镜像平均速度提高1倍，所以平均读取时间约为10.76/2=5.38ms该系统缺陷主要在于无法同时处理同侧柱面的读取请求，大量同侧请求到来时会导致一边队列累积而另一边空闲,Exercise13.3.2,Exercise13.4.9(2.6.7),Modulo-2sumofthenewvalue01111111andtheoldvalue01010101is00101010,Exercise13.5.3(3.2.2)8+25+1+10=44bytes8+32+8+16=64bytes8+28+4+12=52bytesExercise13.6.5(3.3.4)IPaddress48=32bits=4BDevicenumber14bits=2B(as213n，如果分裂前的数据为0000-0011，则分裂后数据仍全归于前两位为00的块，仍需递归分裂,Exercise14.3.4,Exercise14.3.5(4.4.6),Exercise14.3.5(4.4.6),Exercise14.5.1(5.2.1),若同一条线上多于两个点，则必须分开。180,280,2.15,2.5,3230,280,2.15,2.7,Exercise14.5.5(5.2.5),46=24Thedistancebetween(110,245)and(115,230)issqrt(250),i.e.(15,16)Lowleftcorner(80,200)(80,250)(100,250)(120,250)(120,200),Exercise14.6.1,Showamultiple-keyindexforthedataofthetableiftheindexesareon：Ram,thenhard-disk.Speed,thenramSpeed,thenhard-disk,thenram,Exercise14.6.1,Ram,thenhard-disk,512,1024,2048,80,250,160,200,250,320,160,250,300,Exercise14.6.1,b)Speed,thenram,1.42,1.86,2.00,2.10,2.20,2.66,2.80,3.20,512,2048,1024,512,1024,2048,1024,1024,2048,512,1024,Exercise14.6.1,Speed,thenhard-disk,thenram,512,1.42,1.86,2.00,2.10,2.20,2.66,2.80,3.20,80,160,250,250,200,250,250,160,250,300,250,320,2048,1024,512,1024,2048,1024,1024,1024,2048,512,1024,Exercise14.6.2(5.3.2),Exercise14.6.2(5.3.2),Exercise14.7.2(5.4.2),Wefirstfindthebit-vectorsfortheagevaluesintherange40,60,therearethreebit-vectors:010000000100,001110000010,000000000001,for45,50,60,respectively.IfwetaketheirbitwiseOR,wecanhaveanewbit-vector:011110000111,inwhich1isinpositioniifandonlyiftheithrecordhasanageinthedesiredrange.wefindthebit-vectorsforthesalariesbetween100and200thousand.Therearefourbit-vectors:000100000000,000001000000,000010000000,000000100000,correspondingtosalaries100,110,120and140.TheirbitwiseORis000111100000.wetakethebitwiseANDofthetwobit-vectors:011110000111and000111100000,thenwecanhave011110000111AND000111100000=000110000000,whichmeansthefourthandfifthrecords,(50,100),(50,120),arethetargets.,Chapter15,Exercise15.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)=528Exercise15.4.4(6.5.3)3(B(R)+B(S)=320,000=60,000Exercise15.5.1(6.6.2)(3-2M/B(S)(B(R)+B(S)=(3-2500/10000)(10000+10000)=58000.(AssumingB(S)=B(R),Exercise15.6.1,Theindexisnotclustering,thecostisT(R)/V(R,a)=500000/kTheindexisclustering,thecostisB(R)/V(R,a)=10000/kRisclustered,andtheindexisnotused,thecostisB(R)=10000,Two-pass,sort-basedjoinMax(B(R),B(S)=(M/2)2=M2/4t:=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.WhenT4triestoreadAthesystemfindsthatT4stimestampislargerthanthatofanyversionofAwritten.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,soT3svalidationsucceeds.Last,T2validates.BothT1andT3finishafterT2started,sowemustcomparetheread-setofT2withthewrite-setsofbothT1andT3.SinceBisinbothW3andR2,wecannotvalidateT2.NotethatsinceT3(butnotT1)finishesafterT2validates,wewouldalsocomparethewritesetofT2withthewritesetofT3,hadwenotalreadyfoundareasonnottovalidateT2.,Exercise18.9.1(9.9.1),T1valida