数据库系统实现习题-全.pdf

《数据库系统实现习题-全.pdf》由会员分享，可在线阅读，更多相关《数据库系统实现习题-全.pdf（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、word 文档 可自由复制编辑（达建松 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）如果一个块是

2、65536 字节（即 64 扇区），一个块得传输时间是多少？f）平均寻道时间是多少？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）磁道平均有

3、1000 个扇区，每个扇区为 1024 字节.3）每个磁道的 20%被用于间隙.c)最大寻道时间是磁头跨越全部柱面所花费的时间。即 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 度圆弧，则被它们覆

4、盖的圆弧的总度数word 文档 可自由复制编辑 为：72*(63/1000)+288*(64/1000)=22.968则 传 输 时 间 是（22.968/360）*0.6ms=0.03828ms 已知：3）每个磁道的 20%被用于间隙。2）磁道平均有 1000 个扇区 。d）中最大旋转等待时间为 6ms。f)磁头行进的平均距离是跨越柱面的 1/3，则平均寻道时间是：1+0.001*（100000/3）=34.33ms g)平均旋转等待时间为磁盘旋转半周所需时间:(1/2)*6ms=3ms （潘达）习题 2.3.1 假设我们正在为 Megatron747 磁盘调度 I/O 请求，磁头的初始位置

5、在磁道 32000，图 2-9 的请求已经产生。在下列两种情况下，每一种请求在何时可以完全得到服务？a)我们采用电梯调度算法（起初朝任何一个方向开始移动都是允许的）。b)我们采用先到达先服务调度。请求的柱面 到达时间 8000 0 48000 1 4000 10 40000 20 图 2-9 4 个块访问请求的到达时间 Megatron747 磁盘的平均寻道时间、旋转等待时间和传输时间分别为 6.46、4.17 和 0.13（所有时间均以 ms 计算）。因为每个块访问导致 0.13ms 传输时间和 4.17ms 平均旋转等待时间，即无论寻道时间是多少，都需为每一次块访问加上 4.3ms。寻道时

6、间可通过 Megatron747的规则计算：1+磁道数/4000（1+磁道数/500）。对于电梯调度算法，计算方式及结果如下。对柱面 8000 的第一个请求需要进行寻道，因为磁头初始位置不是 8000。这样访问 8000 完成的寻道时间为 1+(32000-8000)/4000ms，即在时间 1+(32000-8000)/4000+4.3=11.3ms 处第一次访问将完成。在此之前，对柱面 48000 和4000 访问的请求分别于第 1 和第 10 时间到达，由于沿着柱面从高到低(32000-8000)方向还有请求 4000，则先处理 4000 的请求。即在第 11.3ms 后，磁头由柱面 8

7、000 向柱面 4000 移动，此段寻道时间为 1+(8000-4000)/4000=2ms，则 4000 访问完成时间为 11.3+2+4.3=16.8ms。当访问 4000 柱面完成时，仅有访问 48000 柱面的请求未完成，因此磁头将沿着从低到高移动，移动到 48000 需要 1+(48000-4000)/4000=12ms，即在 12+16.8=28.8ms 才可到达 48000柱面。在向48000移动过程中，移动到40000柱面的寻道时间为1+(40000-4000)/4000=10ms，即在16.8+10=26.8ms访问到40000，在此之前访问40000的请求已经到达(在第20

8、ms到达的)，故而，在访问 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。综上所述，对于电梯调度算法而言每个请求的完成时间如下表：请求的柱面 到达时间 完全得到服务时间 8000 0 11.3 48000 1 38.4 4000 10 16.8 word 文档 可自由复制编辑 40000 20 31.1 对于 FCFS 算法而言每个请

9、求的完成时间如下表：请求的柱面 到达时间 完全得到服务时间 8000 0 0+7+4.3=11.3 48000 1 11.3+11+4.3=26.6 4000 10 26.6+12+4.3=42.9 40000 20 42.9+10+4.3=57.2 （周红磊 2141284）习题 2.3.2 假设我们使用两台 Megatron 747 磁盘 互相作为镜像。然而，我们使第一个磁盘的磁头保持在柱面的靠内一半，第二个磁盘的磁头保持在柱面靠外的一半，而不是允许从两个磁盘都能读任何的块。假设读请求是对随机的磁道，我们始终不必去写：a)系统的能够读块的平均速率是多少？读块的平均速率为之前单个磁头的两倍。

10、b)这个速率与无任何约束的镜像 Megatron 747 磁盘的平均速率相比如何？平均速率一样。c）你预计该系统的缺点是什么？1.缺点是以空间为代价换取时间。2.如果其中的一个磁头坏了，则读取操作就出问题了，每次只能读取一半的数据。2.4.1 计算下列位序列的奇偶校验位：a）00111011。b）00000000。c）10101101。解：定义：如果有奇数个数据盘的第 j 位为 1，在冗余盘中，我们选取位 j 为 1,；如果在数据盘中的第 j 位有偶数个 1，我们选取冗余盘的位 j 为 0。即：有奇数个 1，为 1；有偶数个 1，为 0。0 0 1 1 1 0 1 1 0 0 0 0 0 0

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

12、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 0 1 0 1 1 冗-1 1 1 1 0 0 1 1 b.1-1

13、 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 1 2.4.8 假设习题 2.4.5 第 1 个盘得块被改变为 01010101。其他盘上相应的块必须做什么样的改变？解：a)由数据盘各位的模 2 和可求得冗余盘的各位，即 00000110。当盘 1 由 01010110 改为 01010101 时，求盘 1 旧值与新值的模 2 和，得到 00000011。将冗余块自身和 00000011求模 2 和，得到新的冗余块，即 00000101。所以盘 1 变为 01010101，

14、冗余盘变为 00000101，盘 2、3、4 没变化。word 文档 可自由复制编辑 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、

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

16、011 7)10001001 图 2-11 所有磁盘的第一块 答案：a)前 4 个盘是数据盘,盘 57 是冗余盘.盘 5 的块是前 3 个盘的块的模 2 和,盘 5 块是 10000110；盘 6 是盘 1,2 和 4 的模 2 和,盘 6 块是 01010111；盘 7 是盘 1,3,4 的模 2 和,盘 7 块是 11100101。磁盘 内容 数据块 1)00110100 2)11100111 3)01010101 4)10000100 冗余块 5)10000110 6)01010111 7)11100101 b)如果第3个盘的块被重写成01111111，求这个序列和序列01010101(

17、该块的旧值)的模2和，则得到 00101010；其中为 1 的位为 3、5、7，所以只要对冗余块 5 和 7 的 3、5、7 位取反，故盘 5 和盘 7 的重写值分别为 10101100、11001111。磁盘 内容 数据块 1)00110100 2)11100111 word 文档 可自由复制编辑 3)01111111 4)10000100 冗余块 5)10101100 6)01010111 7)11001111 （樊星宇 2141312）2.4.10 RAID 6 方案 从磁盘崩溃中恢复 使用足够多的冗余盘处理多个磁盘的崩溃，例如，基于海明码的纠错技术 7 个盘，其中 14 为数据盘，57

18、 为冗余盘。数据盘与冗余盘之间的关系由一个 37 矩阵描述如下：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 级方案，描述从下列故障中恢复所要采取的步骤：a)盘 1 和盘 4；b)盘 1 和盘 7；c)盘 2 和盘 5。word 文档 可自由复制编辑 （蒋娜 2141288）习题 3.1.1 假定一个存储块可存放 5 个记录，或 20 个键-指针对。已知有 n 个记录，如果表示成 n 的函数，创建以下

19、两种数据文件各需要多少个数据块：a）稠密索引；b）稀疏索引 答案：解:a.稠密索引 因为一个存储块存储 5 个记录，n 个存储记录需要 n/5 个数据块，稠密索引需要为每个记录建立键-指针对，所以键-指针需要 n/20 个数据库，所以表示成 n 的函数是 n/5+n/20=n/4 b.稀疏索引 因为一个存储块存储 5 个记录，n 个存储记录需要 n/5 个数据块，但是稀疏索引需要为每个数据块建立键-指针对，所以键-指针对需要(n/5)/20 个数据块，所以表示成 n 的函数是n/5+(n/5)/20=21n/100 习题 3.1.2 如果数据块中可以存放 50 个记录，或 500 个键-指针对

20、，但是存放数据和索引的数据块都要word 文档 可自由复制编辑 求最多只能填满 80%，重做习题 3.1.1.答案:答：我们知道一个记录在存放时有数据文件和索引文件，它们分别占用存储块，由题中所述可知在索引块中我们采用了稠密索引和稀疏索引，这样两种形式。只要分别计算出这两个部分的存储块的大小，再求和就能求出需要的存储块。下面分别来求：a)一个数据文件和一个稠密索引 数据文件的大小容易知道，由已知给定的记录数为 n，且每个存储块可存放 50 个记录,数据块充满度不许超过 80%。我们得到数据文件所占用的存储块大小为：n/(50*0.8);稠密索引是指块中只存放记录的键以及指向记录本身的指针，数据

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

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

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

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

25、/5+5000/100+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 树为稠密索

26、引，叶结点中为数据文件的每一个记录设有一个键指针对。首先有100000数据块，如果在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）一样，但组成数据

27、文件的记录没有特定顺序；每块存放 20 个记录。b(1)1000000/10=100000 块。首先有 100000 数据块，如果在 B 树底层结点平均每块有 70word 文档 可自由复制编辑 个指针，然后有 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 块，第

28、三层需要 1 块，第四层需要 1 块。1000 个记录可能分布在 1000 个块中，所以需要1000+15+1+1+1=1018 块。c）同 a）一样，但 B 树为稀疏索引。c(1)1000000/10=100000 块。若 B 树为稀疏索引，在叶结点中为数据文件的每个块设有一个键指针对。首先有 100000 数据块，如果在 B 树底层结点平均每块有 70 个指针，然后有100000/70=1429 个 B 树块在最底层，下一层的 B 树需要 1429/70=21 个 B 树块，第三层需要21/70=1 块，第四层需要 1 个根块。所以需要 100000+1429+21+1+1=101452

29、(2)匹配记录有 1000 个，1000/10=100，首先 100/70=2 块，2/70=1 块，第三层需要 1 块，第四层需要 1 块。所以需要 100+2+1+1+1=105 块。d）数据文件是顺序文件，且 B-树是稀疏索引，但数据文件的每个基本块有一个溢出块。平均来讲，基本块是满的，而溢出块只半满。不过，记录在基本块和溢出块中没有特定的顺序。d(1)但数据文件的每个基本块有一个溢出块。平均来讲基本块是满的，而溢出块只是半满。所以基本快的记录为 10 个，溢出块记录为 5 个。所以有 1000000/15=66667 个数据块。然后有 66667/70=953 个 B 树块在最低层，下

30、一层的 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 树的叶结点中不放指向数据记录的指针，而是保存记录本身。每块可存放 10 个记录，但平均每个叶结点的充满度为 70%，即每个叶结点存放 7 个记录。e(1)1000000/7=142858 块 如果在 B 树底层结点平均每块有 70 个指针，然后有 142858

31、/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 个，在这种情况下，重做习题 3.2.1。假定存储块能放 10 个记录或者 99 个键和 100 个指针，再假定 B 树结点的平均充满程度为70%；

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

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

34、5/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 树

35、块，第三层需要 205/70=3 块，第四层需要 1 个根块，所以需要 50000+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/

36、70=11 个 B 树块，第三层需要 11/70=1 块。所以需要50000+715+11+1=50727。(2)匹配记录有 200 个，200/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。因此有 333

37、34 的数据块和 477+7+1=485 块个索引块。一共 33819 块。（2）200/30=7 块，7/70=1 块，第二层需要 1 块，第三层需要 1 块。因此有 7 个数据块和 3 个索引块。总共 10 块磁盘 I/O。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)查询匹配的记录有 200 个，就需要 200/7=15 块，

38、15/70=1 块，第二层需要 1 块，第三层需要 1 块。所以总共需要 15+1+1+1=18 块。（岳鑫 2151382）习题3.7.3 word 文档 可自由复制编辑 考虑一个有1 00 000个记录的文件，且字段F有m个不同值：a)作为m的一个函数，F的位图索引有多少个字节？b)假定编号从1到1 00 000的记录的字段F的值按循环方式给出。因此，每个值每隔m个记录出现一次。使用压缩索引需要多少个字节？答：a）100 000*m/8 1 00 000*m是总共位图索引的位数，用总共的位数除以8得到所需的字节数。b)j=log2m 共需要100 000/m*2j）*m/8.解释：对于每个

39、未压缩的位图向量来说，共有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个位图向量，所以一个需要（1 00 000/m*2j）*m个二进制位来表示，转换成字节为（1 00 000/m*2j）*m/8.习题 3.7.4 利用 3.7.2 节的方法，编码下列位图 a)01100000010000000100 b)100000001000001001010001 c

40、)0001000000000001000010000 答案：a)位向量有 4 个段(1,0,6,7)，1 的编码是 01；0 的编码是 00；6 的编码 110110；7 的编码110111。它的编码是 0100110110110111 b)位向量有 6 个段(0,7,5,2,1,3)，0 的编码是 00；7 的编码 110111；5 的编码 110101；2的编码是1010；1的编码是01；3的编码是1011。它的编码是001101111101011010011011 c)位向量有 3 个段(3,11,4)，3 的编码是 1011；11 的编码是 11101011；4 的编码是 110100

41、。它的编码是 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，并且在外层循环中我们必须用10000个磁盘I/O来完整地读取R，总共需要用10.01*10000=100100个，加上 S 的 10000 个，总共需要磁盘 I/O 代价为 10000+1

42、00100=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)=528 b)B(S)+(B(S)*B(R)/(M-1)=6668 c）B(S)+(B(S)*B(R)/(M-1)=20001.word 文档 可自由复制编辑（陈思思 2151387）解：a)消除重复需要内存大小为，所以所需的内存大小为20000=1002个块大小 b)分组需要内存大小为，所以所需的内存大小为20000=1002个块大小 c)

43、并需要内存大小为，所以所需的内存大小为(20000+20000)=200 个块大小 连接需要内存大小为，因为每个关系都是 20000 个块，所以所需内存大小为20000=1002个块大小 解：a)简单的排序-连接需要内存大小为，因为 B(R)=B(S)=10000,M=500,满足这一条件 磁盘 I/O 的需求为：5(B(R)+B(S)=5*(10000+10000)=50000 b)4.4.8 节更有效排序-连接，磁盘 I/O 的需求为：3(B(R)+B(S)=3*(10000+10000)=30000 c)集合并,磁盘 I/O 的需求为：3(B(R)+B(S)=3*(10000+10000

44、)=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 个桶的 20 个缓冲区，桶大小的预期是 B(S)/k=476,对于 S，在第一趟中我们用来读取 S 的所有内容所使用的磁盘 I/O 的数目是 B(S)=10000，并word 文档 可自由

45、复制编辑 且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.8 个用于再次读取那些元组，总数就是 58095 个磁盘 I/O。习题 4.6.1 假设

46、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/k b)B(R)/V(R,a)=10 000/k c)B(R)=10 000 （秦琦冰 2141290）习题 5.2.1 给出例子证明：a 重复消除()不能下推到投影之下 b 重复消除不能下推到包并或包差之下。c 投影不能下推到集合并之下。d 投影不能下推到集合差或包差之下

47、。例子证明如下：(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)=(1,2)word 文档 可自由复制编辑 RBS=(1,2),(1,2),(1,2),(RBS)=(1,2)(R)B(S)=(1,2)B

48、(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(RS)=(1)(a R)(aS)=(1)(1)=，not equal；投影不能下推到包差之下：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)=

49、（1）,not equal;（尹旭明 2151381）习题 5.2.3 某些集合的定律也适用于包；某些则不然。下面每一条定律对于集合都是成立的。判定对包是否也正。对包不正确的给出反例，对包正确的加以证明。a)R-R=b)RR=R c)RR=R d)R(ST)=(RS)(RT)解答：a):对于任何包与自身做差运算都为空集。故此定律对包正确。b):包与其本身做交运算其结果仍是该包本身。故此定律对包正确。c):不正确：反例：假设 R=1,1,2,2 RR=1,1,1,1,2,2,2,2R d):左边 R(ST)假设元组 m 在 R(ST)的结果当中，对于 R 的元组 r，S 的元组 s，T 的元组

50、t 对于 ST 有必存在一个相同的 s 和 t。对于 R(ST)则 m 包含了每一个 r 和 s（或者 t）那么对于右边(RS)(RT)必然存在一个元组包含了每一个 r 和 s，以及另一个元组包含了每一个 r 和 t。则最终的右边的结果元组 m 包含了这两个元组的至少一个相同元组。即 m包含了每一个 r 和 s(或者 t).word 文档 可自由复制编辑（庞国彬 2151378）习题 5.4.1 下面是 4 个关系 W、X、Y 和 Z 的关键统计值：W(a,b)X(b,c)Y(c,d)Z(d,e)T(W)=400 T(X)=300 T(Y)=200 T(Z)=100 V(W,a)=50 V(X