数据库系统实现部分习题参考答案

习题2.2.1Megatron777磁盘具有以下特性：1）有10个盘面，每个盘面有100000个磁道。2）磁道平均有1000个扇区，每个扇区为1024字节3）每个磁道的20%被用于间隙。4）磁盘旋转为10000转/min。5）磁头移动n个磁道所需要的时间是1+0.0002nms。回答下列有关Megatron777的问题。a）磁盘的容量是多少？b）如果磁道是在直径3.5英寸的圆面上，那么一个磁道的扇区中的平均位密度是多少？c）最大寻道时间是多少？d）最大旋转等待时间是多少？e）如果一个块是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）磁道平均有1000个扇区，每个扇区为1024字节.3）每个磁道的20%被用于间隙.c)最大寻道时间是磁头跨越全部柱面所花费的时间。即1+0.0002*99999=20.9998ms已知：1）有10个盘面，每个盘面有100000个磁道。5）磁头移动n个磁道所需要的时间是1+0.0002nms。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.03828ms已知：3）每个磁道的20%被用于间隙。2）磁道平均有1000个扇区。d）中最大旋转等待时间为6ms。f)磁头行进的平均距离是跨越柱面的1/3，则平均寻道时间是：1+0.001*（100000/3）=34.33msg)平均旋转等待时间为磁盘旋转半周所需时间:(1/2)*6ms=3msExercise2.2.1(a)Thediskhas10*10,000=100,000tracks.Theaveragetrackhas1000*512=512,000bytes.Thus,thecapacityis51.2gigabytes.Exercise2.2.1(c)Themaximumseektimeoccurswhentheheadshavetomoveacrossallthetracks.Thus,substitute10,000(really9999)fornintheformula1+.001ntoget11milliseconds.Exercise2.2.1(d)Themaximumrotationallatencyisonefullrevolution.Sincethediskrotatesat10,000rpm,ittakes1/10000ofaminute,or1/167ofasecondtorotate,orabout6milliseconds.2.4.1计算下列位序列的奇偶校验位：a）00111011。b）00000000。c）10101101。解：定义：如果有奇数个数据盘的第j位为1，在冗余盘中，我们选取位j为1,；如果在数据盘中的第j位有偶数个1，我们选取冗余盘的位j为0。即：有奇数个1，为1；有偶数个1，为0。001110110000000010101101-------------------------10010110习题2.4.9如果我们有例2.13的RAID6级方案，4个数据盘的块分别为00110100、11100111、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)111100002)101010103)010101014)10000100冗余块5)011000106)000110117)10001001图2-11所有磁盘的第一块答案：a)前4个盘是数据盘,盘5~7是冗余盘.盘5的块是前3个盘的块的模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)001101002)111001113)011111114)10000100冗余块5)101011006)010101117)110011112.4.10RAID6方案从磁盘崩溃中恢复使用足够多的冗余盘处理多个磁盘的崩溃，例如，基于海明码的纠错技术7个盘，其中1～4为数据盘，5～7为冗余盘。数据盘与冗余盘之间的关系由一个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个磁盘的RAID6级方案，描述从下列故障中恢复所要采取的步骤：a)盘1和盘4；b)盘1和盘7；c)盘2和盘5。2.5.1假设一条记录有如下所示顺序的字段:一个长度为15的字符串，一个2字节整数，一个SQL2日期，一个SQL2时间（无小数点）。如果a)字段可在任何字节处开始；b)字段必须在4的倍数的字节处开始；c)字段必须在8的倍数的字节处开始；这条记录占用多少个字节？First,notethatSQL2datesrequire10bytes,andSQL2timesrequire8bytesifthereisnodecimalpoint;thismaterialisinSection3.1.3.a)Thebytesrequirsedbyeachofthefieldsis15+2+10+8=35.b)Roundeachofthefourfieldlengthsuptoamultipleof4,toget16+4+12+8=40.c)Roundupagain,toamultipleof8,toget16+8+16+8=48.首先，请注意SQL2日期需要10个字节，SQL2次需要8个字节（没有小数点），点，这种材料是在3.1.3节。A）由每个字段需要的字节是15+2+10+8=35。B）每此循环的四个字段长度为4的倍数,即所有字段长度为4的倍数，得到16+4+12+8=40。C）再次循环，到8的倍数,即所有字段长度为8的倍数，得到16+8+16+8=48。2.6.5采用如习题2.6.4一样的RAID4级方案，假设数据盘1有故障。在下列情况下恢复该磁盘的块：a)盘2～盘4的内容为01010110、11000000和00111011，同时冗余盘保存着11111011。b)盘2～盘4的内容为11110000、11111000和00111111，同时冗余盘保存着00000001。答案:a、磁盘1的内容：01010110b、磁盘1的内容：001101102.6.7如果我们有例2.22的RAID6级方案，4个数据盘的块分别为00111100、11000111、01010101和10000100。a)冗余盘的相应块是什么？b)如果第三个盘的块被重写成10000000，必须采取哪些步骤以改变其他盘？答案：RAID6级方案，4个数据块，3个冗余块（第1对应数据块123的模2和，第2对应124的模2和，第3对应134的模2和）a数据块100111100211000111301010101410000100冗余块110101110201111111311101101b原第三块01010101与重写块10000000模2和为11010101，其中为1的位为1、2、4、6、8所以只要对冗余块1、2块的1、2、4、6、8位求反得01111011，10101010习题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个数据块，但是稀疏索引需要为每个数据块建立键-指针对，所以键-指针对需要(n/5)/20个数据块，所以表示成n的函数是n/5+(n/5)/20=21n/100习题3.1.2如果数据块中可以存放50个记录，或500个键-指针对，但是存放数据和索引的数据块都要求最多只能填满80%，重做习题3.1.1.答案:答：我们知道一个记录在存放时有数据文件和索引文件，它们分别占用存储块，由题中所述可知在索引块中我们采用了稠密索引和稀疏索引，这样两种形式。只要分别计算出这两个部分的存储块的大小，再求和就能求出需要的存储块。下面分别来求：a)一个数据文件和一个稠密索引数据文件的大小容易知道，由已知给定的记录数为n，且每个存储块可存放50个记录,数据块充满度不许超过80%。我们得到数据文件所占用的存储块大小为：n/(50*0.8);稠密索引是指块中只存放记录的键以及指向记录本身的指针，数据文件中每个键在索引中都被表示出来，且稠密索引文件中的索引块保持键的顺序和文件中的排序顺序一致，又由已知每个存储块可存放500个键-指针对，索引块充满度不许超过80%。这样我们就能得到索引文件所占用的存储块大小为：n/(500*0.8)。所以总的结果=数据文件所占用的存储块+索引文件所占用的存储块=n/(50*0.8)+n/(500*0.8)=（11/400）*nb)一个数据文件和一个稀疏索引同上，数据文件的大小容易知道，由已知给定的记录数为n，且每个存储块可存放50个记录,数据块充满度不许超过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/160003.2.1假定存储块能放10个记录或者99个键和100个指针，再假定B树结点的平均充满程度为70%；即有69个键和70个指针。我们可以用B树作为几种不同结构的一部分。对下面描述的每种结构，确定：（1）1000000个记录的文件所需的