数据库系统实现习题答案市公开课金奖市赛课一等奖课件

Chapter15第1页Exercise15.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(){.}第2页Exercise15.2.3.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)<=00M>=528第3页Exercise15.3.4Open(){R.Open();S.Open();s:=S.getNext();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();}第4页Exercise15.4.2.asqrt(0)=142Exercise15.4.5当子表数小于M时，有额外缓冲区。在每次读子表时，能够将子表其它块同时读入缓冲区，在进行归并时，假如某个子表S所在一个缓冲区块读完之后，直接使用该子表S保留于额外缓冲区下一块进行归并，而不用再从S所在磁盘中读取到内存。第5页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也均是10000*20/21，另外条一趟读S和R代价均为10000，故总代价为：2*10000+2*(10000*20/21+10000*20/21)=58096第6页Exercise15.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。进行散列时，桶中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个块必须小于或等于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=34393ms第7页Exercise15.6.4.a表扫描I/O为：10000 索引扫描I/O为：T(R)/k=500000/k500000/K<=10000时，即k>=50，用索引扫描;不然用表扫描Exercise15.6.5对三种连接都会首先进行选择操作，得到R中满足条件元组，共3个。即做选择操作代价都一样。现在将R看成仅有3条元组关系，对比3三种连接方法。认为B(R)=0基于排序：两趟排序代价:3(B(R)+B(S))=3B(S)基于HASH：因为对3个元组进行Hash代价为0，故对S中每个元组一旦Hash到对应桶中即可进行连接输出，并不用写回磁盘，故代价为B(S)基于索引：假如索引聚簇则代价为T(R)B(S)/V(S,name)，假如索引是非聚簇则代价为T(R)T(S)/V(S,name)。因为同名电影明星极少，所以T(S)/V(S,name)比1略大，所以基于索引代价约为3综上可知，基于索引代价最小，其次为Hash，最终是排序第8页

第9页Exercise1