数据库系统实现习题全

1、（达建松 2141280）习题2.2.1 M egatron 777磁盘具有以下特性：1）有10个盘面，每个盘面有100000个磁道。2）磁道平均有1000个扇区，每个扇区为1024字节3）每个磁道的20%被用于间隙。4）磁盘旋转为10000转/min。5）磁头移动n个磁道所需要的时间是1+0.0002n ms。回答下列有关Megatron777的问题。a）磁盘的容量是多少？b）如果磁道是在直径3.5英寸的圆面上，那么一个磁道的扇区中的平均位密度是多少？c）最大寻道时间是多少？d）最大旋转等待时间是多少？e）如果一个块是65536字节（即64扇区），一个块得传输时间是多少？f）平均寻道时间是多

2、少？g）平均旋转等待时间是多少？答案：a) 磁盘容量=盘面数*磁道数*扇区数*扇区容量=10*100000*1000*1024字节=210*109字节注释：已知1）有10个盘面，每个盘面有100000个磁道。2）磁道平均有1000个扇区，每个扇区为1024字节.b) 一个磁道存放存放1000*1024*8=8192000bits.直径为3.5英尺那么中间磁道直径为3.5/2（英寸） 中间扇区所占的周长是80*3.5/2（英寸）所以，每个磁道的扇区中的平均密度是 注释：已知： 2）磁道平均有1000个扇区，每个扇区为1024字节. 3）每个磁道的20%被用于间隙. c) 最大寻道时间是磁头跨越全

3、部柱面所花费的时间。即1+0.0002*99999=20.9998ms已知： 1）有10个盘面，每个盘面有100000个磁道。 5）磁头移动n个磁道所需要的时间是1+0.0002n ms。 d) 最大旋转等待时间是磁头旋转一圈的时间。即1/(10000/60)= 6ms已知： 4）磁盘旋转为10000转/min。e) 该块占用64个扇区，为此，磁头必须越过64个扇区和扇区之间的63个间隙。由于间隙合在一起占72度圆弧，而扇区覆盖剩余288度圆弧，则被它们覆盖的圆弧的总度数为： 72*(63/1000)+288*(64/1000)=22.968则传输时间是（22.968/360）*0.6ms=0

4、.03828ms已知：3）每个磁道的20%被用于间隙。2）磁道平均有1000个扇区 。d）中最大旋转等待时间为6ms。f) 磁头行进的平均距离是跨越柱面的1/3，则平均寻道时间是：1+0.001*（100000/3）=34.33msg) 平均旋转等待时间为磁盘旋转半周所需时间: (1/2)*6ms=3ms（潘达）习题2.3.1假设我们正在为Megatron747磁盘调度I/O请求，磁头的初始位置在磁道32000，图2-9的请求已经产生。在下列两种情况下，每一种请求在何时可以完全得到服务？a) 我们采用电梯调度算法（起初朝任何一个方向开始移动都是允许的）。b) 我们采用先到达先服务调度。请求的柱

5、面到达时间800004800014000104000020图2-9 4个块访问请求的到达时间Megatron747磁盘的平均寻道时间、旋转等待时间和传输时间分别为6.46、4.17和0.13（所有时间均以ms计算）。因为每个块访问导致0.13ms传输时间和4.17ms平均旋转等待时间，即无论寻道时间是多少，都需为每一次块访问加上4.3ms。寻道时间可通过Megatron747的规则计算：1+磁道数/4000（1+磁道数/500）。对于电梯调度算法，计算方式及结果如下。对柱面8000的第一个请求需要进行寻道，因为磁头初始位置不是8000。这样访问8000完成的寻道时间为1+(32000-8000

6、)/4000ms，即在时间1+(32000-8000)/4000+4.3=11.3ms处第一次访问将完成。在此之前，对柱面48000和4000访问的请求分别于第1和第10时间到达，由于沿着柱面从高到低(32000->8000)方向还有请求4000，则先处理4000的请求。即在第11.3ms后，磁头由柱面8000向柱面4000移动，此段寻道时间为1+(8000-4000)/4000=2ms，则4000访问完成时间为11.3+2+4.3=16.8ms。当访问4000柱面完成时，仅有访问48000柱面的请求未完成，因此磁头将沿着从低到高移动，移动到48000需要1+(48000-4000)/4

7、000=12ms，即在12+16.8=28.8ms才可到达48000柱面。在向48000移动过程中，移动到40000柱面的寻道时间为1+(40000-4000)/4000=10ms，即在16.8+10=26.8ms访问到40000，在此之前访问40000的请求已经到达(在第20ms到达的)，故而，在访问48000之前，先处理访问40000的请求，即对40000柱面的请求在16.8+10+4.3=31.3ms处理完成。从柱面40000到48000的寻道时间为1+(48000-40000)/4000=3ms，则48000的请求处理完成时间为31.1+3+4.3=38.4ms。综上所述，对于电梯调度

8、算法而言每个请求的完成时间如下表：请求的柱面到达时间完全得到服务时间8000011.348000138.440001016.8400002031.1对于FCFS算法而言每个请求的完成时间如下表：请求的柱面到达时间完全得到服务时间800000+7+4.3=11.348000111.3+11+4.3=26.640001026.6+12+4.3=42.9400002042.9+10+4.3=57.2（周红磊 2141284）习题 2.3.2 假设我们使用两台Megatron 747 磁盘 互相作为镜像。然而，我们使第一个磁盘的磁头保持在柱面的靠内一半，第二个磁盘的磁头保持在柱面靠外的一半，而不是允许

9、从两个磁盘都能读任何的块。假设读请求是对随机的磁道，我们始终不必去写：a) 系统的能够读块的平均速率是多少？ 读块的平均速率为之前单个磁头的两倍。b) 这个速率与无任何约束的镜像Megatron 747 磁盘的平均速率相比如何？ 平均速率一样。c）你预计该系统的缺点是什么？ 1. 缺点是以空间为代价换取时间。 2. 如果其中的一个磁头坏了，则读取操作就出问题了，每次只能读取一半的数据。2.4.1计算下列位序列的奇偶校验位：a）00111011。b）00000000。c）10101101。解：定义：如果有奇数个数据盘的第j位为1，在冗余盘中，我们选取位j为1,；如果在数据盘中的第j位有偶数个1，

10、我们选取冗余盘的位j为0。即：有奇数个1，为1；有偶数个1，为0。0 0 1 1 1 0 1 10 0 0 0 0 0 0 01 0 1 0 1 1 0 1-10010110（薛鑫）2.4.2如果我们在一个串末附加一个位作为该串奇数位置的奇偶校验位，另一个位作为该串各偶数位置的奇偶位，我们就有了与一个串关联的两个奇偶位。对于习题2.4.1的每一个串，找出按这种方法计算的两个位。a）00111011。b）00000000。c）10101101。解：RAID5级，不必将一个盘作为冗余盘，而把其他盘作为数据盘；相反我们可以把每个磁盘作为某些块的冗余盘来处理。12345678-0 0 1 1 1 0

11、1 1 100 0 0 0 0 0 0 0 001 0 1 0 1 1 0 1 10（韩月 2141276）2.4.7采用如习题2.4.5一样的RAID4级方案，假设数据盘1有故障。在下列情况下恢复该磁盘的块：a） 盘2至盘4的内容为01110110、11000000和00101011，同时冗余盘保存着11110011。b） 盘2至盘4的内容为11110000、11111000、00110011，同时冗余盘保存着10000001。解:a. 1->0 1 1 0 1 1 1 0 2->0 1 1 1 0 1 1 0 3->1 1 0 0 0 0 0 0 4->0 0 1

12、0 1 0 1 1冗->1 1 1 1 0 0 1 1b. 1->1 0 1 1 1 0 1 0 2->1 1 1 1 0 0 0 0 3->1 1 1 1 1 0 0 0 4->0 0 1 1 0 0 1 1冗->1 0 0 0 0 0 0 12.4.8假设习题2.4.5第1个盘得块被改变为01010101。其他盘上相应的块必须做什么样的改变？解：a) 由数据盘各位的模2和可求得冗余盘的各位，即00000110。当盘1由01010110改为01010101时，求盘1旧值与新值的模2和，得到00000011。将冗余块自身和00000011求模2和，得到新的冗

13、余块，即00000101。所以盘1变为01010101，冗余盘变为00000101，盘2、3、4没变化。b) 由数据盘各位的模2和可求得冗余盘的各位，即01110101。当盘1由11110000改为01010101时，求盘1旧值与新值的模2和，得到10100101。将冗余块自身和10100101求模2和，得到新的冗余块，即11010000。所以盘1变为01010101，冗余盘变为11010000，盘2、3、4没变化。（张柳影 2141286）习题2.4.9如果我们有例2.13的RAID6级方案，4个数据盘的块分别为00110100、11100111、01010101和10000100。a） 冗

14、余盘的相应块是什么？b） 如果第3个盘的块被重写成01111111，必须采取哪些步骤以改变其他盘？注例2.13内容：假设块只有8位长，并且关注在我们的RAID6级示例中用到的7个磁盘的第一块。首先，假设数据盘和冗余盘的第一块的内容如图2-11所示。请注意，盘5的块是前3个盘的块模2和，第6行是行1、2、4的模2和，而最后一行是行1、3、4的模2和。磁盘内容数据块 1)111100002)101010103)010101014)10000100冗余块 5)011000106)000110117)10001001图2-11 所有磁盘的第一块答案：a)前4个盘是数据盘,盘57是冗余盘.盘5的块是前3

15、个盘的块的模2和, 盘5块是10000110；盘6是盘1,2和4的模2和, 盘6块是01010111；盘7是盘1,3,4的模2和, 盘7块是11100101。磁盘内容数据块 1)001101002)111001113)010101014)10000100冗余块 5)100001106)010101117)11100101b)如果第3个盘的块被重写成01111111，求这个序列和序列01010101(该块的旧值)的模2和，则得到00101010；其中为1的位为3、5、7，所以只要对冗余块5和7的3、5、7位取反，故盘5和盘7的重写值分别为10101100、11001111。磁盘内容数据块 1)0

16、01101002)111001113)011111114)10000100冗余块 5)101011006)010101117)11001111（樊星宇 2141312）2.4.10RAID 6 方案 从磁盘崩溃中恢复使用足够多的冗余盘处理多个磁盘的崩溃，例如，基于海明码的纠错技术7个盘，其中14为数据盘，57为冗余盘。数据盘与冗余盘之间的关系由一个3´7矩阵描述如下：1. 盘5的位是盘1,2,3相应位的模2和。 2. 盘6的位是盘1,2,4相应位的模2和。 3. 盘7的位是盘1,3,4相应位的模2和。 习题2.4.10 假设块只有8位长，采用带有7个磁盘的RAID 6级方案，描述从下

17、列故障中恢复所要采取的步骤： a)盘1和盘4； b)盘1和盘7； c)盘2和盘5。 （蒋娜 2141288）习题3.1.1假定一个存储块可存放5个记录，或20个键-指针对。已知有n个记录，如果表示成n的函数，创建以下两种数据文件各需要多少个数据块：a）稠密索引；b）稀疏索引答案：解:a.稠密索引因为一个存储块存储5个记录，n个存储记录需要n/5个数据块，稠密索引需要为每个记录建立键-指针对，所以键-指针需要n/20个数据库，所以表示成n的函数是n/5+n/20=n/4b.稀疏索引因为一个存储块存储5个记录，n个存储记录需要n/5个数据块，但是稀疏索引需要为每个数据块建立键-指针对，所以键-指针

18、对需要(n/5)/20个数据块，所以表示成n的函数是n/5+(n/5)/20=21n/100习题3.1.2如果数据块中可以存放50个记录，或500个键-指针对，但是存放数据和索引的数据块都要求最多只能填满80%，重做习题3.1.1.答案:答：我们知道一个记录在存放时有数据文件和索引文件，它们分别占用存储块，由题中所述可知在索引块中我们采用了稠密索引和稀疏索引，这样两种形式。只要分别计算出这两个部分的存储块的大小，再求和就能求出需要的存储块。下面分别来求： a)一个数据文件和一个稠密索引数据文件的大小容易知道，由已知给定的记录数为n，且每个存储块可存放50个记录, 数据块充满度不许超过80%。我

19、们得到数据文件所占用的存储块大小为：n/(50*0.8); 稠密索引是指块中只存放记录的键以及指向记录本身的指针，数据文件中每个键在索引中都被表示出来，且稠密索引文件中的索引块保持键的顺序和文件中的排序顺序一致，又由已知每个存储块可存放500个键-指针对，索引块充满度不许超过80%。这样我们就能得到索引文件所占用的存储块大小为：n/(500*0.8)。 所以总的结果=数据文件所占用的存储块+索引文件所占用的存储块= n/(50*0.8)+ n/(500*0.8)=（11/400）*n b)一个数据文件和一个稀疏索引同上，数据文件的大小容易知道，由已知给定的记录数为n，且每个存储块可存放50个记

20、录, 数据块充满度不许超过80%。我们得到数据文件所占用的存储块大小为：n/(50*0.8); 稀疏索引与稠密索引不同点在于，稀疏索引在索引中只为每个数据块存放一个键。但要注意如果本题按照书中所给出的稀疏索引的比例存放记录的话，参见P92.则又由已知每个存储块可存放500个键-指针对，索引块充满度不许超过80%。这样我们就能得到索引文件所占用的存储块大小为：n/(50*500*0.8)。这样才能保证结果的正确性。 所以总的结果=数据文件所占用的存储块+索引文件所占用的存储块= n/(50*0.8)+ (n/50*0.8)/500*0.8=401n/16000（万康 2141289）习题3.1.

21、5 假定一个存储块可以存放5个记录，或20个键-指针对，或100个指针。如果我们使用图3-7的间接桶模式： a)如果平均每个查找键值出现在10个记录中，存放在5000个记录和它的辅助索引共需要多少块？如果不使用桶又需要多少块？ b)如果给定键值的记录数没有限制，所需的最大和最小存储块数各为多少？ 图3-7 通过在辅助索引中使用间接层以节省空间解:a)使用桶时 每个数据存储块可以存储5个记录，所以5000个记录需要的数据存储块个数为5000/5=1000 每个桶存储块可以存放100个指针，所以存放这5000个记录辅助索引需要的桶 存储块个数为5000/100=50 每个索引块设有20个键-指针对

22、，平均每个键值出现在10个记录中，所以存放这5000个记录的辅助索引需要的索引块数为 5000/(20*10)=25 总块数=5000/5+5000/100+5000/(20*10) =1000+50+25=1075不使用桶时 索引指针直接对应到相应的数据存储块的记录上块总数为5000/5+5000/20=1250图3-5 辅助索引b)给定键值的记录数没有限制 假设给定键值的记录数为1，就可以得到最多的存储块数为 5000/5+5000/100+5000/(20*1)=1000+50+250=1300 假设给定键值的记录数为5000，就可以得到最少的存储块数为 5000/5+5000/100+

23、1=1051（张恩斌 2141287）习题3.2.1假定存储块能放10个记录或者99个键和100个指针，再假定B树结点的平均充满程度为70%；即有69个键和70个指针。我们可以用B树作为几种不同结构的一部分。对下面描述的每种结构，确定：（1）1000000个记录的文件所需的总块数；（2）检索一个给定键值的记录所需的平均磁盘I/O数。可以假定最初在主存中不存在任何东西，并且查找键是记录的主键。a） 数据文件是按查找键排序的顺序文件，每块存放20个记录。B-树为稠密索引a(1)1000000/10=100000块。B树为稠密索引，叶结点中为数据文件的每一个记录设有一个键指针对。首先有100000数

24、据块，如果在B树底层结点平均每块有70个指针，然后有1000000/70=14286个B树块在最底层，下一层的B树需要14286/70=205个B树块，第三层需要205/70=3块，第四层需要1个根块，所以需要100000+14286+205+3+1=114495块。 (2)匹配记录有1000个，首先1000/10=100数据块，1000/70=15块，15/70=1块，第三层需要1块，第四层需要1块。所以需要100+15+1+1+1=118块。b）同a）一样，但组成数据文件的记录没有特定顺序；每块存放20个记录。b(1) 1000000/10=100000块。首先有100000数据块，如果在

25、B树底层结点平均每块有70个指针，然后有1000000/70=14286个B树块在最底层，下一层的B树需要14286/70=205个B树块，第三层需要205/70=3块，第四层需要1个根块，所以需要100000+14286+205+3+1=114495块。 (2) 匹配记录有1000个，首先1000/10=100数据块，1000/70=15块，15/70=1块，第三层需要1块，第四层需要1块。1000个记录可能分布在1000个块中，所以需要1000+15+1+1+1=1018块。c）同a）一样，但B树为稀疏索引。c(1) 1000000/10=100000块。若B树为稀疏索引，在叶结点中为数据

26、文件的每个块设有一个键指针对。首先有100000数据块，如果在B树底层结点平均每块有70个指针，然后有100000/70=1429个B树块在最底层，下一层的B树需要1429/70=21个B树块，第三层需要21/70=1块，第四层需要1个根块。所以需要100000+1429+21+1+1=101452 (2)匹配记录有1000个，1000/10=100，首先100/70=2块，2/70=1块，第三层需要1块，第四层需要1块。所以需要100+2+1+1+1=105块。d）数据文件是顺序文件，且B-树是稀疏索引，但数据文件的每个基本块有一个溢出块。平均来讲，基本块是满的，而溢出块只半满。不过，记录在

27、基本块和溢出块中没有特定的顺序。d(1) 但数据文件的每个基本块有一个溢出块。平均来讲基本块是满的，而溢出块只是半满。所以基本快的记录为10个，溢出块记录为5个。所以有1000000/15=66667个数据块。然后有66667/70=953个B树块在最低层，下一层的B树需要953/70=14个B树块，第三层需要14/70=1。因此有66667的数据块和953+14+1=968块个索引块。一共67635块。 (2)1000/15=67块，67/70=1块，第二层需要1块，第三层需要1块。因此有67个数据块和3个索引块。总共70块磁盘I/O。e）B树的叶结点中不放指向数据记录的指针，而是保存记录本

28、身。每块可存放10个记录，但平均每个叶结点的充满度为70%，即每个叶结点存放7个记录。e(1) 1000000/7=142858块如果在B树底层结点平均每块有70个指针，然后有142858/70=2041个B树块在最底层，下一层的B树需要2041/70=30个B树块，第三层需要30/70=1块，所以需要142858+2041+30+1=144930块。 (2)查询匹配的记录有1000个，就需要1000/7=143块，143/70=3块，3/70=1块，第三层需要1块。所以总共需要143+3+1+1=148块。（谢胜男 2141283）习题3.2.2假设查询是范围查询且匹配的记录有200个，在这

29、种情况下，重做习题3.2.1。假定存储块能放10个记录或者99个键和100个指针，再假定B树结点的平均充满程度为70%；即有69个键和70个指针。我们可以用B树作为几种不同结构的一部分。对下面描述的每种结构，确定：（1）1000000个记录的文件所需的总块数；（2）假设查询是范围查询且匹配的记录有200个，检索一个给定键值的记录所需的平均磁盘I/O数。可以假定最初在主存中不存在任何东西，并且查找键是记录的主键。a）数据文件是按查找键排序的顺序文件，每块存放20个记录。B-树为稠密索引。b）同a）一样，但组成数据文件的记录没有特定顺序；每块存放20个记录。c）同a）一样，但B树为稀疏索引。d）数

30、据文件是顺序文件，且B-树是稀疏索引，但数据文件的每个基本块有一个溢出块。平均来讲，基本块是满的，而溢出块只半满。不过，记录在基本块和溢出块中没有特定的顺序。!e）B树的叶结点中不放指向数据记录的指针，而是保存记录本身。每块可存放10个记录，但平均每个叶结点的充满度为70%，即每个叶结点存放7个记录。解：a)（1）1000000/20=50000块B树为稠密索引，叶结点中为数据文件的每一个记录设有一个键指针对。首先有50000数据块，如果在B树底层结点平均每块有70个指针，然后有1000000/70=14286个B树块在最底层，下一层的B树需要14286/70=205个B树块，第三层需要205

31、/70=3块，第四层需要1个根块，所以需要50000+14286+205+3+1=64495块。（2）匹配记录有200个，首先200/20=10数据块，200/70=3块，3/70=1块，第三层需要1块，第四层需要1块。所以需要10+3+1+1+1=16块。b)(1)1000000/20=50000块B树为稠密索引，叶结点中为数据文件的每一个记录设有一个键指针对。首先有50000数据块，如果在B树底层结点平均每块有70个指针，然后有1000000/70=14286个B树块在最底层，下一层的B树需要14286/70=205个B树块，第三层需要205/70=3块，第四层需要1个根块，所以需要500

32、00+14286+205+3+1=64495块。(2)匹配记录有200个， 200/70=3块，3/70=1块，第三层需要1块，第四层需要1块。200个记录可能分布在200个块中，所以需要200+3+1+1+1=206块。c)(1) 1000000/20=50000块若B树为稀疏索引，在叶结点中为数据文件的每个块设有一个键指针对。首先有50000数据块，如果在B树底层结点平均每块有70个指针，然后有50000/70=715个B树块在最底层，下一层的B树需要715/70=11个B树块，第三层需要11/70=1块。所以需要50000+715+11+1=50727。(2)匹配记录有200个，200/

33、20=10，首先10/70=1块，第二层1块，第三层需要1块。所以需要10+1+1+1=13块d)（1）但数据文件的每个基本块有一个溢出块。平均来讲基本块是满的，而溢出块只是半满。所以基本块的记录为20个，溢出块记录为10个。所以有1000000/30=33334个数据块。然后有33334/70=477个B树块在最低层，下一层的B树需要477/70=7个B树块，第三层需要7/70=1。因此有33334的数据块和477+7+1=485块个索引块。一共33819块。（2）200/30=7块，7/70=1块，第二层需要1块，第三层需要1块。因此有7个数据块和3个索引块。总共10块磁盘I/O。e)(1

34、) 1000000/7=142858块如果在B树底层结点平均每块有70个指针，然后有142858/70=2041个B树块在最底层，下一层的B树需要2041/70=30个B树块，第三层需要30/70=1块，所以需要142858+2041+30+1=144930块。(2)查询匹配的记录有200个，就需要200/7=15块，15/70=1块，第二层需要1块，第三层需要1块。所以总共需要15+1+1+1=18块。（岳鑫 2151382）习题3.7.3考虑一个有1 00 000个记录的文件，且字段F有m个不同值：a)作为m的一个函数，F的位图索引有多少个字节？b)假定编号从1到1 00 000的记录的字

35、段F的值按循环方式给出。因此 ，每个值每隔m个记录出现一次。使用压缩索引需要多少个字节？答：a）100 000*m/81 00 000 * m是总共位图索引的位数，用总共的位数除以8得到所需的字节数。 b)j=log2m 共需要100 000/ m*2j）* m/8.解释：对于每个未压缩的位图向量来说，共有1 00 000位二进制来表示，且其中每m个0后有一个1，因为对于m个0后有一个1进行压缩索引需要2j（其中j=log2m）位二进制，而对于1 00 000位二进制可以出现1 00 000/ m个1，所以，对于一个压缩的位图向量需要1 00 000/ m*2j位二进制位来表示，而总共有m个位

36、图向量，所以一个需要（1 00 000/ m*2j）* m个二进制位来表示，转换成字节为（1 00 000/ m*2j）* m/8.习题3.7.4 利用3.7.2节的方法，编码下列位图a) 01100000010000000100b) 100000001000001001010001c) 0001000000000001000010000答案：a) 位向量有4个段(1,0,6,7)，1的编码是01；0的编码是00；6的编码110110；7的编码110111。它的编码是0100110110110111b) 位向量有6个段(0,7,5,2,1,3)，0的编码是00； 7的编码110111；5的编码

37、110101；2的编码是1010；1的编码是01；3的编码是1011。它的编码是001101111101011010011011c) 位向量有3个段(3,11,4)，3的编码是1011；11的编码是11101011；4的编码是110100。它的编码是101111101011110100（李翰博 2151388）题4.3.1假设B(R)=B(S)=10000,并且M=1000.计算嵌套连接的磁盘I/O代价。因为M=1000，我们将用999个内存块来按照大小为999块的chunk对S进行缓冲，我们需要10000/999=10.01次迭代。每一次迭代中，我们用999个磁盘I/O读取S的chunk，并

38、且在外层循环中我们必须用10000个磁盘I/O来完整地读取R，总共需要用10.01*10000=100100个，加上S的10000个，总共需要磁盘I/O代价为10000+100100=110100.题4.3.2 对于习题4.3.1中的关系，使用嵌套循环连接算法计算RS时我们需要什么样的M值，磁盘I/O才不超过：a）200000；！b）25000；！c）15000.a)B(S)+(B(S)*B(R)/(M-1)<=200000得M>=528b) B(S)+(B(S)*B(R)/(M-1)<=25000得M>=6668c）B(S)+(B(S)*B(R)/(M-1)<=

39、15000得M>=20001.代价代价是aaaaassasdhh（陈思思 2151387）解：a) 消除重复需要内存大小为，所以所需的内存大小为20000=1002个块大小b) 分组需要内存大小为，所以所需的内存大小为20000=1002个块大小c) 并需要内存大小为，所以所需的内存大小为20000+20000=200个块大小连接需要内存大小为，因为每个关系都是20000个块，所以所需内存大小为20000=1002个块大小解：a) 简单的排序-连接需要内存大小为，因为B(R)=B(S)=10000,M=500,满足这一条件磁盘I/O的需求为：5(B(R)+B(S)=5*(10000+10

40、000)=50000b)4.4.8节更有效排序-连接，磁盘I/O的需求为：3(B(R)+B(S)=3*(10000+10000)=30000c)集合并,磁盘I/O的需求为：3(B(R)+B(S)=3*(10000+10000)=30000（郭晓丹 2151384）习题4.5.1 如果B(S)=B(R)=10000，M=500，对于一个混合散列连接需要多少磁盘I/O？答：若选择桶数k=B(S)/M=20,那么平均每个桶将有S的元组的500个块，我们在内存中容纳这些桶中的一个以及其它19个桶中的19个块，那么就需要519个块，大于内存块数，我们选择k=21.当在第一趟中散列S时，我们有对应20个桶

41、的20个缓冲区，桶大小的预期是B(S)/k=476,对于S，在第一趟中我们用来读取S的所有内容所使用的磁盘I/O的数目是B(S)=10000，并且B(S)-B(S)/k=10000-476=9524个I/O用来将20个桶写到磁盘。当我们在第一趟中处理R时，需要读取R的所有内容(1000次磁盘I/O)，并将它的21个桶中的20个写到磁盘上（B(R)(k+1)/k=9523.8个磁盘I/O）。在第二趟中，我们读取写到磁盘上的所有桶9524+9523.8=19047.8个磁盘I/O。总的磁盘I/O的数量就是20000个用于读取R和S，19047.8个用于将这些关系中的20/21写出，再有19047.

42、8个用于再次读取那些元组，总数就是58095个磁盘I/O。习题4.6.1 假设B(R)=10000，T(R)=500000。R.a上有一个索引，令V(R.a)=k，k是某个常数，在下面情况下给出a=0(R)的代价作为k的一个函数。你可以忽略访问索引自身所需的磁盘I/O。a) 索引是非聚簇的b) 索引是聚簇的c) R是聚簇的，并且不使用索引答：a) T(R)/V(R,a) = 500 000/kb) B(R)/V(R,a) = 10 000/kc) B(R) = 10 000（秦琦冰 2141290）习题5.2.1给出例子证明：a 重复消除()不能下推到投影之下b重复消除不能下推到包并或包差之下

43、。c投影不能下推到集合并之下。d投影不能下推到集合差或包差之下。例子证明如下：(a) 重复消除不能下推到投影之下:R(a,b) = (1,2),(1,3)R = R, a(R) = (1),(1)a R = (1),(1),(aR) = (1),not equal;(b) 重复消除不能下推到包差之下：R(a,b) = (1,2),(1,2), S(a,b) = (1,2)R BS = (1,2), (R BS) = (1,2)(R ) B(S) = (1,2) B(1,2) = , not equal;重复消除不能下推到包并之下：R(a,b) = (1,2),(1,2), S(a,b) = (

44、1,2)RBS = (1,2),(1,2),(1,2),(RBS) = (1,2)(R)B(S) = (1,2)B(1,2) = (1,2),(1,2),not equal;(c) 投影不能下推到集合并之下：R(a,b) = (1,2) , S(a,b) = (1,3)a(RS) =a(1,2),(1,3) = (1,1)(a R)(aS) = (1)(1) = (1)，not equal；(d) 投影不能下推到集合差之下：R(a,b) = (1,2) , S(a,b) = (1,3)a(R-S) = (1)(a R)-(aS) = (1)-(1) = ， not equal；投影不能下推到包

45、差之下：R(a,b) = (1,2),(1,2), S(a,b) = (1,3)R BS = (1,2)，（1,2）, a(R BS) = (1)，（1）(a R ) B(aS) = (1)，（1) B(1) = （1） , not equal;（尹旭明 2151381）习题5.2.3 某些集合的定律也适用于包；某些则不然。下面每一条定律对于集合都是成立的。判定对包是否也正。对包不正确的给出反例，对包正确的加以证明。a)R-R= b)RR=Rc)RR=Rd)R(ST)=(RS) (RT)解答：a):对于任何包与自身做差运算都为空集。故此定律对包正确。b):包与其本身做交运算其结果仍是该包本身。

46、故此定律对包正确。c):不正确：反例：假设R=1,1,2,2 RR=1,1,1,1,2,2,2,2Rd):左边R(ST) 假设元组m在R(ST)的结果当中，对于R的元组r，S的元组s，T的元组t对于ST有必存在一个相同的s和t。对于R(ST)则m包含了每一个r和s（或者t）那么对于右边(RS) (RT)必然存在一个元组包含了每一个r和s，以及另一个元组包含了每一个r和t。则最终的右边的结果元组m包含了这两个元组的至少一个相同元组。即m包含了每一个r和s(或者t).（庞国彬 2151378）习题5.4.1下面是4个关系 W、X、Y和Z的关键统计值：W(a,b)X(b,c)Y(c,d)Z(d,e)

47、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)=50估计下列表达式结果关系的大小： a) W X Y Zb) 𝛔a=10(W)c) 𝛔c=20(Y)d) 𝛔c=20(Y) Ze) W × Yf) 𝛔d>10(Z)g) 𝛔a=1 AND b=2(W)h) 𝛔a=1 AND b>2(W)i)答：(a) 各关系做连接操作结果为：

48、100*200*300*400 = 2,400,000,000. 由于属性 b 在两个关系里面出现，由其中较大的决定，即V(W,b) 和 V(X,b), 取60. 类似地，对于 c 取 100,对于d 取20. 结果2,400,000,000/60/100/20=20000 (b) T(W)/V(W,a) = 400/50 = 8. (c) T(Y)/V(Y,c)= 200/50 = 4.(d) ( T(Y)/V(Y,c) )*Z(d,e)/Max(V(Y,d), V(Z,d)=(200/50)*100 / 20=20.(e) W × Y=400*200=80000(f) T(Z)/

49、3 = 100/3 = 33(g) T(W) / (V(W,a)*V(W,b) =400 / 40*50 = 1/5(h) T(W) / V(W,a) * 3 = 400/50*3 =2.67(i) T(X X.c < Y.c Y) = T(X)T(Y)/3*V(X,c) = 200（王亚珂 2151383）5.4.2下面是4个关系E,F,G,H的统计值：E(a ,b ,c)F(a ,b ,d)G(a ,c ,d)H(b ,c ,d)T(E)=1000T(F)=2000T(G)=3000T(H)=4000V(E ,a)=500V(F ,a)=50V(G ,a)=500V(H ,b)=40

50、0V(E ,b)=100V(F ,b)=200V(G ,c)=300V(H ,c)=200V(E ,c)=20V(F ,d)=100V(G ,d)=100V(H ,d)=800利用这一节中的估计技术，估计这些元组的连接会产生多少结果元组？答案：1000*2000*3000*4000/(500*500*200*400*300*200*100*800)=1/4000000（随云仙 2151380）习题5.6.1 对习题5.4.1中的关系，给定评价以下所有可能的链接顺序的动态规划表项 a)只有左深树。 b)所有树。在每一种情况下什么是最佳选择？表5-1 单集合的表WXYZ大小400300200100

51、代价0000最优计划WXYZ表5-2关系对的表W，XW，YW，ZX，YX，ZY，Z大小20008000040000600300001000代价000000最优计划WXWYWZXYXZYZTW，X=TW*TX/maxV W,b ,VX,b =400*300/60=2000依次类推可以计算出剩下的关系对的大小表5-3 三个关系为一组表W，X，YW，X，ZX，Y，ZW，Y，Z大小40002000003000400000代价60020006001000最优计划(XY)W(WX)Z(XY)Z(YZ)W三个关系为一组，这里我们以计算W，X，Y为例子，依次考虑三对中的每一个。如果我们以WX开始，则代价就是这

52、个关系的大小为2000（参见关系对的表格）。以WY开始的中间关系的代价为80000，以XY开始的中间关系的代价为600，由于后者是三个选择中最小的，我们选择了这个计划（XY）W，该选择不仅反映在W，X，Y的代价表项中，而且也反映在最优计划行。依次类推可以确定三个关系为一组表中剩下的项。只有左深树时以可能的最佳方法选择三个进行连接，然后与第四个连接，如下：表5-4 左深树关系表分组代价(XY)W)Z4600(WX)Z) Y202000(XY)Z) W3600(YZ)W) X401000连接代价等于关系的大小加上代价。有两种通用的方法可以计算全部四个关系的连接： 1.以可能的最佳方法选择三个进行连

53、接，然后与第四个连接。 2.将四个关系划分为两对，将每一对进行连接，再将两个结果进行连接。表5-5 所有树分组连接及代价分组代价(XY)W)Z4600(WX)Z) Y202000(XY)Z) W3600(YZ)W) X401000(WX)(YZ)3000(WY)(X Z)110000(WZ)(XY)40600（王亚杰 2151386）习题5.6.2下面是4个关系W、X、Y和Z的关键统计值：W(a,b)X(b,c)Y(c,d)Z(d,a)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

54、,c)=100V(Y,d)=20V(Z,a)=50给定评价以下所有可能的链接顺序的动态规划表项 a)只有左深树。 b)所有树。在每一种情况下什么是最佳选择？解：由题意得对于单个的集合，它们的大小、代价以及最佳计划如下图所示，即对每一个单独的关系给定他们每一个的大小分别是400、300、200、100，代价为0，这是因为他们不需要中间关系，并且最佳的表达式就是关系本身对于关系对，由于两个关系的链接中仍然没有中间关系，所以每对关系的代价为0.两个关系中任意一个可以作为左参数，因此有两种可能的计划。因此，对于每一个关系对，我们都按照字母的顺序选择在前面的作为左参数，结果由TW，X=TW*TX/max

55、V W,b ,VX,b算出，于是关系对的结果如下图所示三个关系为一组，这里我们以计算W，X，Y为例子，依次考虑三对中的每一个。如果我们以WX开始，则代价就是这个关系的大小为2000（参见关系对的表格）。以WY开始的中间关系的代价为80000，以XY开始的中间关系的代价为600，由于后者是三个选择中最小的，我们选择了这个计划（XY）W，该选择不仅反映在W，X，Y的代价表项中，而且也反映在最优计划行。依次类推可以确定三个关系为一组表中剩下的项。只有左深树时以可能的最佳方法选择三个进行连接，然后与第四个连接，如下有两种通用的方法可以计算全部四个关系的连接： 1.以可能的最佳方法选择三个进行连接，然后与第四个连接。 2.将四个关系划分为两对，将每一对进行连接，再将两个结果进行连接。（林杨 2151377）5.7.1考虑一个关系R(a,