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

《数据库系统实现(第二版-英文版)部分答案.ppt》由会员分享，可在线阅读，更多相关《数据库系统实现(第二版-英文版)部分答案.ppt（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Gan LinQQ:85906478a)The capacity of the disk?The disk has 8 100,000=800,000 tracks.The average track has 2000 1024=2048,000 bytes.Thus,the capacity is 214 108 bytes b)The maximum seek time?The maximum seek time occurs when the heads have to move across all the tracks.Thus,substitute 100,000 tracts(r

2、eally 99999)for n in the formula 1+.0003n to get 31(30.9997)ms.c)The maximum rotational latency?The maximum rotational latency is one full revolution.Since the disk rotates at 6,000 rpm,it takes 1/6000 of a minute,or 0.01s to rotate.d)Transfer time of a block?Since a track has 2000 sectors and 2000

3、gaps,and 10%of a track is used for gaps,there are 36o for gaps and 324o for sectors of a track circle.So there are 36o/2000 for each gap and 324o/2000 for each sector.This block is 65546 bytes(i.e.64 sectors),the heads must therefore pass over 63 gaps and 64 gaps,i.e.6336o/2000+64324o/2000.As the ma

4、ximum rotational latency is 0.01s,we can have the transfer time of the block is(6336o/2000+64324o/2000)0.01/360 o=0.0003195s or 0.3195ms.e)The average seek time?The average n is tracks/3 of a surface,i.e.100,000/3.So the average seek time is 1+.0003n=1+.0003100,000/3=11ms.f)The average rotational la

5、tency?The average rotational latency is 0.01/2=0.005sg)The average density of bits in the sectors of a outer track？A track has 2000 sectors,each sector holds 1024 bytes,and every byte takes 8 bits,so a track is 200010248 bits.For the 3.5 inch disk,the density of the outer track is 200010248/(3.5 90%

6、)=1655615.6394 bit/inch.The average tracks the heads have to move:(1+2+4095)+(1+2+(65536-4096)/6553628928Seek time:1+28928/4000=8.232msTransfer time=0.13msRotational latency=4.17msAverage seek time+average rotational latency+average transfer time=12.532ms4096655361Seek time=1+tracks/4000Transfer tim

7、e=0.13Rotational latency=4.17Complete time=deal time+seek time+transfer time+rotational latencyCylinder of requestFirst time availableE Seek timeElevatorE RankF Seek timeFCFSFCFS Rank8,000037.3137.3148,00011122.621122.624,00010329.941238.9340,000201044.231053.24a)块传输时间为0.13ms，平均旋转等待时间为4.17ms，平均寻道时间为

8、1+65536/(340002)=3.72ms，所以平均读取一个块的时间为8.02msb)无约束的megatron镜像平均速度提高1倍，所以平均读取时间约为10.76/2=5.38msc)该系统缺陷主要在于无法同时处理同侧柱面的读取请求，大量同侧请求到来时会导致一边队列累积而另一边空闲Data disksRedundantDisk 1Disk 2Disk 3Disk 4Disk 5Disk 6Disk 7111010011010101011001DiskContents100110100211100111301010101410000100510000110601010111711100101

9、DiskContents100110100211100111301111111410000100510101100601010111711001111Modulo-2 sum of the new value 01111111 and the old value 01010101 is 00101010Exercise 13.5.3(3.2.2)8+25+1+10=44 bytes8+32+8+16=64 bytes8+28+4+12=52 bytesExercise 13.6.5(3.3.4)IP address 48=32bits=4BDevice number 14 bits=2B (a

10、s 21310,0002n，例如散列键值为四位数，且某块j值为1，存储第一位为0的数据，但n=3，而可能存储的数据为0000-0111共有8条数据。分裂后每个子块最多有4条数据，仍然n，如果分裂前的数据为0000-0011，则分裂后数据仍全归于前两位为00的块，仍需递归分裂a)b)c)d)若同一条线上多于两个点，则必须分开。180,280,2.15,2.5,3230,280,2.15,2.746=24The distance between(110,245)and(115,230)is sqrt(250),i.e.(15,16)Low left corner(80,200)(80,250)(1

11、00,250)(120,250)(120,200)Show a multiple-key index for the data of the table if the indexes are on：a)Ram,then hard-disk.b)Speed,then ramc)Speed,then hard-disk,then ram型号型号速度速度内存内存硬盘硬盘10012.66102425010022.1051225010031.425128010042.80102425010053.2051225010063.20102432010072.20102420010082.2020482501

12、0092.00102425010102.80204830010111.86204816010122.801024160a)Ram,then hard-disk5121024204880250160200250320160250300b)Speed,then ram1.421.862.002.102.202.662.803.2051220481024512102420481024102420485121024a)Speed,then hard-disk,then ram5121.421.862.002.102.202.662.803.2080160250250200250250160250300

13、250320204810245121024204810241024102420485121024SpeedRamHd2.6610242502.105122501.42512802.8010242503.205122503.2010243202.2010242002.2020482502.0010242502.8020483001.8620481602.801024160Speed 2.70Ram 1500Ram 1500Speed 3.00Speed 2.152.10 5121.42 5122.66 10242.20 2048Ram 8002.00 10242.20 20481.86 2048

14、2.80 20482.80 10242.80 10243.20 5123.20 1024Speed 2.50Ram 1500Ram 800hd 280 hd 3001.42 512 802.20 1024 320Speed 1.802.00 1024 250 2.10 512 2502.20 2048 2501.86 2048 1603.20 512 2502.80 2048 3003.20 1024 3202.66 1024 250Speed 2.702.80 1024 250 2.80 1024 160OR,we can have a new bit-vector:,in which 1

15、is in position i if and only if the ith record has an age in the desired range.we find the bit-vectors for the salaries between 100 and 200 thousand.There are four bit-vectors:000100000000,000001000000,000010000000,000000100000,corresponding to salaries 100,110,120 and 140.Their bitwise OR is 000111

16、100000.,which means the fourth and fifth records,(50,100),(50,120),are the targets.Open()Perform R1.Open()and initialize to empty the setS.GetNext()If CurRel=R1 then perform t=R1.GetNext().If Found=True,then insert t into S and return t.If Found=False,then R1 is exhausted.Perform R1.Close(),R2.Open(

17、),set CurRel=R2,and repeatedly perform t=R2.GetNext()until either t is in S,in which case delete the t in S,or Found=False,in which case just return.Close():Perform R2.Close().Exercise 15.3.2(6.4.3)Suppose B(R)=B(S)=10000,B(S)+(B(S)B(R)/(M-1)=528Exercise 15.4.4(6.5.3)3(B(R)+B(S)=320,000=60,000Exerci

18、se 15.5.1(6.6.2)(3-2M/B(S)(B(R)+B(S)=(3-2500/10000)(10000+10000)=58000.(Assuming B(S)=B(R)a)The index is not clustering,the cost isT(R)/V(R,a)=500 000/kb)The index is clustering,the cost is B(R)/V(R,a)=10 000/kc)R is clustered,and the index is not used,the cost isB(R)=10 000c)Two-pass,sort-based joi

19、nMax(B(R),B(S)=(M/2)2=M2/4&B(R)+B(S)=(M/2)2=M2/4Exercise 15.7.1(6.8.1)SELECT FROM WHERE IN ()a R b a R S R.b S.b SELECT FROM WHERE ,=SELECT FROM WHERE,=a c R S R.b S.ba)R(a,b)=(1,2),(1,3)dR=R,pa(dR)=(1),(1)pa R=(1),(1),d(pa R)=(1),not equalb)R(a,b)=(1,2),(1,2),S(a,b)=(1,2)R-BS=(1,2),d(R-BS)=(1,2);(d

20、R)B(dS)=(1,2)B(1,2)=,not equal.RBS=(1,2),(1,2),(1,2),d(RB S)=(1,2);(dR)B(dS)=(1,2)B(1,2)=(1,2),(1,2),not equal.d)R(a,b)=(1,2),S(a,b)=(1,3)pa(R-S)=(1)pa R-pa S=(1)-(1)=,not equala)pa R R.b=a(pa(R R.b=S.b S)a)pa,c(R R.b=S.b S)pasR IN pa b R.b=S.b R Spa R.b=a R pa R.b=S.b R Sc)(R(a,b)S(b,c)(T(c,d)U(a,d

21、)=pR.a-a,R.b-b,S.c-c,T.d-d(R S T U)Commutative not associative group R.b=S.bS.c=T.cR.a=U.cT.d=U.da)For natural join R(X,Y)S(Y,Z),the cost is:T(RS)=T(R)T(S)/max(V(R,Y),V(S,Y)so the cost of WXYZ can be eveluated by：T(WXYZ)=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)=

22、20000b)T(a=10(W)=T(W)/V(W,a)=8c)T(c=20(Y)=T(Y)/V(Y,c)=4d)T(c=20(Y)Z)=T(c=20(Y)T(Z)/max(V(c=20(Y),d),V(Z,d)=40e)T(WY)=T(W)T(Y)=80000f)T(d10(Z)=T(Z)/3 33g)T(a=1 AND b=2(W)=T(W)/(V(W,a)V(W,b)=0.2c)T(a=1 AND b2(W)=T(W)/(V(W,a)3)2.67d)T(XX.c240 0 1 2 3 4 others-R.b 5 4 10 5 36S.b 10 8 5 7 50a)Left deep t

23、rees onlyWXYZ大小400=T(W)300 200 100最小代价0000最优组合WXYZW,XW,YW,ZX,YX,ZY,Z大小2000=T(W)T(X)/maxV(W,b),V(X,b)8000040000 60030000 1000最小代价000000最优组合W XW YW ZX YX ZY ZW(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)=50Left deep trees

24、 onlyW,X,YW,X,ZW,Y,ZX,Y,Z大小4000=T(W)T(X)T(Y)/maxV(W,b),V(X,b)/maxV(X,c),V(Y,c)2000004000003000最小代价600=T(X)T(Y)/maxV(X,c),V(Y,c)20001000600最优组合(X Y)W(W X)Z(Y Z)W(X Y)Z代价(X Y)W)Z4600=T(X)T(Y)/maxV(X,c),V(Y,c)+T(W)T(X)T(Y)/maxV(W,b),V(X,b)/maxV(X,c),V(Y,c)(W X)Z)Y202000(Y Z)W)X401000(X Y)Z)W3600b)All t

25、reesLeft-deep trees have been discussedRight-deep treesbushyThe Example of GroupsCost X (Y (Z W)600=T(X)+T(Y)+T(Z)X (Y (W Z)900=T(X)+T(Y)+T(W)X (Z (W Y)800=T(X)+T(Z)+T(W)Y (Z (W X)700=T(Y)+T(Z)+T(W)Groups Cost(W X)(Y Z)3000=T(W)T(X)/maxV(W,b),V(X,b)+T(Y)T(Z)/maxV(Y,d),V(Z,d)(Z X)(Y W)110000=T(Z)T(X)

26、+T(Y)T(W)(X Y)(Z W)40600=T(X)T(Y)/maxV(X,c),V(Y,c)+T(Z)T(W)a)1.table scan:B(R)=5002.a index.a=1:B(R)/V(R,a)=103.c b=2:T(R)/V(R,b)=54.c index.c=3:T(R)/3=1667 故最佳查询计划为第三种。即搜索所有b=2的元组，另外两个条件过滤，代价为5次I/Ob)1.table scan:B(R)=5002.a index.a=1:B(R)/V(R,a)=103.a index.b=3:T(R)/3=1667 故最佳查询计划为第二种。即搜索所有a=1的元组，另

27、外两个条件过滤，代价为10次I/Oa)i.S is the only active transaction,so the log record is.We can write the record after the record.ii.If the crash occurs after that time,we have to search back only to the.The search must continue back as far as the record.b)i.T is the only active transaction,so the log record is.W

28、e can write the record after the record.ii.If the crash occurs after that time,we have to search back only to the.However,for crashes prior to the record,the search must continue back as far as the record,since that is the(lone)transaction that was active at the start of the checkpoint.There are sev

29、en events of interest,which we shall call:A:database element A is written to disk.B:database element B is written to disk.C:database element C is written to disk.LA:the log record for A is written to disk.LB:the log record for B is written to disk.LC:the log record for C is written to disk.D:the com

30、mit record is written to disk.a)With redo logging,the writing of the elements A and B must occur after all log records are written.Thus,the only option is which element gets written first,and the legal sequences of events are LA,LB,D,A,B and LA,LB,D,B,A.b)Legal sequences of events are:LA,LB,LC,D,A,B

31、,CLA,LB,LC,D,B,A,CLA,LB,LC,D,C,B,ALA,LB,LC,D,C,A,B LA,LB,LC,D,A,C,BLA,LB,LC,D,B,C,Aa)i.The END CKPT record could appear anywhere after the record.The reason is that the writing of dirty blocks can be performed independent of whatever actions the transactions are performing in the interrumii.The only

32、 active transaction when the checkpoint began was S.If the crash occurs after the END CKPT,then we need only go back as far as the.However,if the crash occurs between the and the,we need go back to the,while we need go back to the,if the crash occurs before.e)i.The END CKPT record could appear anywh

33、ere after the record.The reason is that the writing of dirty blocks can be performed independent of whatever actions the transactions are performing in the interrumii.The active transactions when the checkpoint began were T and V.If the crash occurs after the END CKPT,then we need only go back as fa

34、r as the.However,if the crash occurs before the checkpoint ended,then we must look back to the.a)(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)b)2 serial schedules and 402 serializable schedulesd)(T1,T2):T1:R(A,t);t:=t+2;W(A,t);|R(B,t);t:=t*3;W(B,t);A0+2 3

35、B0T2:R(B,s);s:=s*2;W(B,s);|R(A,s);s:=s+3;W(A,s);6B0 A0+5(T2,T1):T2:R(B,s);s:=s*2;W(B,s);|R(A,s);s:=s+3;W(A,s);2B0 A0+3T1:R(A,t);t:=t+2;W(A,t);|R(B,t);t:=t*3;W(B,t);A0+5 6B0c)The three writes create three versions of A.When T2 tries to read A,it is given the value that it itself wrote,since that is t

36、he version with the greatest timestamp that does not exceed the timestamp of T2.That makes sense,although in practice,we doubt that a well written transaction would read its own value through the database storage system.When T4 tries to read A the system finds that T4s timestamp is larger than that

37、of any version of A written.Thus,T4 gets the version with the largest of the timestamps,the one written by T3.That makes sense,because in the hypothetical serial order based on the timestamps of the transactions,T3 would be the last to write A.d)uAs T1 is the first to validate,there is nothing to ch

38、eck;T1 validates successfully.uT3 validates next.The only other validated transaction is T1,and T1 has not yet finished.Thus,both the read-and write-sets of T3 must be compared with the write-set of T1.However,T1 writes only A,and T3 neither reads nor writes A,so T3s validation succeeds.uLast,T2 val

39、idates.Both T1 and T3 finish after T2 started,so we must compare the read-set of T2 with the write-sets of both T1 and T3.Since B is in both W3 and R2,we cannot validate T2.Note that since T3(but not T1)finishes after T2 validates,we would also compare the write set of T2 with the write set of T3,ha

40、d we not already found a reason not to validate T2.e)T1 validates(no other validated transaction).Write A.T3.(T1 is validated,but not finished.RS(T3)&WS(T3)VS WS(T1)RS(T3)=C,D;WS(T3)=D.WS(T1)=A;T1 RS=A,BWS=AT3 RS=C,D;WS=DT2 RS=B,CWS=ARS(T3)WS(T1)=&WS(T3)WS(T1)=So,T3 validates.Write D.iii T2.(T1 fini

41、shed,but T2 starts before t1 finished,so RS(T2)should be compared against WS(T1).And RS(T3)&WS(T3)must be compared with WS(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)=T2 validates.Write A.a)T1 wrote only B,but that value was later read by T3.Thus,T3 must be roll

42、ed back.T3 wrote C,and C was later read by T2.Thus,T2 must be rolled back.T2 wrote D,but no transaction has read D,so no further rollbacks are needed.T1 T2 T3 -R1(A)W1(B)rollback R3(B)W3(C)rollback R2(C)W2(D)rollbackb)T1 wrote only B,but that value was later read by T3.Thus,T3 must be rolled back.T3

43、 wrote C,and C was later read by T2.Thus,T2 must be rolled back.T1 T2 T3 -R3(A)R2(A)R1(A)W1(B)rollback R3(B)R2(B)W3(C)R2(C)rollback rollbacka)Waits for graph:T1 T2 T3-sl1(A);R1(A)sl3(B);R3(B)sl2(C);R2(C)xl1(B);Denied xl3(C);Denied xl2(D);W2(D)T1T3T2T1T3T1a)Waits for graph:T1 T2 T3-sl1(A);R1(A)sl2(B)

44、;R2(B)sl3(C);R3(C)xl1(B);Denied xl2(C);Denied xl3(A);DeniedT1T2T3T1T2T1a)3*(40%+8%)=1.44b)The 90%of the accesses that are read-only require no messages,since there is a lock table and a copy at each site.The remaining 10%of the accesses require exclusive locks.Thus,each requires three messages between the originating site and each of the four other sites,a total of 12 messages.The average number of messages is 1.2.c)s=x=(n+1)/2=33s=3x=990%*3s+10%*3x=9