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

1、.wd.wd.wd.习题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平均寻道时间是多少g平均旋转等待时间是多少参考答案：磁盘容

2、量=盘面数*磁道数*扇区数*扇区容量=10*100000*1000*1024字节=210*109字节注释：1有10个盘面，每个盘面有100000个磁道。2磁道平均有1000个扇区，每个扇区为1024字节.一个磁道存放存放1000*1024*8=8192000bits.直径为3.5英尺那么中间磁道直径为3.5/2英寸中间扇区所占的周长是80*3.5/2英寸所以，每个磁道的扇区中的平均密度是 注释： 2磁道平均有1000个扇区，每个扇区为1024字节. 3每个磁道的20%被用于间隙. 最大寻道时间是磁头跨越全部柱面所花费的时间。即1+0.0002*99999=20.9998ms： 1有10个盘面，

3、每个盘面有100000个磁道。 5磁头移动n个磁道所需要的时间是1+0.0002n ms。最大旋转等待时间是磁头旋转一圈的时间。即1/(10000/60)= 6ms： 4磁盘旋转为10000转/min。该块占用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。磁头行进的

4、平均距离是跨越柱面的1/3，那么平均寻道时间是：1+0.001*100000/3=34.33ms平均旋转等待时间为磁盘旋转半周所需时间: (1/2)*6ms=3msExercise 2.2.1(a)The disk has 10 * 10,000 = 100,000 tracks. The average track has 1000 * 512 = 512,000 bytes. Thus,the capacity is 51.2 gigabytes.Exercise 2.2.1(c)The maximum seek time occurs when the heads have to mov

5、e across all the tracks. Thus, substitute10,000 (really 9999) for n in the formula 1+.001n to get 11 milliseconds.Exercise 2.2.1(d)The maximum rotational latency is one full revolution. Since the disk rotates at 10,000 rpm, it takes1/10000 of a minute, or 1/167 of a second to rotate, or about 6 mill

6、iseconds.2.4.1计算以下位序列的奇偶校验位：a00111011。b00000000。c10101101。解：定义：如果有奇数个数据盘的第j位为1，在冗余盘中，我们选取位j为1,；如果在数据盘中的第j位有偶数个1，我们选取冗余盘的位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.9如果我们有例2.13的RAID6级方案，4个数据盘的块分别为00110100、11100111、01010101和10000100。冗余盘的相应块是什么如果第3个盘的块被重写成011111

7、11，必须采取哪些步骤以改变其他盘注例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个盘的块的模2和, 盘5块是10000110；盘6是盘1,2和4

8、的模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)10

9、000100冗余块 5)101011006)010101117)110011112.4.10RAID 6 方案 从磁盘崩溃中恢复使用足够多的冗余盘处理多个磁盘的崩溃，例如，基于海明码的纠错技术7个盘，其中14为数据盘，57为冗余盘。数据盘与冗余盘之间的关系由一个37矩阵描述如下：盘5的位是盘1,2,3相应位的模2和。盘6的位是盘1,2,4相应位的模2和。盘7的位是盘1,3,4相应位的模2和。习题2.4.10 假设块只有8位长，采用带有7个磁盘的RAID 6级方案，描述从以下故障中恢复所要采取的步骤： a)盘1和盘4； b)盘1和盘7； c)盘2和盘5。2.5.1假设一条记录有如下所示顺序的字段

10、:一个长度为15的字符串，一个2字节整数，一个SQL2日期，一个SQL2时间无小数点。如果a)字段可在任何字节处开场；b)字段必须在4的倍数的字节处开场；c)字段必须在8的倍数的字节处开场；这条记录占用多少个字节First, note that SQL2 dates require 10 bytes, and SQL2 times require 8 bytes if there is no decimal point; this material is in Section 3.1.3.a) The bytes requirsed by each of the fields is 15 +

11、2 + 10 + 8 = 35.b) Round each of the four field lengths up to a multiple of 4, to get 16 + 4 + 12 + 8 = 40.c) Round up again, to a multiple of 8, to get 16 + 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

12、再次循环，到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的内容：0 1 0 1 0 1 1 0b、磁盘1的内容：0 0 1 1 0 1 1 02.6.7如果我们有例2.22的RAID6级方案，4个数据盘的块分别为00111100、110001

13、11、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，1010101

14、0习题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如果数据

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

16、文件中每个键在索引中都被表示出来，且稠密索引文件中的索引块保持键的顺序和文件中的排序顺序一致，又由每个存储块可存放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); 稀疏索引与稠密索引不同点在于，稀疏

17、索引在索引中只为每个数据块存放一个键。但要注意如果此题按照书中所给出的稀疏索引的比例存放记录的话，参见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树作为几种不同构造的一局部。

18、对下面描述的每种构造，确定：11000000个记录的文件所需的总块数；2检索一个给定键值的记录所需的平均磁盘I/O数。可以假定最初在主存中不存在任何东西，并且查找键是记录的主键。*a)数据文件是按查找键排序的顺序文件，每块存放10个记录。B树为稠密索引。b)同a一样，但组成数据文件的记录没有特定顺序；每块存放10个记录。c)同a一样，但B树为稀疏索引。!d)B树的叶结点中不放指向数据记录的指针，而是保存记录本身。每块可存放10个记录，但平均每个叶结点的充满度为70%，即每个叶结点存入7个记录。*e)数据文件是顺序文件，且B树是稀疏索引，但数据文件的每个 基本块有一个溢出块。平均来讲， 基本块是

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

20、设有一个键指针对。首先有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一样，但组成数据文件的记录没有特定顺序；每块存放20个记录。b(1) 1000000/10=100000块

21、。首先有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块。1000个记录可能分布在1000个块中，所以需要1000+15+1+1+1=1018块。c同a一样，但B树为稀疏索引。c(1) 1000000/10=100000块。假设

22、B树为稀疏索引，在叶结点中为数据文件的每个块设有一个键指针对。首先有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-树是稀疏索引，但数据文件的每个 基本块有一个溢出块。平均来讲， 基本块是

23、满的，而溢出块只半满。不过，记录在 基本块和溢出块中没有特定的顺序。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。eB树的叶结点

24、中不放指向数据记录的指针，而是保存记录本身。每块可存放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块。3.2.5假设字段如3.2.1，记录有个首部，

25、它由两个四字节的指针和一个字符组成，且我们希望在一个4096个字节的块中装入尽可能多的记录，使用的块首部由10个4字节的整数组成，对习题3.2.1中的三个情况，我们各能将多少记录装入块中参考3.2.1题答案( 4096 40 ) / 35( 4096 40 ) / 40( 4096 80 ) / 483.3.3 假假设在图散列表中发生以下插入和删除，请说明将产生什么情况：1)记录g到记录j分别插入桶0到桶3。2)记录a和b记录被删除。3)记录k到n分别插入桶0到桶3。4)记录c和d被删除。答案：(题目没给出是否顺序产生这4种情况还是各自独立发生)设4种情况独立发生g直接插入到桶0中的第二个存储

26、块；增加一个新存储块在该存储块的第一块上存储h，并链接到桶1的第一块上；i直接插入到桶2中的第二个存储块；增加一个新存储块在该存储块的第一块上存储j，并链接到桶1的第一块上；2、在桶3上删除该a记录并将剩下的记录移动到块前部以使其紧凑；在桶2上直接删除该b记录习题3.7.4利用3.7.2节的方法，编码以下位图011000000100000001001000000010000010010100010001000000000001000010000答案：位向量有4个段(1,0,6,7)，1的编码是01；0的编码是00；6的编码110110；7的编码110111。它的编码是0100110110110

27、111位向量有6个段(0,7,5,2,1,3)，0的编码是00； 7的编码110111；5的编码110101；2的编码是1010；1的编码是01；3的编码是1011。它的编码是001101111101011010011011位向量有3个段(3,11,4)，3的编码是1011；11的编码是11101011；4的编码是110100。它的编码是101111101011110100Exercise 4.2.1(a)The iterator for pi_L(R) can be described informally as follows:Open():R.Open()GetNext():Let t

28、= R.GetNext(). If Found = False, return. Else, construct and return the tuple consistingof the elements of list L evaluated for tuple t.Close():R.Close()Exercise 4.2.1 (b)Here is the iterator for delta(R):Open():First perform R.Open(). Then, initialize a main-memory structure S that will represent a

29、 set oftuples of R seen so far. For example, a hash table could be used. Initially, set S is empty.GetNext():Repeat R.GetNext() until either Found = False or a tuple t that is not in set S is returned. Inthe later case, insert t into S and return that tuple.Close():R.Close()Exercise 4.2.1 (d)For the

30、 set union R1 union R2 we need both a set S that will store the tuples of R1 and a flag CurRelas in Example 6.13. Here is a summary of the iterator:Open()Perform R1.Open() and initialize to empty the set S.GetNext()If CurRel = R1 then perform t = R1.GetNext(). If Found = True, then insert t into S a

31、ndreturn t. If Found = False, then R1 is exhausted. Perform R1.Close(), R2.Open(), setCurRel = R2, and repeatedly perform t = R2.GetNext() until either Found = False (inwhich case, just return), or t is not in S. In the latter case, return t.Close():Perform R2.Close()题4.3.1假设B(R)=B(S)=10000,并且M=1000

32、.计算嵌套连接的磁盘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+100100=110100.假设B(R)= B(S)=10000 ,并且M=1000,计算嵌套循环连接的磁盘I/O代价The formula in Section 6.4.4 gives 10000 + 1

33、0000*10000/999 or 110,101.这个公式在6.4.4 章节所给的结果是10000+10000*10000/999或者110,101编者注: 6.4.4章节公式:B(S)+Exercise 4.3.1The formula in Section 6.4.4 gives 10000 + 10000*10000/999 or 110,101.题4.3.2 对于习题4.3.1中的关系，使用嵌套循环连接算法计算RS时我们需要什么样的M值，磁盘I/O才不超过：a200000；！b25000；！c15000.a)B(S)+(B(S)*B(R)/(M-1)=528b) B(S)+(B(S)

34、*B(R)/(M-1)=6668cB(S)+(B(S)*B(R)/(M-1)=20001.Exercise 4.4.1 (a)An iterator for delta(R) must do the first sorting pass in its Open() function. Here is a sketch:Open():Perform R.Open() and repeatedly use R.GetNext() to read memory-sized chunks of R. Sorteach into a sorted sublist and write out the li

35、st. Each of these lists may be thought of as havingits own iterator. Open each list and initialize a data structure into which the current elementof each list may be read into main memory. Use GetNext() for each list to initialize the mainmemory structure with the first element of each list. Finally

36、, execute R.Close().GetNext():Find the least tuple t in the main-memory structure, and output one copy of it. Delete all copiesof t in main memory, using GetNext() for the appropriate sublist, until all copies of t havedisappeared, then return. If there was no such tuple t, because all the sublists

37、were exhausted,set Found = False and return.Close():Close all the sorted sublists.Exercise 4.4.2 (c)For R1 intersect R2 do the following:Open():Open R1 and R2, use their GetNext() functions to read all their tuples in main-memory-sizedchunks, and create sorted sublists, which are stored on disk. Ini

38、tialize a main-memory datastructure that will hold the current tuple of each sorted sublist, and use the Open() andGetNext() functions of an iterator from each sublist to initialize the structure to have the firsttuple from each sublist. Finally, close R1 and R2.GetNext():Find the least tuple t amon

39、g all the first elements of the sorted sublists. If t occurs on a list fromR1 and a list from R2, then output t, remove the copies of t, use GetNext from the two sublistsinvolved to replentish the main-memory structure, and return. If t appears on only one of thesublists, do not output t. Ratherm re

40、move it from its list, replentish that list, and repeat thesesteps with the new least t. If no t exists, because all the lists are exhausted, set Found = Falseand return.Close():Close all the sorted sublists.Exercise 6.5.3(b)The formula of Fig. 6.16 gives 5*(10000+10000) = 100,000. Note that the mem

41、ory available, whichis 1000 blocks, is larger than the minimum required, which is sqrt(10000), or 100 blocks. Thus, themethod is feasible代价代价是aaaaassasdhh解：消除重复需要内存大小为，所以所需的内存大小为20000=1002个块大小分组需要内存大小为，所以所需的内存大小为20000=1002个块大小并需要内存大小为，所以所需的内存大小为20000+20000=200个块大小连接需要内存大小为，因为每个关系都是20000个块，所以所需内存大小为2

42、0000=1002个块大小5.2.5针对表达式L(R(a,b,c) S(b,c,d,e) ,尽可能下推投影，其中L是: a)b+cx c+dy 。b)a,b,a+dz。We cannot push down b+c -& x, because both b and c are used in the join. Notice that if wereplaced b+c by their sum before joining, we would join tuples whose sum b+c agreed, but that had different values of b and c.

43、 What we can push down is:1. The elimination of a from R.2. The elimination of e from S.3. The replacement of c+d by y in S. Thus, the answer is:pi_b+c-x, y(pi_b,c(R) JOIN pi_b, c, c+d-y(S)因为在联接中b和c都被用到，所以我们不能推出b+c-x。注意：如果我们在连接之前用b+c的和来替换b+c，我们可以连接b和c相加所允许的元祖，但是b和c的值是不同的。我们可以推出的是：从R中消去a从S中消去e在S中y替换c

44、+d因此，答案是：a)b+c-x,y(b,c(R) JOIN b,c,c+d-y(S)b)a,b,a+d-z(a,b,c(R) JOIN b,c,d(S)林杨 21513775.7.1考虑一个关系R(a,b,c,d),该关系有一个a上的剧簇索引以及每一个其他属性上的非聚簇索引。相关参数为：B(R)=500,T(R)=5000,V(R,a)=50,V(R,b)=1000,V(R,c)=5000,V(R,d)=500。给出最正确查询方案索引扫描或者表扫描然后进展一个过滤器操作步骤以及以下选择运算的每一个的磁盘I/O开销：(A)a=1ANDb=2ANDc=3(R)(B)a=1ANDb=3(R)(C)

45、a=1ANDb=2ANDd=3(R)以第一道题为例,有以下几种方式：1表扫描后进展过滤，其代价是B(R)，即500次的磁盘I/O，因为R是聚集的。2使用a的索引以及索引扫描来找出a=1的元组，然后利用过滤操作来检测b=2以及c=3，由于有B(R)/V(R,a)=10个元组的a=1，并且索引是聚集的，我们大约需要10次I/O。3使用b的索引以及索引扫描来找出b=2的元组，然后利用过滤操作来检测a=1以及c=3，由于有T(R)/V(R,b)=5个元组的b=2，并且索引是非聚集的，我们大约需要5次I/O。4使用c的索引以及索引扫描来找出c=3的元组，然后利用过滤操作来检测a=1以及b=2，由于有T(

46、R)/3=167个元组的c=3，并且索引是非聚集的，我们大约需要167次I/O。我们可以看到代价最小的方案是第三种，估计代价为5次磁盘I/O。因此，这个选择的最正确物理方案搜索b=2的元组，然后为另外两个条件进展过滤。5.7.1考虑一个关系R(a,b,c,d),该关系有一个a的聚簇索引以及对每一个其他属性的非聚簇索引。相关变元为:B(R)=1000,T(R)=5000,V(R,a)=20,V(R,b)=1000,V(R,c)=5000,V(R,d)=500.对于以下各项选择，给出最正确查询方案(索引扫描或者表扫描，然后进展一个过滤步骤)以及磁盘I/O开销a)a=1 and b=2 and d=

47、3(R) b)a=1 and b=2 and c=3(R) c)a=1 and b=3(R)Use an index-scan using the nonclustering index on c. Since V(R,c) = 5000, only one block should be retrieved. Filter the retrieved tuples for a=1 and d=3. The expected disk I/O cost is 1.使用索引扫描，使用非聚簇索引扫描c，当V(R,c)=5000，只有一块被检索到。用a=1 and b=2 and d=3过滤检索元组

48、。预期的磁盘I/O的成本是1。编者注： R被聚簇那么为B(R) ,R没有被聚簇那么为B(R)，以a=常数来扫描的算法代价是：如果索引是聚簇索引那么为B(R)/V(R,a)；如果索引是非聚簇索引那么为T(R)/V(R,a)以不等项，形如a常数来扫描的算法代价是：如果索引是聚簇索引那么为B(R)/3；如果索引是非聚簇索引那么为T(R)/3编者注：1) 表-扫描后进展过滤。因为R为聚簇，其代价为B(R)=1000,即1000次磁盘I/O2) 使用a的索引以及索引扫描找出a=1的元祖，然后利用过滤操作符来检查b=2 and d=3,因为a聚簇索引，为会有B(R)/V(R,a)=50个元祖，需要50次I

49、/O3) 使用b的索引以及索引扫描找出b=2的元祖，然后利用过滤操作符来检查a=1 and d=3,因为b非聚簇索引，为会有T(R)/V(R,b)=5个元祖，需要5次I/O4) 使用d的索引以及索引扫描找出d=3的元祖，然后利用过滤操作符来检查b=2 and a=1,因为d非聚簇索引，为会有T(R)/V(R,d)=10个元祖，需要10次I/O5) 使用c的索引以及索引扫描找出所有元祖，然后利用过滤操作符来检查a=1 and b=2 and d=3,因为c非聚簇索引，为会有T(R)/V(R,c)=1个元祖，需要1次I/O6.1.2对习题6.1.1中的每个事务，在计算中参加读写动作，并给出各步骤对

50、主存和磁盘产生的影响。假设最初A=50且B=25.此外，请说明当OUTPUT动作顺序恰当时，是否可能即使在事务的执行过程中发生了故障，一致性仍能得到保持。6.1.1事务：a) B:=A+B;A:=A+B;b)A:=B+1;B:=A+1;c)A:=A+B;B:=A+B; a)动作t内存中的A内存中的B磁盘中的A磁盘中的BREAD(B,t1)25255025READ(A,t2)5050255025t1:=t2+RITE(B,t1)7550755025t2:=t2+t112550755025WRITE(A,t2)125125755025OutputB,t1)75125755

51、075Output(A,t2)1251257512575b)动作t内存中的A内存中的B磁盘中的A磁盘中的BREAD(A,t1)50505025READ(B,t2)2550255025t1:=t2+12650255025WRITE(A,t1)2626255025t2:=t1+12726255025WRITE(B,t2)2726275025OutputA,t1)2626272625Output(B,t2)2726272627c)动作t内存中的A内存中的B磁盘中的A磁盘中的BREAD(A,t1)50505025READ(B,t2)2550255025t1:=t1+t27550255025WRITE(

52、A,t1)7575255025t2:=t1+t210075255025WRITE(B,t2)100751005025OutputA,t1)75751007525Output(B,t2)1007510075100如果OUTPUT动作顺序恰当，即使在事务执行过程中发生故障，一致性仍能得到保持。6.2.3下面是两个事务T和U的一系列日志记录：; ; ; ; ; ; ; ; ; 。请描述恢复管理器的行为，包括对磁盘和日志所做的改变，假设故障发生且出现在磁盘上的最后一条日志记录为：a) b) c) d)a事务T、U未提交，要被撤销。向后扫描日志，遇到记录，于是将A在磁盘上的值存为10。最后，记录和被写到

53、日志中且日志被刷新。b事务T已提交，U未提交，要被撤销。向后扫描日志，遇到记录，于是将C在磁盘上的值存为30。最后，记录被写到日志中且日志被刷新。c事务T已提交，U未提交，要被撤销。向后扫描日志，首先遇到记录，将E在磁盘上的值存为50。接着遇到记录，于是将C在磁盘上的值存为30。最后，记录被写到日志中且日志被刷新。d) 事务T、U均被提交。什么都不做。6.2.3 下面是两个事务T和U的一系列日志记录：;.描述恢复管理器的行为，包括对磁盘盒日志所做的改变，假设发生故障且出现在磁盘上的最后一条日志记录为(编者注：故障发生在以下语句的后一句，试描述如何恢复)：a) b) c) d)U is iden

54、tified as committed, while T is not. Thus, T must be undone. Scanning the log backwards,we set C to 30 and A to 10. Then, we write an T record on the log.a.不需要undob.C=30,A=10 事务U状态是提交，而T不是。因此，T必须undone。扫描日志，我们设置C=30和A=10。然后，我们在日志写一个记录。c.E=50,C=30,A=10编者注：undo还没有提交的数据要恢复,数据时老数据使用redo日志重做上题Since T is

55、not complete, we can be sure that none of its changes reached disk, and we can ignore log records about T. On the other hand, U was committed, and its log record reached disk, so some of its changes may have reached disk. To be sure, we must redo all of the actions of U. Thus, we first set B to 20 a

56、nd then set D to 40.因为T没有完成，我们可以肯定他的任何变化都没有到达磁盘，我们可以忽略关于T的日志记录，另一方面，U提交了，他的日志写道了磁盘上。它的一些变化也到达磁盘的。可以肯定的是，我们必须重做U的所有行动，因此，我们首先B=20，然后到D=40编者注：redo已经提交的数据要重新做，数据时新数据6.2.3下面是两个事务T和U的一系列日志记录：;。请描述恢复管理器的行为，包括对磁盘和日志所作的改变，假设故障发生且出现在磁盘上的最后一条日志记录为：a) b) c) d)答案1假设题目是:; ; .那么答案是首先扫描日志,发现事务T和U都未commit,将其连接到未完成事

57、务列.按照未完成事务列,从后往前逐步扫描日志并执行undo操作，按照将磁盘中A值写为10,将和写入日志中并刷新日志。首先扫描日志,发现事务T已经commit，将其连接到已完成事务列,事务U未完成，将其连接到未完成事务列。按照未完成事务列，从后往前扫描日志执行undo操作，按照将磁盘中C值写为30，将磁盘A值写为10。将写入日志中并刷新日志。首先扫描日志,发现事务T已经commit，将其连接到已完成事务列,事务U未完成，将其连接到未完成事务列。按照未完成事务列从后往前扫描日志执行undo操作，按照将磁盘中E值写为50，将磁盘中C值写为30，将磁盘A值写为10。将写入日志中并刷新日志。d)首先扫描

58、日志,发现事务T、U已经commit，将其连接到已完成列，未完成列为空，不做任何操作。6.2.4对于习题6.2.3描述的每种情况，T和U所写的哪些值必然出现在磁盘上哪些值可能出现在磁盘上6.3.2使用习题6.2.7的数据，对该习题中a到e的各个位置答复：I：何时能写入记录Ii：对每一个可能发生的故障的时刻，为了找到所有可能未完成的事务，我们需要在日志中向后看多远。请考虑记录在崩溃发生以前写入和未写入的两种情况。习题6.2.7数据：日志记录序列：;假设在如下日志中的某一条写入后立即开场一个非静止检查点：A)B)C)D)E)第一问1在a后写入START CKPT时，此时，只有s是活泼的，在后写入记

59、录；2.在b后写入START CKPT时，此时，只有T是活泼的，在后写入记录；3.在C后写入START CKPT时，此时，只有U、T都是活泼的，在后写入录；4.在d后写入START CKPT时，此时，只有U、T、V都是活泼的，在后写入记录；5.在e后写入START CKPT时，此时，只有T、V都是活泼的，在后写入录；第二问在a处，如果记录在崩溃前写入的话，此时需要在日志中向后看到记录；如果记录在崩溃后写入的话，此时需要在日志中向后看到记录;2. 在b处，如果记录在崩溃前写入的话，此时需要在日志中向后看到记录；如果记录在崩溃后写入的话，此时需要在日志中向后看到记录;3. 在C处，如果记录在崩溃前

60、写入的话，此时需要在日志中向后看到记录；如果记录在崩溃后写入的话，此时需要在日志中向后看到记录;4、在d处，如果记录在崩溃前写入的话，此时需要在日志中向后看到记录；如果记录在崩溃后写入的话，此时需要在日志中向后看到记录;5、在e处，如果记录在崩溃前写入的话，此时需要在日志中向后看到记录；如果记录在崩溃后写入的话，此时需要在日志中向后看到记录;6.4.2下面是两个事务T和U的一系列日志记录：;。描述恢复管理器的行为，包括对磁盘和日志所作的改变，假设故障发生且出现在磁盘上的最后一条日志记录如下：a b) c d答案1：a首先扫描日志，发现事务U、T均未commit，将其连接到未完成列。按照未完成列