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

-.z.习题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〕平均旋转等待时间是多少？参考答案：磁盘容量=盘面数*磁道数*扇区数*扇区容量=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个盘面，每个盘面有100000个磁道。5〕磁头移动n个磁道所需要的时间是1+0.0002nms。最大旋转等待时间是磁头旋转一圈的时间。即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。磁头行进的平均距离是跨越柱面的1/3，则平均寻道时间是：1+0.001*〔100000/3〕=34.33ms平均旋转等待时间为磁盘旋转半周所需时间:(1/2)*6ms=3msE*ercise2.2.1(a)Thediskhas10*10,000=100,000tracks.Theaveragetrackhas1000*512=512,000bytes.Thus,thecapacityis51.2gigabytes.E*ercise2.2.1(c)Thema*imumseektimeoccurswhentheheadshavetomoveacrossallthetracks.Thus,substitute10,000(really9999)fornintheformula1+.001ntoget11milliseconds.E*ercise2.2.1(d)Thema*imumrotationallatencyisonefullrevolution.Sincethediskrotatesat10,000rpm,ittakes1/10000ofaminute,or1/167ofasecondtorotate,orabout6milliseconds.计算以下位序列的奇偶校验位：a〕00111011。b〕00000000。c〕10101101。解：定义：如果有奇数个数据盘的第j位为1，在冗余盘中，我们选取位j为1,；如果在数据盘中的第j位有偶数个1，我们选取冗余盘的位j为0。即：有奇数个1，为1；有偶数个1，为0。001110110000000010101101-------------------------10010110习题如果我们有例2.13的RAID6级方案，4个数据盘的块分别为00110100、11100111、01010101和10000100。冗余盘的相应块是什么？如果第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)11001111RAID6方案从磁盘崩溃中恢复使用足够多的冗余盘处理多个磁盘的崩溃，例如，基于海明码的纠错技术7个盘，其中1～4为数据盘，5～7为冗余盘。数据盘与冗余盘之间的关系由一个37矩阵描述如下：盘5的位是盘1,2,3相应位的模2和。盘6的位是盘1,2,4相应位的模2和。盘7的位是盘1,3,4相应位的模2和。习题2.4.10假设块只有8位长，采用带有7个磁盘的RAID6级方案，描述从以下故障中恢复所要采取的步骤：a)盘1和盘4；b)盘1和盘7；c)盘2和盘5。假设一条记录有如下所示顺序的字段:一个长度为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个字节〔没有小数点〕，点，这种材料是在节。A〕由每个字段需要的字节是15+2+10+8=35。B〕每此循环的四个字段长度为4的倍数,即所有字段长度为4的倍数，得到16+4+12+8=40。C〕再次循环，到8的倍数,即所有字段长度为8的倍数，得到16+8+16+8=48。采用如习题一样的RAID4级方案，假设数据盘1有故障。在以下情况下恢复该磁盘的块：a)盘2～盘4的内容为01010110、11000000和00111011，同时冗余盘保存着11111011。b)盘2～盘4的内容为11110000、11111000和00111111，同时冗余盘保存着00000001。答案: a、磁盘1的内容：01010110b、磁盘1的内容：00110110如果我们有例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习题假定一个存储块可存放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习题如果数据块中可以存放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个记录的文件所需的总块数；〔2〕检索一个给定键值的记录所需的平均磁盘I/O数。可以假定最初在主存中不存在任何东西，并且查找键是记录的主键。*a)数据文件是按查找键排序的顺序文件，每块存放10个记录。B树为稠密索引。b)同a〕一样，但组成数据文件的记录没有特定顺序；每块存放10个记录。c)同a〕一样，但B树为稀疏索引。!d)B树的叶结点中不放指向数据记录的指针，而是保存记录本身。每块可存放10个记录，但平均每个叶结点的充满度为70%，即每个叶结点存入7个记录。*e)数据文件是顺序文件，且B树是稀疏索引，但数据文件的每个根本块有一个溢出块。平均来讲，根本块是满的，而溢出块只半满。不过，记录在根本块和溢出块中没有特定的顺序。〔*恩斌2141287〕习题假定存储块能放10个记录或者99个键和100个指针，再假定B树结点的平均充满程度为70%；即有69个键和70个指针。我们可以用B树作为几种不同构造的一局部。对下面描述的每种构造，确定：〔1〕1000000个记录的文件所需的总块数；〔2〕检索一个给定键值的记录所需的平均磁盘I/O数。可以假定最初在主存中不存在任何东西，并且查找键是记录的主键。数据文件是按查找键排序的顺序文件，每块存放20个记录。B-树为稠密索引[a](1)1000000/10=100000块。B树为稠密索引，叶结点中为数据文件的每一个记录设有一个键指针对。首先有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块。首先有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块。假设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-树是稀疏索引，但数据文件的每个根本块有一个溢出块。平均来讲，根本块是满的，而溢出块只半满。不过，记录在根本块和溢出块中没有特定的顺序。[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树的叶结点中不放指向数据记录的指针，而是保存记录本身。每块可存放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块。假设字段如，记录有个首部，它由两个四字节的指针和一个字符组成，且我们希望在一个4096个字节的块中装入尽可能多的记录，使用的块首部由10个4字节的整数组成，对习题中的三个情况，我们各能将多少记录装入块中参考题答案(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中的第二个存储块；增加一个新存储块在该存储块的第一块上存储h，并到桶1的第一块上；i直接插入到桶2中的第二个存储块；增加一个新存储块在该存储块的第一块上存储j，并到桶1的第一块上；2、在桶3上删除该a记录并将剩下的记录移动到块前部以使其紧凑；在桶2上直接删除该b记录习题3.7.4利用节的方法，编码以下位图100101000100010000答案：位向量有4个段(1,0,6,7)，1的编码是01；0的编码是00；6的编码110110；7的编码110111。它的编码是10111位向量有6个段(0,7,5,2,1,3)，0的编码是00；7的编码110111；5的编码110101；2的编码是1010；1的编码是01；3的编码是1011。它的编码是0011011位向量有3个段(3,11,4)，3的编码是1011；11的编码是11101011；4的编码是110100。它的编码是0E*ercise4.2.1(a)Theiteratorforpi_L(R)canbedescribedinformallyasfollows:Open():R.Open()GetNe*t():Lett=R.GetNe*t().IfFound=False,return.Else,constructandreturnthetupleconsistingoftheelementsoflistLevaluatedfortuplet.Close():R.Close()E*ercise4.2.1(b)Hereistheiteratorfordelta(R):Open():FirstperformR.Open().Then,initializeamain-memorystructureSthatwillrepresentasetoftuplesofRseensofar.Fore*ample,ahashtablecouldbeused.Initially,setSisempty.GetNe*t():RepeatR.GetNe*t()untileitherFound=FalseoratupletthatisnotinsetSisreturned.Inthelatercase,inserttintoSandreturnthattuple.Close():R.Close()E*ercise4.2.1(d)ForthesetunionR1unionR2weneedbothasetSthatwillstorethetuplesofR1andaflagCurRelasinE*ample6.13.Hereisasummaryoftheiterator:Open()PerformR1.Open()andinitializetoemptythesetS.GetNe*t()IfCurRel=R1thenperformt=R1.GetNe*t().IfFound=True,theninserttintoSandreturnt.IfFound=False,thenR1ise*hausted.PerformR1.Close(),R2.Open(),setCurRel=R2,andrepeatedlyperformt=R2.GetNe*t()untileitherFound=False(inwhichcase,justreturn),ortisnotinS.Inthelattercase,returnt.Close():PerformR2.Close()题假设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+100100=110100.假设B(R)=B(S)=10000,并且M=1000,计算嵌套循环连接的磁盘I/O代价TheformulainSection6.4.4gives10000+10000*10000/999or110,101.这个公式在6.4.4章节所给的结果是10000+10000*10000/999或者110,101编者注章节公式:B(S)+TheformulainSection6.4.4gives10000+10000*10000/999or110,101.题4.3.2对于习题中的关系，使用嵌套循环连接算法计算R⋈S时我们需要什么样的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))<=15000得M>=20001.E*ercise4.4.1(a)Aniteratorfordelta(R)mustdothefirstsortingpassinitsOpen()function.Hereisasketch:Open():PerformR.Open()andrepeatedlyuseR.GetNe*t()toreadmemory-sizedchunksofR.Sorteachintoasortedsublistandwriteoutthelist.Eachoftheselistsmaybethoughtofashavingitsowniterator.Openeachlistandinitializeadatastructureintowhichthe``current''elementofeachlistmaybereadintomainmemory.UseGetNe*t()foreachlisttoinitializethemainmemorystructurewiththefirstelementofeachlist.Finally,e*ecuteR.Close().GetNe*t():Findtheleasttupletinthemain-memorystructure,andoutputonecopyofit.Deleteallcopiesoftinmainmemory,usingGetNe*t()fortheappropriatesublist,untilallcopiesofthavedisappeared,thenreturn.Iftherewasnosuchtuplet,becauseallthesublistsweree*hausted,setFound=Falseandreturn.Close():Closeallthesortedsublists.E*ercise4.4.2(c)ForR1intersectR2dothefollowing:Open():OpenR1andR2,usetheirGetNe*t()functionstoreadalltheirtuplesinmain-memory-sizedchunks,andcreatesortedsublists,whicharestoredondisk.Initializeamain-memorydatastructurethatwillholdthe``current''tupleofeachsortedsublist,andusetheOpen()andGetNe*t()functionsofaniteratorfromeachsublisttoinitializethestructuretohavethefirsttuplefromeachsublist.Finally,closeR1andR2.GetNe*t():Findtheleasttupletamongallthefirstelementsofthesortedsublists.IftoccursonalistfromR1andalistfromR2,thenoutputt,removethecopiesoft,useGetNe*tfromthetwosublistsinvolvedtoreplentishthemain-memorystructure,andreturn.Iftappearsononlyoneofthesublists,donotoutputt.Rathermremoveitfromitslist,replentishthatlist,andrepeatthesestepswiththenewleastt.Ifnote*ists,becauseallthelistsaree*hausted,setFound=Falseandreturn.Close():Closeallthesortedsublists.E*ercise6.5.3(b)TheformulaofFig.6.16gives5*(10000+10000)=100,000.Notethatthememoryavailable,whichis1000blocks,islargerthantheminimumrequired,whichissqrt(10000),or100blocks.Thus,themethodisfeasible解：消除重复需要内存大小为，所以所需的内存大小为QUOTE=100QUOTE个块大小分组需要内存大小为，所以所需的内存大小为QUOTE=100QUOTE个块大小并需要内存大小为，所以所需的内存大小为QUOTE=200个块大小连接需要内存大小为，因为每个关系都是20000个块，所以所需内存大小为QUOTE=100QUOTE个块大小针对表达式πL(R(a,b,c)⋈S(b,c,d,e)),尽可能下推投影，其中L是:a)b+c→*c+d→y。b)a,b,a+d→z。Wecannotpushdownb+c-&>*,becausebothbandcareusedinthejoin.Noticethatifwereplacedb+cbytheirsumbeforejoining,wewouldjointupleswhosesumb+cagreed,butthathaddifferentvaluesofbandc.Whatwecanpushdownis:1.TheeliminationofafromR.2.TheeliminationofefromS.3.Thereplacementofc+dbyyinS.Thus,theansweris:pi_{b+c->*,y}(pi_{b,c}(R)JOINpi_{b,c,c+d->y}(S))因为在联接中b和c都被用到，所以我们不能推出b+c->*。注意：如果我们在连接之前用b+c的和来替换b+c，我们可以连接b和c相加所允许的元祖，但是b和c的值是不同的。我们可以推出的是：从R中消去a从S中消去e在S中y替换c+d因此，答案是：a)πb+c->*,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))〔林杨2151377〕考虑一个关系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<=2ANDc>=3(R)(C)δ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(R)/3=167个元组的c>=3，并且索引是非聚集的，我们大约需要167次I/O。我们可以看到代价最小的方案是第三种，估计代价为5次磁盘I/O。因此，这个选择的最正确物理方案搜索b=2的元组，然后为另外两个条件进展过滤。考虑一个关系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=1andb=2andd=3(R)b)σa=1andb=2andc>=3(R)c)σa=1andb<=2andc>=3(R)Useaninde*-scanusingthenonclusteringinde*onc.SinceV(R,c)=5000,onlyoneblockshouldberetrieved.Filtertheretrievedtuplesfora=1andd=3.Thee*pecteddiskI/Ocostis1.使用索引扫描，使用非聚簇索引扫描c，当V(R,c)=5000，只有一块被检索到。用a=1andb=2andd=3过滤检索元组。预期的磁盘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=2andd=3,因为a聚簇索引，为会有B(R)/V(R,a)=50个元祖，需要50次I/O3)使用b的索引以及索引扫描找出b=2的元祖，然后利用过滤操作符来检查a=1andd=3,因为b非聚簇索引，为会有T(R)/V(R,b)=5个元祖，需要5次I/O4)使用d的索引以及索引扫描找出d=3的元祖，然后利用过滤操作符来检查b=2anda=1,因为d非聚簇索引，为会有T(R)/V(R,d)=10个元祖，需要10次I/O5)使用c的索引以及索引扫描找出所有元祖，然后利用过滤操作符来检查a=1andb=2andd=3,因为c非聚簇索引，为会有T(R)/V(R,c)=1个元祖，需要1次I/O对习题中的每个事务，在计算中参加读写动作，并给出各步骤对主存和磁盘产生的影响。假设最初A=50且B=25.此外，请说明当OUTPUT动作顺序恰当时，是否可能即使在事务的执行过程中发生了故障，一致性仍能得到保持。事务：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)125125755025Output〔B,t1)75125755075Output(A,t2)1251257512575b)动作t内存中的A内存中的B磁盘中的A磁盘中的BREAD(A,t1)50505025READ(B,t2)2550255025t1:=t2+12650255025WRITE(A,t1)2626255025t2:=t1+12726255025WRITE(B,t2)2726275025Output〔A,t1)2626272625Output(B,t2)2726272627c)动作t内存中的A内存中的B磁盘中的A磁盘中的BREAD(A,t1)50505025READ(B,t2)2550255025t1:=t1+t27550255025WRITE(A,t1)7575255025t2:=t1+t210075255025WRITE(B,t2)100751005025Output〔A,t1)75751007525Output(B,t2)1007510075100如果OUTPUT动作顺序恰当，即使在事务执行过程中发生故障，一致性仍能得到保持。下面是两个事务T和U的一系列日志记录：<STARTU>;<T,A,10>;<STARTT>;<T,B,20>;<U,C,30>;<T,D,40>;<MITT>;<U,E,50>;<MITU>;。请描述恢复管理器的行为，包括对磁盘和日志所做的改变，假设故障发生且出现在磁盘上的最后一条日志记录为：a)<STARTT>b)<MITT>c)<U,E,50>d)<MITU>a〕<STARTT>事务T、U未提交，要被撤销。向后扫描日志，遇到记录<T,A,10>，于是将A在磁盘上的值存为10。最后，记录<ABORTU>和<ABORTT>被写到日志中且日志被刷新。b〕<MITT>事务T已提交，U未提交，要被撤销。向后扫描日志，遇到记录<U,C,30>，于是将C在磁盘上的值存为30。最后，记录<ABORTU>被写到日志中且日志被刷新。c〕<U,E,50>事务T已提交，U未提交，要被撤销。向后扫描日志，首先遇到记录<U,E,50>，将E在磁盘上的值存为50。接着遇到记录<U,C,30>，于是将C在磁盘上的值存为30。最后，记录<ABORTU>被写到日志中且日志被刷新。d)<MITU>事务T、U均被提交。什么都不做。6.2.3下面是两个事务T和U的一系列日志记录：<STARTT>;<T,A,10>;<STARTU>;<U,B,20>;<T,C,30>;<U,D,40>;<MITU>;<T,E,50>;<MITT>.描述恢复管理器的行为，包括对磁盘盒日志所做的改变，假设发生故障且出现在磁盘上的最后一条日志记录为(编者注：故障发生在以下语句的后一句，试描述如何恢复)：a)<STARTU>b)<MITU>c)<T,E,50>d)<MITT>Uisidentifiedasmitted,whileTisnot.Thus,Tmustbeundone.Scanningthelogbackwards,wesetCto30andAto10.Then,wewritean<ABORT>Trecordonthelog.a.不需要undob.C=30,A=10〔事务U状态是提交，而T不是。因此，T必须undone。扫描日志，我们设置C=30和A=10。然后，我们在日志写一个<ABORT>记录。〕c.E=50,C=30,A=10编者注：undo还没有提交的数据要恢复,数据时老数据使用redo日志重做上题SinceTisnotplete,wecanbesurethatnoneofitschangesreacheddisk,andwecanignorelogrecordsaboutT.Ontheotherhand,Uwasmitted,anditslogrecordreacheddisk,sosomeofitschangesmayhavereacheddisk.Tobesure,wemustredoalloftheactionsofU.Thus,wefirstsetBto20andthensetDto40.因为T没有完成，我们可以肯定他的任何变化都没有到达磁盘，我们可以忽略关于T的日志记录，另一方面，U提交了，他的日志写道了磁盘上。它的一些变化也到达磁盘的。可以肯定的是，我们必须重做U的所有行动，因此，我们首先B=20，然后到D=40编者注：redo已经提交的数据要重新做，数据时新数据下面是两个事务T和U的一系列日志记录：<STARTU>;<U,A,10>;<STARTT>;<T,B,20>;<U,C,30>;<T,D,40>;<MITT>;<U,E,50>;<MITU>。请描述恢复管理器的行为，包括对磁盘和日志所作的改变，假设故障发生且出现在磁盘上的最后一条日志记录为：a)<STARTT>b)<MITT>c)<U,E,50>d)<MITU>答案1假设题目是:<STARTU>;<U,A,10>;<STARTT>….则答案是首先扫描日志,发现事务T和U都未mit,将其连接到未完成事务列.按照未完成事务列,从后往前逐步扫描日志并执行undo操作，按照<U,A,10>将磁盘中A值写为10,将<ABORTT>和<ABORTU>写入日志中并刷新日志。首先扫描日志,发现事务T已经mit，将其连接到已完成事务列,事务U未完成，将其连接到未完成事务列。按照未完成事务列，从后往前扫描日志执行undo操作，按照<U,C,30>将磁盘中C值写为30，<U,A,10>将磁盘A值写为10。将<ABORTU>写入日志中并刷新日志。首先扫描日志,发现事务T已经mit，将其连接到已完成事务列,事务U未完成，将其连接到未完成事务列。按照未完成事务列从后往前扫描日志执行undo操作，按照<U,E,50>将磁盘中E值写为50，<U,C,30>将磁盘中C值写为30，<U,A,10>将磁盘A值写为10。将<ABORTU>写入日志中并刷新日志。d)首先扫描日志,发现事务T、U已经mit，将其连接到已完成列，未完成列为空，不做任何操作。对于习题描述的每种情况，T和U所写的哪些值必然出现在磁盘上？哪些值可能出现在磁盘上？使用习题的数据，对该习题中〔a〕到〔e〕的各个位置答复：I：何时能写入<CKPT>记录Ii：对每一个可能发生的故障的时刻，为了找到所有可能未完成的事务，我们需要在日志中向后看多远。请考虑<ENDCKPT>记录在崩溃发生以前写入和未写入的两种情况。习题数据：日志记录序列：<STARTS>;<<S,A,60>;<MITS>;<STARTT>;<T,A,10>;<STARTU>;<U,B,20>;<T,C,30>;<STARTV>;<U,D,40>;<V,F,70>;<MITU>;<T,E,50>;<MITT>;<V,B,80>;<MITV>;假设在如下日志中的*一条写入后立即开场一个非静止检查点：A)<S,A,60>B)<T,A,10>C)<U,B,20>D)<U,D,40>E)<T,E,50>第一问1在a〕<S,A,60>后写入STARTCKPT时，此时，只有s是活泼的，在<MITS>后写入<ENDCKPT>记录；2.在b〕后写入STARTCKPT时，此时，只有T是活泼的，在<MITT>后写入<ENDCKPT>记录；3.在C〕后写入STARTCKPT时，此时，只有U、T都是活泼的，在<MITT>后写入<ENDCKPT>录；4.在d〕后写入STARTCKPT时，此时，只有U、T、V都是活泼的，在<MITV>后写入<ENDCKPT>记录；5.在e〕后写入STARTCKPT时，此时，只有T、V都是活泼的，在<MITV>后写入<ENDCKPT>录；第二问在a〕处，如果<ENDCKPT>记录在崩溃前写入的话，此时需要在日志中向后看到记录<STARTCKPT(S)>；如果<ENDCKPT>记录在崩溃后写入的话，此时需要在日志中向后看到记录<STARTS>;2.在b〕处，如果<ENDCKPT>记录在崩溃前写入的话，此时需要在日志中向后看到记录<STARTCKPT(T)>；如果<ENDCKPT>记录在崩溃后写入的话，此时需要在日志中向后看到记录<STARTT>;3.在C〕处，如果<ENDCKPT>记录在崩溃前写入的话，此时需要在日志中向后看到记录<STARTCKPT(T，U)>；如果<ENDCKPT>记录在崩溃后写入的话，此时需要在日志中向后看到记录<STARTT>;4、在d〕处，如果<ENDCKPT>记录在崩溃前写入的话，此时需要在日志中向后看到记录<STARTCKPT(T,U,V)>；如果<ENDCKPT>记录在崩溃后写入的话，此时需要在日志中向后看到记录<STARTT>;5、在e〕处，如果<ENDCKPT>记录在崩溃前写入的话，此时需要在日志中向后看到记录<STARTCKPT(T，V)>；如果<ENDCKPT>记录在崩溃后写入的话，此时需要在日志中向后看到记录<STARTT>;下面是两个事务T和U的一系列日志记录：<STARTU>;<U,A,10,11>;<STARTT>;<T,B,20,21>;<U,C,30,31>;<T,D,40,41>;<MITT>;<U,E,50,51>;<MITU>。描述恢复管理器的行为，包括对磁盘和日志所作的改变，假设故障发生且出现在磁盘上的最后一条日志记录如下：a〕<STARTT>b)<MITT>c〕<U,E,50,51>d〕<MITU>答案1：a〕首先扫描日志，发现事务U、T均未mit，将其连接到未完成列。按照未完成列，从后往前逐步扫描日志并执行undo操作，按照<U,A,10,11>将磁盘中A值写为10.b〕首先扫描日志，发现事务T已为mit而U未mit，故将T连接到已完成列而U连接到未完成列。按照未完成列，从后往前扫描日志，按照<U,C,30,31>将磁盘中C写为30，<U,A,10,11>将磁盘中A值写为10。按照已完成列，从前往后扫描日志，按照<T,B,20,21>将磁盘中B写为21，<T,D,40,41>将磁盘中D写为41.c)最后一条记录为<U,E,50，51>这时我们为E往磁盘上写入值51，但是崩溃在<MITU>记录到达前发生，则E在磁盘上的值为50。d)最后一条记录为<MITU>，这时U被认为是已提交的事务。我们为E往磁盘上写入值51，E已经具有值51。6.4.2下面是两个事务组T和U的一组记录<STARTT>;<T,A,10,11>;<STARTU>;<U,B,20,21>;<T,C,30,31>;<U,D,40,41>;<MITU>;<T,E,50,51>;<MITT>.描述回复管理器的行为，包括对磁盘和日志所做的改变，假设故障发生，且出现在磁盘上的最后一条日志记录如下：<STARTU>b)<MITU>SinceUismitted,weredoitsactions,settingBto21andDto41.Then,sinceTisunmitted,weundoitsactionsfromtheendmovingbackwards;wesetCto30andAto10.b)由于U已经提交，我们重做所有U动作，设定B=21和D=41。然后，因为T是未提交的，我们向前回溯进展恢复其行动;我们设置C=30和A=10。编者注：undo/redo日志已经提交的数据要重新做，还没有提交的数据要恢复6.2.7考虑如下日志记录序列<STARTS>;<S,A,60>;<MITS>;<STARTT>;<T,A,10>;<STARTU>;<U,B,20>;<T,C,30>;<STARTV>;<U,D,40>;<V,F,70>;<MITU>;<T,E,50>;<MITT>;<V,B,80>;<MITV>;假设我们在如下日志记录中的*一条写入(主存)后立即开场一个非静止检查点：<S,A,60>;<T,A,10>;<U,B,20>;<U,D,40>;<T,E,50>;对其中的每一个，说明：何时写入<ENDCKPT>记录。对于每一个可能发生故障的时刻，为了找到所有可能未完成的事物，我们需要在日志中回溯多远。-.z.1. <STARTS>;<S,A,60>;<STARTCKPT(S)>;<MITS>;<ENDCKPT>;<STARTT>;<T,A,10>;<STARTU>;<U,B,20>;<T,C,30>;<STARTV>;<U,D,40>;<V,F,70>;<MITU>;<T,E,50>;<MITT>;<V,B,80>;<MITV>;-.z.2. <STARTS>;<S,A,60>;<MITS>;<STARTT>;<T,A,10>;<STARTCKPT(T)>;<STARTU>;<U,B,20>;<T,C,30>;<STARTV>;<U,D,40>;<V,F,70>;<MITU>;<T,E,50>;<MITT>;<ENDCKPT>;<V,B,80>;<MITV>;-.z.-.z.3. <STARTS>;<S,A,60>;<MITS>;<STARTT>;<T,A,10>;<STARTU>;<U,B,20>;<STARTCKPT(T,U)>;<T,C,30>;<STARTV>;<U,D,40>;<V,F,70>;<MITU>;<T,E,50>;<MITT>;<ENDCKPT>;<V,B,80>;<MITV>;-.z.4. <STARTS>;<S,A,60>;<MITS>;<STARTT>;<T,A,10>;<STARTU>;<U,B,20>;<T,C,30>;<STARTV>;<U,D,40>;<STARTCKPT(T,U,V)>;<V,F,70>;<MITU>;<T,E,50>;<MITT>;<V,B,80>;<MITV>;<ENDCKPT>;-.z.5. <STARTS>;<S,A,60>;<MITS>;<STARTT>;<T,A,10>;<STARTU>;<U,B,20>;<T,C,30>;<STARTV>;<U,D,40>;<V,F,70>;<MITU>;<T,E,50>;<STARTCKPT(T,V)>;<MITT>;<V,B,80>;<MITV>;<ENDCKPT>;2假设崩溃发生在<ENDCKPT>之后则只需回溯到对应的<STARTCKPT>，假设崩溃发生在<ENDCKPT>之前则需回溯到上一个<STARTCKPT>习题6.3.2使用习题的数据，对该习题中(a)到(e)的各个位置，答复：何时能写入<CKPT>记录对每一个可能发生故障的时刻，为了找到所有可能未完成的事务，我们需要在日志中向后看多远。请考虑<ENDCKPT>记录在发生崩溃以前写入和未写入的两种情况-.z.1.<STARTS><S,A,60><STARTCKPT(S)><MITS><STARTT><T,A,10><STARTU><U,B,20><T,C,30><STARTV><U,D,40><V,F,