数据库系统实现 第15章习题答案.ppt

《数据库系统实现 第15章习题答案.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Chapter15Exercise15.2.1.aOpen(){R.open();将R在分组属性上排序，得到S[];len=size(S);s:=S[0];R.Close();cursor=0; }GetNext(){sum:=0;grplen=0;if(cursor>len)returnnotfound;j:=cursor;while(S[cursor][a]=S[j][a]){grplen++;sum+=s[j][b];j++;}.cursor:=j;returnS[cursor][a]sum/grplen;}Close(){.}Exercise15.2.3.

2、a假设R（X,Y）与S（Y,Z）连接1.读取R的所有元组，并用它们构造一个以Y为查找关键字的内存查找结构，并设置一个是否已连接的字段，将内存M-1块用于这一目的2.将S中每一块读到内存中的缓冲区，对S每个元组t，找到R中与t在Y所有属性上都符合的元组，将这些元组标记为joined，然后连接并输出。3.S扫描完毕后，将R中所有未标记为joined的元组和空元组连接并输出Exercise15.3.2.aB(S)+(B(S)×B(R))/(M-1)<=200000M>=528Exercise15.3.4Open(){R.Open();S.Open();s:=S.getN

3、ext();r:=R.getNext();R.Close();if(rorsisnotfound)empty:=1}GetNext(){if(empty=1)returnnotfound;REPEAT{与书上相同}UNTIL(r与s能连接);RETURNr和s的连接Close(){R.Close();S.Close();}Exercise15.4.2.asqrt(20000)=142Exercise15.4.5当子表数小于M时，有额外的缓冲区。在每次读子表时，可以将子表其它块同时读入缓冲区，在进行归并时，如果某个子表S所在的一个缓冲区块读完之后，直接使用该子表S保

4、存于额外缓冲区的下一块进行归并，而不用再从S所在磁盘中读取到内存。Exercise15.5.1(3-2M/B(S))(B(R)+B(S))=(3-2×500/10000)(10000+10000)=58000.B(S)/M=10000/500=20。但如果取20个桶，每个桶500个块，那么混合散列连接没有多余缓冲区用于存放一个完整的桶和其余19个桶的一个块，所以我们取21个桶，S和R每个桶的块数都是10000/21=477。对S和R，21个桶中都有20个桶写到磁盘中。所以S和R写回时的磁盘I/O均为10000*20/21，而第二趟读S和R的磁盘I/O也均是1000

5、0*20/21，另外条一趟读S和R代价均为10000，故总代价为：2*10000+2*(10000*20/21+10000*20/21)=58096Exercise15.5.5.a考虑最基本的情况：因为散列时每次读和写操作都是1个块为单位，而一个块的磁盘I/O时间为100.5ms，所以一块一块地处理磁盘总I/O时间为3(B(R)+B(S))*100.5=452250ms一次读或写连续的块则可以减少I/O时间。那么设桶数为k，可以在缓冲区中每个桶设置为t个块，并另外增加一个大小为t的块作为输入缓冲区，读取S和R时均读取连续t块。则(k+1)t<=101。进行散列时，

6、桶中的t个块满时就一次写回磁盘。由于读写都是以连续t个块为单位，一次读/写连续t块代价为(100+t/2)，完成整个表的读写次数为B/t。因此有：散列时读操作S：B(S)/t*(100+t/2),R:B(R)/t*(100+t/2)写回磁盘时，每次写回t个块，则写S：B(S)/t*(100+t/2)，同理R:B(R)/t*(100+t/2)再次读R和S时，一次读t块，则读S：B(S)/t*(100+t/2)，读R：B(R)/t*(100+t/2)总I/O时间3(100(B(S)+B(R))/t+(B(S)+B(R))/2)S每个桶的块数加上作为R的输入缓冲区的t个

7、块必须小于或等于M，即B(S)/k+t<=101；并且(k+1)t<=101，题目要求用尽量小的桶，读写尽量多的连续块，则取t=101/(k+1)，得到min(k)=6,t=14。总I/O时间最小:300*1500/14+3*1500/2=34393msExercise15.6.4.a表扫描I/O为：10000索引扫描I/O为：T(R)/k=500000/k500000/K<=10000时，即k>=50，用索引扫描;否则用表扫描Exercise15.6.5对三种连接都会首先进行选择操作，得到R中满足条件的元组，共3个。即做选择操作的代价都一样。现在将R看成仅有3条

8、元组的关系