4-9章习题解答.doc 53页

'第4章数据存储与组织管理4.1简要回答以下问题。（1）描述磁盘空间管理器的主要作用，并说明它与OS文件系统的关系。（2）解释关系数据库系统中关系表与文件的关系。（3）如果有一个大文件需要频繁执行顺序扫描，那么，为该文件选择哪种页存储方式最合适？（4）分别描述持久化指针解引用(dereference)和指针混写的这两个基本过程，它们之间有何联系？（5）说明排序文件中的记录及页的基本存储组织方式。（6）解释缓冲区管理器处理一个读页请求的过程。如果被请求页位于缓冲池但未被闩住(pinned)，那么情况会怎样？缓冲区管理器何时写一个磁盘页？（7）一个缓存页被闩住（bepinned）意味着什么？一般由谁负责给缓存页上闩，由谁负责给缓存页解闩?（8）当一个页请求发生时，如果缓冲池中所有页都是脏页，将会发生什么？（9）与OS缓存管理相比，DBMS缓冲区管理器具有那些独特的重要能力？（10）什么是预取？解释为什么这种策略很重要。（11）描述两种可能的记录格式，并指明它们的优缺点。（12）描述两种可能的页格式，说明它们优缺点和适用场合。【解答】（1）磁盘空间管理器支持以页(page)为单位的数据管理，隐藏了下层硬件（甚至包括OS文件管理）的细节，且允许高层软件认为DB数据是一系列以页为单位的磁盘数据集合，是DBMS体系结构中最低层的软件模块。DB系统的磁盘空间管理器通常按三种方式来应用OS的文件管理功能：n将整个DB存储在一个或几个磁盘文件中，调用OS功能实现流式文件的磁盘R/W。n让OS分配给DB系统一个或几个大的OS文件，然后自己管理（读/写）这个文件。n完全自己来管理磁盘。（2）通过磁盘空间管理器，可将DB中的“关系”映射到“关系数据文件”，这种“文件”既可能是实际的OS文件，也可能只是一个虚拟的OS文件。一些小规模的DB系统实现甚至可能将关系直接存储在单独的OS文件中。但更多的现代大型DB系统，则是把所有关系都集中存储在一个或几个大文件中的复杂结构。这时，我们仍然可在概念上认为每个关系被存储在一个“虚拟文件”中。（3）这时选用堆文件的页存储方式最合适。当不需要检索特点的记录，而只是全文件顺序扫描时，选用堆文件的页存储方式最合适，因为这种情况不需维护顺序，插入插入与删除操作很直接，代价较小，另外，也不需要数据本身之外的额外存储空间和辅助索引文件。（1）存取数据库记录/数据页要用到两种类型指针：内存指针与数据库地址(持久化指针)。 根据给定的指针或地址寻找目标对象的过程，称为解引用。给定一个内存指针，查找对象本质上只是对内存单元的一个引用（C语法：*指针名）。给定一个持久化指针，解引用一个对象需要额外的步骤，即需先在“转换表”中查找持久化指针所代表对象的实际内存地址。如果指针所指对象不在内存，则必须从磁盘把它载入，并在转换表中添加新映射项。与内存指针解引用相比，即使转换表中有映射项，通过转换表实现解引用仍是一个慢过程。指针混写是一种减少定位已在内存中持久对象所需代价的方法。其基本思想是，当一个主存中对象/记录所含的持久指针第一次解引用时，这个持久指针所指向的目标对象被定位――如果它不存在内存中，就将它载入内存并同时在转换表中添加一个新的映射项。然后，将存放该持久指针的内存单元，直接修改为目标对象的内存位置指针。下一次同一持久化指针再次被解引用时，就可以直接使用内存引用，从而可避免重复转换内存地址的过程开销。显然，指针混写包含了持久化指针解引用过程，但前者比后者多了一个在主存中同一位置来回修改“持久化指⇔针内存指针”过程。指针混写能降低持久化化对象解引用的过程。（1）排序文件是指按指定的键排序记录集的一种文件组织。虽然在辅存中严格按排序顺序先后安排文件中记录存储，能显著提高记录集检索性能，但这样做的维护代价太大，DB系统一般并不这种做，通常是指针把记录按顺序链接起来。删除记录时仅做标记并留下空位，暂不移动其它记录；而在插入时，相应位置即使没有空位，也暂时不移动其它记录来腾出位置，而是引入溢出页。对排序文件，页内的记录索引项或目录项通常是严格按顺序的。另外，记录链接自动隐含了页间链接。（2）缓冲区管理器执行读页请求的基本过程如下：n检查DB缓冲池中是否存在该请求页，如果该页不在DB缓冲池中，则进一步执行以下一些操作。n基于置换策略，选择一个可被置换的frame，将该frame的pin_count计数加1。n如果该frame中原先页被修改过（即dirty=1），则将原先页写回磁盘。n从磁盘读入新请求页到该frame中，同时置dirty=0。n返回包含请求页的frame地址给请求者。如果被请求页位于缓冲池但未被闩住(pinned)，那么该页不会被替换，即没有新页可被读入该页所占据的页框。当一个缓存页已被修改过(dirty位置1)，且该页未上闩，所占据页框需读入新页时，通常会触发缓冲区管理器写一个磁盘页。（3）缓存页备闩住意味着与该页对应的pincount>0，每pin一次，pincount加1。拴住一个能为高层DBMS软件保证缓冲区管理器不会将该页从缓冲池移除，即其它文件页不会被读入该被闩页所占据的页框。一般有缓冲区管理器具体执行pin/unpin页，但页请求者有责任通知缓冲区管理器unpin一个不再用的页。 （1）当一个页请求发生时，如果缓冲池中所有的页都是脏页，缓冲区管理器会依据缓冲区置换策略选择要换出frame,并将该frame中原先的页写回磁盘。从磁盘读入请求页，同时将dirty置0，返回包含请求页的地址给请求者。（2）与OS缓存管理相比，DBMS缓冲区管理器有以下几个特别功能特性：a)因为与一般应用相比，DMBS更容易准确预测磁盘页存取顺序。所以，DBMS缓冲区管理器通常能更好、更灵活地选择合适的页置换策略，或采用一些特别的、适合于DB环境的特殊管理措施。b)因可更准确预测引用模式，DBMS缓冲区管理器可以使用一些很简单、但却非常有效的预取策略，以有效减少多个连续页的磁盘I/O时间。c)当决定一个页何时被写回磁盘时，DBMS希望或需要有更多的控制权。（3）假设A块、B块存储在磁盘相邻的位置上。系统预计或猜测到A和B两块可能会先后同时被访问，故当A块需要被读入主存时，系统顺带把B块也读入主存缓冲区。这种方案通常可减少I/O操作时间，显著提高DBMS系统性能，是DBMS优化的一个很重要策略。（4）定长记录格式和可变记录格式（详见书本4.5节）。（5）连续槽的页组织格式和基于目录槽的页组织格式（参见书本4.4节）。4.2考虑一个磁盘：它有5个双面盘片，每个盘面2,000个磁道，每个磁道50个扇区，每个扇区512字节。另外，假设它的平均寻道时间为10msec。（1）计算每个盘面的格式化容量和整个磁盘的格式化容量。（2）如果磁盘转速为5,400转/分钟，计算磁盘的最大旋转延迟和平均旋转延迟时间。（3）在256、2048和51,200三个值中，那些值是可能的有效块大小？为什么？（4）如果每个磁盘块大小占2个扇区，试估算传输一个块的平均时间。【解答】（1）每个盘面的格式化容量＝磁道数*扇区数*字节数=2000*50*512B≈49MB整个磁盘的格式化容量＝盘面数*每个盘面的容量=10*49M=490MB（2）最大的旋转延迟时间＝磁盘旋转一周所用的时间＝1/转速=60/5400=0.011s平均旋转等待时间＝最大的旋转延迟时间/2=0.011s/2=0.0055s（3）块是DBMS与OS实际读写磁盘的基本单位，必须是扇区大小的整数倍；其次，块大小选择要适中，太小会导致I/O数增加，太大则会造成磁盘读写操作浪费加大，都不利于管理。因此，三个值中，只有2048可能是有效块大小。（4）旋转传输1个块的时间=读两个扇区所用的时间=（60/5400）*（2/50）≈0.44ms传输一个块的时间=寻道时间＋旋转延迟时间＋传输时间=10ms+5.5ms+0.5ms=16ms4.3对习题4.2中磁盘，若磁盘块大小为1,024字节。假设有一个包含100,000个元组、每个元组100字节的关系文件存储在该磁盘上，并规定记录不允许跨块存储。（1）每个块中可存放多少个元组？存储整个文件需要多少个块？（2）估算顺序扫描该关系文件需要的总时间。 （1）如果该磁盘的各盘面上磁头能并行读/写数据，且磁盘数据是按可能的最优方式安排存储，这种情况下，执行全文件顺序扫描需要多少时间？【解答】（1）每个块可存放元组数＝磁盘块大小/每个元组字节数=1024/100=10个存储整个文件需要块数＝总的元组数/每个块元组数=100,000/10=10,000块（2）顺序扫描文件需总时间＝文件总存储块数*每块存取时间≈10,000*16ms=160,000ms＝2.7分钟（3）根据题意，可认为读写一个柱面时间＝最大的旋转延迟时间＝0.011s一个柱面大小＝盘面数[10]*扇区数*字节数=10*50*512B按柱面安排连续存储文件需要的柱面数=100,000*100/(10*50*512)=40（向上取整）所以，这种情况下，顺序扫描文件需总时间＝40*0.011s≈0.5s4.4假设某磁盘具有以下特性：有10个盘面，每个盘面10,000个磁道；每个磁道1000个扇区，每个扇区512个字节；每个磁道20%被用于间隙；磁盘旋转速率10,000转/分钟；磁头移动n个磁道所需时间为1+0.0001n毫秒。请回答关于该磁盘的以下问题：（1）磁盘的总容量是多少？（2）最大寻道时间和最大旋转等待时间分别为多少？（3）如果一个块是16,384字节（即32扇区），那么，一个块的传输时间是多少？【解答】（1）磁盘总容量＝盘面数*磁道数*扇区数*字节数=10*10000*1000*512B=47.7GB（2）最大寻道时间＝磁头跨越所有磁道时间=1+0.0001*9999≈2ms最大的旋转等待时间＝磁盘旋转一周的时间=60/10,000s=6ms（3）一个块（含32个扇区&31个间隙）所占圆弧度=32*0.8*(360/1000)+31*0.2*(360/1000)=31.8*360/1000旋转通过这样大小弧长需时间=((31.8*360/1000)/360)*6ms≈0.19ms平均寻道时间，取1/3的最大寻道时间＝2ms/3=0.67ms平均旋转等待时间，取1/2的最大旋转等待时间＝6ms/2=3ms所以，传输一个块的时间＝0.67ms＋3ms＋0.19ms≈3.86ms4.5假设我们正在为某磁盘调度I/O请求，磁头的初始位置在磁道4000。已知该磁盘寻道时间可按公式（1+移动磁道数/500）毫秒来计算，到达磁道后访问一个块的平均时间还需要约8.3毫秒。假定调度时已经产生的请求共有4个，它们所在的柱面分别为:1000/6000/500/5000，它们达到的先后时序值分别为0/1/10/20。试分别计算下列两种情况下，服务完这些请求需要的时间。（1）采用电梯算法，先从任何方向开始移动都是可能的。 （1）采用先到先服务算法。【解答】（1）由于最先到的的请求是1000，假设磁头向下运动，那么，电梯调度策略的块访问情况如下表所示。块请求及被服务顺序完成时间1000(1+3000/500)+8.3=15.350015.3+(1+500/500)+8.3=25.6500025.6+(1+4500/500)+8.3=43.9600043.9+(1+1000/500)+8.3=55.2（2）若采用先到先服务策略，则各块请求被服务并完成时间如下：块请求及被服务顺序完成时间1000(1+3000/500)+8.3=15.3600015.3+(1+5000/500)+8.3=34.650034.6+(1+5500/500)+8.3=54.9500054.9+(1+4500/500)+8.3=73.2对比这两种磁头调度策略，不难发现，采用电梯算法可节省约18s时间。4.6某磁盘传输速率是传送每个4096字节块0.5毫秒。若要实时播放一部MPEG影片要求每小时至少传1GB字节。如果我们能以最好的方式在该磁盘上安排MPEG影片的块，能实时播放该影片吗？如果不能，则需要多少个该型磁盘？且应如何在这些磁盘上安排块，才能使影片在播放时有最小的延迟？【解答】如果我们按连续柱面方式安排存储块，这样可忽略寻道时间和旋转等待时间，那么，传送1GB字节至少需要时间为：（230/4096）×0.5ms=131s，约2分钟。远小于1小时，所以完全可到达实时播放要求。4.7考虑基于目录槽变长记录页格式。（1）管理目录槽的一种方法是使用最大目录槽号，并在页创建时分配目录数组。给出赞成和反对该方法的理由。（2）建议该方法的一种改进，使得允许我们能在不移动记录和不改变记录rids的情况下，按某个字段排序记录。（3）估算顺序扫描该关系文件需要的总时间。【解答】（1）采用最大目录槽号方法比较简单，但不灵活。因为这种方法很容易导致保留过多的槽或槽不够用情况，这是因为系统无法预测页中存储记录的长度。（2）一种允许记录按指定的字段排序的改进方案是：在页首存储象<页内逻辑记录号,记录偏移地址>结构形式为记录槽目录项数组。 4.8假设我们使用RAID4级方案，有4个数据盘和一个冗余盘。假设块为单字节，如果数据盘中相应的块值如下，试给出冗余盘的块值。（1）01010110,11000000,00111011和11111011。（2）11110000，11111000，00111111和00000001。【解答】（1）01010110；（2）001101104.9采用带有7个磁盘的RAID6级方案,描述从下列故障中恢复所要采取的步骤（1）盘1＃和盘7＃。（2）盘1＃和盘4＃。【解答】（1）先用2#、3#、5#号盘恢复盘1#的数据，再用1#、3#、4#号盘恢复盘7#的数据。（2）先用2#、3#、5#号盘恢复盘1#的数据，再用1#、2#、6#号盘恢复盘4#的数据。 第五章数据库索引技术5.1简要回答以下问题。（1）如果要频繁进行：①基于某字段值的范围搜索；②执行插入和扫描操作，不关心记录顺序；③基于特定的属性值搜索记录。那么，我们应分别选择基本文件组织方式中的哪一种？（2）说明索引项的三种基本形式。（3）①说明顺序索引的基本概念，并指出稠密索引在哪些情况下，不需要数据文件是排序文件。②说明稀疏索引的概念，稀疏索引肯定是聚集索引吗？相应的数据文件肯定是排序文件吗？请解释原因。③二级或二级以上索引肯定是稀疏索引吗？为什么？（4）辨析以下概念对，说明它们之间的差异。（a）聚簇文件与聚集索引；（b）稠密索引与稀疏索引；（c）主（码）索引与辅助索引。【解答】（1）以操作代价作为依据：要频繁作基于字段值的范围搜索：应该选用排序文件作为基本的文件组织方式。要频繁执行插入和扫描操作，应该选用堆文件作为基本的文件组织方式。要频繁作基于特定属性值的搜索记录，应该选用散列文件作为基本的文件组织方式。（2）索引项的三种基本形式：索引项k*就是数据记录本身，没有另外单独的索引文件。，有独立的索引文件，每个索引项只能给出一个rid.,有独立的索引文件，每个索引项允许包含多个rid.（3）①顺序索引是指按索引键值顺序来组织索引项的索引文件。如果每个索引键值都至少对应有一个索引项，则称索引为稠密索引。在稠密索引情况下，如果每个记录都对应有一个索引项，或在每个索引项中存储包含键值的记录指针链表，则可以不要求数据文件是排序的。②只为搜索键的某些值建立索引项的索引称为稀疏索引，稀疏索引必须是聚集索引。聚集索引是指一个索引文件中索引项的排序方式和数据文件记录的排序方式一致的索引方式，所以，与稀疏索引对应的数据文件一定是排序文件。③二级或二级以上索引肯定是稀疏索引，因为如果还是像稠密索引那样一对一地建立二级索引的话，索引项或索引文件大小没有实质减少，没有什么意义。作为索引一定是排好序的，故在低级索引基础上可建立更稀疏的上级索引。（4） Ø区别聚簇文件与聚集索引-聚簇文件：指数据文件，这种数据文件的每个页中，都只存放同一个关系表的记录。-聚集索引：指一种索引文件，这类索引文件中索引项的排序方式和数据文件记录的排序方式一致时。虽然一个数据文件可以根据不同索引键建立不同索引文件，但至多只能有一个索引文件是聚集的。Ø稠密索引与稀疏索引（参见前一小题说明）Ø区别主(码)索引与辅助索引-主索引或主码索引：指搜索键恰好是主码的索引。因为一个关系数据文件最多只有一个主码，所有每个关系最多也只有一个主码索引。通常主码索引往往也是聚集索引。主码索引中肯定没有重复索引项，因为主码肯定是候选码，没有重复键。-辅助索引：非主索引的索引文件。辅助索引中通常会有重复索引项。图5.21习题5.2附图图5.22习题5.3附图5.2考虑图5.21所示的阶数m=4的B+树索引。（1） 标示插入数据项9*之后的B+树，并指出完成该插入需要读多少个页和写多少个页。（1）给出在原树中删除数据项8*之后的B+树，并指出完成该操作需要读多少个页和写多少个页。（2）给出在原树中先插入数据项46*，然后再删除数据项52*之后的B+树。（3）给出在原树中，依次删除32*、39*、41*、45*和73*之后的B+树。【解答】（1）由图看出插入9*不需要分裂，直接插入即可。由于索引项即数据文件本身，从根结点到索引项读3个页。只有叶结点改过，所以写1个页。插入后的局部图如下：（2）删除8*后要跟前一个索引项重组，从根结点到两个索引项要读4个页。操作完成后两个叶结点和一个中间结点是脏页，故要写出3个页。删除后的局部图：(3)可直接插入数据项46*。删除数据项52*则要合并重组，操作完成后的局部图：(4)依次删除32*、39*、41*、45*、73*后的图： 5.3考虑图5.22所示B+树索引：内节点可容纳4个键值和5个指针；叶节点中直接存储数据记录，可容纳4条记录且相邻叶节点之间用双链连接在一起。回答以下问题。（1）指出回答查询“取搜索键值大于38的所有记录”时，需要读取的有关节点。（2）给出插入109*后的B+树。（3）给出从原树中删除81*后的B+树。（4）给出一个插入时会导致树高度增加的键值。（5）图中没有详细给出子树A、B和C。你能推测出这些子树的内容和形状吗？【解答】(1)查询大于38*的所有记录，要读取的节点有：I1,I2,L2,L3,L4,L5,L6,L7,L8(2)插入109*后，原L8节点需要分裂，完成操作后的局部图：(3)删除81*后，L6,L7两个节点要重组，操作完成后的局部图如下： (1)插入任何[65,79]之间的搜索键值，都会分裂L5节点，而I2也是满的，向上分裂到根结点，根结点也是满的，就会导致高度增加一层。(2)关于子树A、B、C，我们可推出以下几件事：1）它们都是树高为1的子树，因为它们的相邻子树，即以I2、I3为根节点的子树树高都是1；2）子树A包含的键值树肯定少于10个，子树B所包含的键值在范围[10,20）之间，子树C所包含的键值在范围[20,30）之间；3）每个中间节点至少会含有3个键值和3个指针。5.4假定我们有一个排序文件，希望在该排序文件基础上构造一个稠密B+树聚集索引。（1）最简单的方案是：扫描文件，并利用B+树插入算法将记录逐个插入到树中。指出该方案在性能和存储利用率方面存在的问题。（2）说明如何用批量加载算法来改进以上方案。【解答】（1）利用标准的B+树插入算法，逐项插入，这种方法可能代价非常昂贵，因为每个项加入都需要从根开始到达合适的叶节点。尽管在连续请求时索引层次的页，可能仍保持在缓冲池中，但这样的开销可能仍然非常可观，在树构建过程中会经历大量叶节点及相关内节点的分裂调整。（3）而采用批量加载方法的效率则要高得多，在树的批量构建过程中可以有效避免叶节点分裂调整，只有少量内节点的顺次分裂调整，以及与树高相对应的有限几次根节点调整。批量加载构建B+树的基本过程步可描述如下：n第一步，从一个关系记录集创建要插入到索引的数据项。该步包括扫描关系记录集，并生成和写出相应的数据项。其代价为(R+E)次I/Os，这里，R是包含记录集的数据文件页数，E是包含数据项的总页数。n第二步，排序数据项；外部排序含数据项的E个页，保守估计需要3E次I/Os（参见6.1部分）。n第三步，从排序好的数据项中建立B+树索引。因为第二步中已排序数据项的数据页，可在它们从排序步输出时，直接调用批量加载算法依次加入到新的B+树中，因此，第三步的代价只是写出所有（内节点）索引页的代价。批量加载算法的总代价为：R+4E+(B树索引节点数)5.5考虑表5.2所示的student关系示例。构造以下几种情况下的4阶B树，假定简单使用溢出页处理重复键值情况。要求使用比k*约定更清晰的方式，在B+树中标示数据项。 （1）age字段上的稠密B+树索引，索引项为数据项。（2）age字段上的稀疏B+树索引，索引项为数据项。（3）gpa字段上的稠密B+树索引，索引项为键值加记录指针。为便于问答这个问题，我们假定实际元组记录存储按图中给定顺序的排序文件中，每个页可存三个元组，前三个元组存储在第1个页的第1/2/3槽中，第4/5/6个元组存储在第2个页的第1/2/3槽中，…。【解答】图5.25习题5.5题解附图 （1）建立age上的稠密索引，见图5.25（a）（2）建立age上的稀疏索引，见图5.25（b）（3）建立gpa上的稠密B+树索引，见图5.25（c）注意，数据项未必按数据记录同样的顺序存储，因为它们可能按不同的顺序被插入到B+树中。我们假设采用简单的插入算法，首先以常规方法定位叶节点，如叶节点中已经有同样键值的数据项，就将新数据项安排到与该叶节点链接的溢出页。这样，可保证每个叶节点中的数据项都有不同的键值。这种做法会导致的一个问题是：当叶节点满而需要分裂时，必须扫描溢出链以确保当一个键值被移动到一个新叶节点时，所有该键的重复项也能伴随移动到新叶节点的溢出页中。另一种方案是分别维护每个键值的重复项溢出链，但考虑到每个页的容量限制，且一个给定键值的重复项数可能很少，故这个方案可能导致很差的空间利用率。5.6关于可扩展散列，请回答以下问题。（1）解释为什么需要全局位深度和局部位深度。（2）在一个引发目录项翻倍的插入后，有多少个桶恰好只有一个目录项指向它？如果从这些桶中删除一个项，那么目录项数是否会发生变化？请给出简要解释。（3）翻倍目录项时，我们需要检查所有局部位深度等于全局位深度的桶吗？（4）对检索一个给定键值记录，可扩展散列能否保证只用1次磁盘I/O完成？（5）如果散列函数在数据项上严重偏斜，那么，关于桶目录大小和桶空间利用率方面，你能得出什么结论？（6）对相同数据项，给出一个线性散列方法组织存储需要的总页数多于可扩展散列存储方法的具体例子。【解答】（1）可扩展散列允许根据插入或删除而引起的数据项数目变化，动态调整目录项的大小。一旦目录项大小变化（翻倍增加或翻倍缩小），应用到搜索键值的散列函数值需保留的有效位数也要随之变化。扩展散列中用全局位深度（globaldepth）决定散列函数值需保留的有效位数。目录大小的增加并不会导致每个新目录项创建新数据桶。目录项翻倍增加时，所有新目录项都与对应的老目录项共享相同的数据桶。当一个被两个或更多目录项所共享的数据桶需要分裂时，并不会导致目录项翻倍增加。这意味着我们需要知道每个桶是否被两个或多个目录项共享。这个信息由局部位深度(localdepth)指示。（2）有且只有两个桶是这种情况（只有一个指向它的目录项），这是因为导致目录翻倍哪个新插入项对应桶必须分裂为两个桶。如果恰好有一个数据项要从这两个桶中的某个桶删除，那么可能会导致两个桶合并，但是否一定进行桶合并，取决于具体的算法策略。如果算法只合并处理空桶，就不一定会发生桶合并情况；而如果算法策略是只要可能就合并桶，则就会导致插入翻倍目录的逆操作――不仅会导致桶合并，而且会导致目录减半压缩。（3）不需要。因为仅当一个桶需要分裂时，才需要检查该桶的局部位深度。（4）可扩展散列并不保证仅用1次磁盘存取来完成记录检索。当目录文件不在主存，或数据桶中存储的只是记录指针或记录指针列表时，都可能需要额外的I/O。（5）如果散列函数在数据项上严重偏斜，那么，桶目录大小和桶空间利用率都会很差。 图5.26习题5.6题解附图（6）对于以下键值序列：8,16,24,32,40,48,56,64,128,7,15,31,63,3,1,10,4。可扩展散列需要9个页（包括目录页），而线性散列为10个页。具体索引结构可参见习题题解附图。5.7考虑图5.23所示的可扩展散列索引文件。回答以下问题。图5.23习题5.7附图图5.24习题5.12图（1）从图中，我们能否看出哪个是最后插入的项，为什么？（2） 若已知到目前为止没有删除发生，那么，从图中我们能否看出哪个是最后插入的项？（1）若已知到目前为止没有删除发生，那么，从图中我们能否看出哪个是导致桶分裂的最后插入项？（2）给出或标示插入68*后的索引文件结构图。（3）给出或标示插入17*、69*后的索引文件结构图。（4）给出或标识删除21*后的索引文件结构图。【解答】（1）不能，它可能是索引中的任何数据项之一。从当前已有索引项中，我们通常总能找出多个以某个特别键作为最后插入项的插入删除序列。例如，考虑数据项16，若先依次插入数据项1521101575141236648245616（最后插入项），然后再依次删除56、24和8就会导致图5.23的可扩展索引结构布局。显然，对以任何一数据项做最后插入项，我们都总能找到一个或多个插入删除序列。（2）虽然我们无法断定那个是最后的插入项，但可以断定最后一个插入项肯定没有导致桶分裂，因为已分裂的桶只有A，且A与A2桶中数据项总数为6，而不是5。（3）首先，导致桶分裂的最后插入项不可能在桶C中，因为C只能与跟它局部位深度也是2的B或D构成分裂映象对，且C与B，或C与D的数据项数和都为4，少于最少要求的项数5。如果开始时全局位深度为1，且还没有桶A2的情况下，那么，导致桶分裂的最后插入项应在B与D桶中，因为D是B位深度相同（均为2），且D与B桶的总数据项数为6（超过5）。综合以上分析，我们可得出结论：如果开始时全局位深度位2，且没有发生过删除操作，那么导致桶分裂的最后插入项肯定在A与A2桶中。 插入68*后的索引文件结构图见：图5.27（a）习题5.7题解附图-1（b）习题5.7题解附图-2图5.27习题5.7题解附图（1）插入17*、69*后的索引文件结构图图见：图5.27（b）（2）删除21*后的索引文件结构图见：图5.27（c）图5.27（c）习题5.7题解附图-3 5.8关于可线性散列，请回答以下问题。（1）如果允许使用溢出页，线性散列如何保证提供只比1多一点（比如1.2）的等值搜索平均代价。（2）对共包含有N个数据项（即N个记录）、每页可存储P个记录的情况，如果采用线性散列方法来组织存储，且假设页的平均利用率为80%，那么，等值搜索的最坏代价是多少？（3）如果散列函数在数据项上严重偏斜，那么，在数据页的空间利用率方面，你能得出什么结论？（4）对相同数据项，给出一个线性散列方法组织存储需要的总页数少于可扩展散列方法的具体例子。【解答】（1）在一个轮中，线性散列所有的桶将按顺序依次分裂一次。如果散列函数对散列键分布均匀，那么，这种在一个轮中的轮流分裂方式，一般都能导致键值在所有桶中的重新分配。即使一个桶有溢出页，经这样的一轮分裂下来，每个桶增加的溢出页长度一般不会超过1（如果散列函数分布很好的话）。（2）N/(0.8P)。这是当散列函数极度偏斜，所有键都被映射到同一个桶的情况。另外，这里占有率，会影响需要的存储页数。（3）参考习题5.6(6)附图。如果系列数据的键值为2i,i>k，那么，通过选择适当的k值，会导致所有的数据项都被映射到桶0中。若规定每次当需要增加一个溢出页到桶0时，都会导致桶分裂。那么，这是空间利用率，还不到50％。（4）考虑如下键值序列：0,4,1,5,2,6,3,7。且两者的散列函数相同，且每个页都可容纳4个记录。在这种情况下，可扩展散列需要4个数据页和1个目录页，而线性散列只需要正好4个页。5.9考虑一个包含有1,000,000个元组的关系R(a,b,c,d)。已知：每页可容纳10个元组；R按堆文件组织、记录无序。假设属性a是R的一个候选键，取值范围0～999,999。若有三种可能的存取路径：1）扫描堆文件R；2)利用R.a上的B+树索引；3）利用R.a上的散列索引。那么，对以下给定的每个查询，指明具有最小查询处理代价应选用的存取方法。（1）检索R的所有元组；（2）检索满足a<50的所有元组；（3）找a＝50的所有元组。 【解答】（1）如果是检索R所有的元组，采用直接扫描堆文件即可。利用索引反而是浪费存取索引项的代价。（2）如果检索a<50的所有元组，由于a是利用B+树索引只需要查询一次索引文件的代价与读取最多50次I/O的数据文件的代价，利用散列索引要查询50次索引文件的代价与最多50次I/O的数据文件的代价，而扫描堆文件需要扫描完整一个文件的代价。因此，选用B+树索引是最理想的。（3）如果检索a=50的记录，由于a是候选键，满足条件的记录只能有一条，所以利用散列索引只需1~2次I/O，而利用B+树索引也只要2~3次，但扫描堆文件则是一个不确定的代价，最坏可能要扫描完整个文件。所以选用散列索引最合适。5.10（1）针对属性a不是R候选键情况；（2）如果R是基于a的排序文件。分别重新回答习题5.9中的所有问题【解答】（1）针对属性a不是候选键的情况，检索R所有元组是一样的，扫描堆文件是最好的方式。检索a<50的所有元组，由于a不是候选键，不能确定满足条件的记录数目，而且由于B+树/散列索引一定不是聚集索引，所以有可能最坏的代价比扫描整个文件还要差。检索a=50的元组也一样，即使有散列索引，但由于非聚集，读取数据文件所用的I/O数可能与满足条件的记录数一样多。所以在这两种情况下采用堆文件的方式也许最好。（2）针对R是基于排序文件的的情况，由于索引是聚集的，检索所有元组采用扫描堆文件最合理。对a<50的范围检索，采用B+树索引合理。对于a=50的检索采用散列索引最合理。5.11假定采用每当插入出现页溢出作为触发桶分裂的条件，考虑图5.24所示线性散列索引文件临时快照。（1）假设有最理想的散列键值均匀分布，那么，在引起第一次桶分裂前，可被插入的最大数据项数和Next值分别是多少？请给出简要解释。（2）画出或标示在只插入一个记录就引发桶分裂后的索引文件结构示图。（3）假设有最理想的散列键均匀分布，那么，会导致四个桶都发生分裂的最少需要插入数据项数及Next值分别是多少？请给出简要解释。【注，原题目有误】【解答】（1）6项，Next=0。只要有溢出项发生，Next值就会变化，就会有分裂发生。而从图中看到:这时所有桶空闲项总和正好为6个，故在不发生分裂的情况下可插入的最大记录数为6。（2）由于最后一个数据页是满的，只要插入一个属于该桶的记录项，就会发生溢出，引发桶分裂。分裂前后的索引图5.28所示。分裂后，Next=1。（3）8项．首先，插入63引起第一次（也正好是第一个桶）分裂；插入41,73引起第二个桶分裂，因只有5被分到新分裂桶中，分裂后第二个桶仍是满的。插入137引起第三个桶分裂。最后，要导致第四次分裂――让第三个个桶溢出，至少还需插入4个都进入第三个桶的记录项（如18,34,66,130）。综合以上分析，可得出：为导致四个桶都分裂一次的最少插入记录项数是8。 图5.28习题5.11题解附图5.12对图5.24所示的那组数据项，给出基于可扩展散列索引的存贮组织结构图，并回答习题5.11中的那些问题。【解答】对图5.24所示的那组数据项，给出基于可扩展散列索引的存贮组织结构图如图5.29(a)所示。（1）6项。原因与5.11（1）相同。图5.29习题5.12题解附图（2）如图5.29(b)所示。（3）10项。可扩展散列情况比较简单，让每个溢出就可导致该桶分裂。5.13关于位图编码和压缩位图的解码，回答以下问题。（1）已知位图编码011000,000,01000,00100；给出对应的压缩位图编码。（2）已知位图编码000,1000,000,000,01000,001000,0；给出对应的压缩位图编码。（3）已知压缩编码1110100100110110011011；给出对应的位图编码。【解答】（1）011000,000,01000,00100对应的压缩位图编码0100110111110101（2）000,1000,000,000,01000,001000,0对应的压缩位图编码1011，11101010，110101（3）1110100100110110011011对应的位图编码000,000,000,110,000,001,010,0015.14 考虑一个有1,000,000个记录的文件，且字段F有m个不同值。作为m的函数，F的位图索引有多少个字节？【解答】F的位图索引有的字节数：1000000*m/85.15关于空间索引，简要回答以下问题。（1）描述空间数据的两种主要类型。（2）描述空间查询的三种主要类型。（3）为什么在多媒体应用中最邻近查询非常重要？（4）为什么B+树索引不同于一个空间索引？对于点数据，何时你使用一个B+树索引效果优于空间索引？对于点数据，何时你使用空间索引优于B+树索引？【解答】（1）空间数据的两种主要类型：n点数据（pointdata）：空间点数据的基本特点是只有位置，没有大小、边界，不占据空间。n区域数据（regiondata）：区域数据是同时具有位置和边界的空间延展。可将区域位置视为区域的固定‘锚点’，比如重心点。（2）空间查询的三种主要类型：n范围查询(rangequeries)：。空间范围查询通常关联着一个区域，并要求返回与目标区域范围重叠(overlap)或位于目标区域内的、指定类型的所有区域对象。n最邻近点查询(nearest-neighborquery)：要求找出离指定点最近的对象。n空间连接查询(spatialjoinqueries)：关联连接两个或两类空间区域的查询。这类查询的典型例子包括“找相互间距离不超过200公里的城市组对”，“找靠近某区域（如一个湖泊）的所有城市”。(3)因为通过映射/变换多媒体对象到特征向量点，可将查找相似对象问题转换为关于特征向量点集的最小邻近点查询问题来处理；而通过最临近查询，可以高效解决多媒体应用中碰到的很多相似对象匹配或搜索问题。(4)B+树索引只是一维索引，对二维或更高维空间点数据或区域数据查询基本没有作用。对于点数据，仅当进行单个维检索，且按B+树搜索键的前缀检索按该键排序的数据文件时，B+树索引效果才会优于空间索引。其它情况，空间索引对于点数据的检索都要好于B+树索引。5.16考虑含100万个记录点的关系R(x,y)，这些记录点随机分布在矩形区域(0,0)－(1000,1000)内。假设：①每个页可存放100个记录点的数据，B-树的每个叶结点可容纳200个键值－指针对；②x值落在[450,550]范围内的记录点数约有10万个，y也是如此；而x和y同时落在[450,550]范围内的记录点数约有1万个。试估算执行范围450≤x,y≤550内的记录点查询时，所需的I/O次数。【解答】把B＋树的根保存在主存，且叶结点的指针已按照查找键排序；访问每一维的10万个指针，需要检查一个B 树中间层结点和所有包含所需指针的叶结点。对每个B树，我们需要查看约500个叶结点X:B树要查找100,000/200＝500个叶节点Y:B树要查找100,000/200＝500个叶节点访问B树的中间节点：X,Y的B＋树中间节点各1次。因此，检索B+树，获得1万个记录指针，大约需要进行1002次的I/O操作。而检索这1万个目标记录指针对应的数据记录，最坏情况下，可能还需要进行1万次的I/O操作。这通常已超过数据文件本身的所有页。5.17考虑图5.17子图①（左上角）中所标示的、含有三个数据点网格文件。（1）给出在按列表顺序分别插入第6、9、10、7、8、4和5这些数据点后的网格文件。（2）讨论如何使用网格文件处理区域数据。【解答】（1）参见书本图5.17。（2）基于网格文件页很容易回答范围查询和最邻近查询。对于范围查询，我们使用线性标度识别要存取的网格目录项组，然后分别检查这组目录项对应的数据桶，来计算回答范围查询的结果。对于邻近查询，我们首先检索给定点所属的网格目录项，并搜索它所指向的数据页。如果该页是空的，我们就使用线性标度计算包含给定点分区之所有邻近分区，检查这些邻近分区数据桶中的数据点，来确定最邻近点。 5.18.参考图5.18，独立回答以下问题。（1）标示一个能插入R4，但不能插入R3的新对象边界。（2）标示一个能同时包含在R1和R6，但被插入R6的新对象边界。（3）标示一个能同时包含在R1和R6，但被插入R1的新对象边界；该对象将被存放在哪个叶节点？（4）若搜索某对象时需要同时检索R1和R2子树，试给出该对象的一个例子。（5）给出一个示例查询，需要检查R3和R4，但不要检查R5（如果没有这样的查询，则给出解释说明）。（6）给出一个示例查询，需要检查R3和R5，但不要检查R4（如果没有这样的查询，则给出解释说明）。【解答】（1）一个能插入R4，但不能插入R3的新对象边界。NEW包含在R4中，但不包含在R3中，所以能插入R4，但不能插入R3。（2）一个能同时包含在R1和R6，但被插入R6的新对象边界。NEW同时包含在R1与R6中，但是对于R6能完全覆盖NEW，所以被插入到R6中。 （3）一个能同时包含在R1和R6，但被插入R1的新对象边界。NEW同时包含在R1与R6中，但是对于R1能完全覆盖NEW，所以被插入到R1中。对比题中的图可知道，NEW靠R4最近，所需的扩展也最小，所以应该被插入到R4中。（4）由于R12与R16同时包含在R1与R2中，所以要检索他们两个数据项时，需要同时检索R1和R2子树。（5）例如，要检索R9和R10时，由于它们同时包含在R3与R4中，但与R5没有关系，所以需要检查R3和R4，但不要检查R5。 第六章关系操作符赋值6.1简要回答以下问题。（1）说明最有选择性存储路径的概念。（2）什么情况下可认为一个选择条件能匹配选择索引？对一个给定的索引，如何来区分选择条件中的主项和非主项？（3）“块嵌入连接”算法是否肯定优于“页嵌入连接”算法？为什么？（4）如何理解基于索引的嵌套循环连接可避免枚举叉积结果？块嵌入连接和排序归并连接能避免枚举叉积结果吗？（5）从代价、主存要求等方面，比较基于排序和基于散列的消除重复算法，说明它们的优缺点。（6）从代价、主存要求等方面，比较两趟算法的排序归并连接和散列连接，说明它们的优缺点。（7）混合散列索引连接是如何改进基本散列连接算法的？（8）说明可用全关系一趟算法实现的一元操作符、可用全关系一趟算法实现的二元操作符。（9）若S是较小关系，参考算法6.7，分别给出R-S和S-R的一趟算法描述。（10）通过一具体例子，说明缓冲区置换策略会影响连接算法的性能。【解答】（1）当同时存在多种存取路径时，称具有最小存取代价的存取路径为最具选择性存取路径。本质上，它指在执行查询赋值期间需要存取的页数最少的那个查询存取路径。（2）称一个索引能匹配选择条件，如果索引可被用来检索满足条件的元组。一个主项是指能匹配索引的那个合取子项。（3）肯定。对两个大小分别为M和N个页的关系连接，页嵌入连接算法的代价为M+M*N，而块嵌入连接算法的代价为N+M*N/(B-2)，其中，B为可用的主存缓存块数。（4）在基于索引的嵌套循环连接算法中，对外层关系的每个元组，只需要以当前外层元组的连接属性值作为搜索键值，从索引检索匹配元组，并不需要扫描整个内存关系去检查与每个内层关系元组是否匹配。因此，可避免枚举叉积结果。排序-归并连接只需要比较两个排序关系的对应等值分区元组，因此，也可避免枚举叉积结果。但嵌套循环连接算法不能避免枚举叉积结果，它只是比简单嵌套循环连接算法更快（因为可减少扫描内层关系的次数）。（5）假设待排序关系的大小为T个页。基于排序算法要求可用缓存页数B>(T)1/2 以保证可按两阶段完成排序，相应算法代价都为M+2T次I/Os。而基于散列算法要求可用缓存页数B足够容纳最大的划分(子桶)，在划分均匀情况下，也是要求B>(T)1/2。但若散列划分不均匀，则可能需要比(T)1/2更大一些的B值。散列算法代价也是M+2T次I/Os。考虑到DB系统有优化得很好的排序工具(函数)、排序方法的投影结果集是排序的、散列可能存在偏斜和CPU的代价等因素，选用排序方法似乎更好些。（1）对等值连接，散列索引通常能提供很好的性能。假设两个待连接关系的大小分别为M、N个页。当缓存较大B>(f*max(M,N))1/2（这里，f为主存散列因子）时，散列连接代价只有（M+N）*3次I/Os。如果还有更大的缓存可能，除了实现正常散列算法需要的主存页数外，还有额外缓存能驻留存储1个甚至更多个桶，那么，采用混合散列连接还可以大幅度地改善性能。B>(max(M,N))1/2时，改进的排序-归并算法代价也只有（M+N）*3次I/Os，排序-归并连接还有一个额外的优势――可产生按连接键排序的输出结果。当主存很大时，用散列连接效果通常会更好，但当需要基于连接属性的排序输出，也可能选择排序-归并算法。当可用主存很少，排序需要多个阶段，散列需要递归进行多次子桶划分时，排序-归并和散列连接算法的性能都会显著下降。另外，对非等值连接，不能用散列连接算法，我们只能选用排序-归并，或索引嵌入循环等连接实现方法。（2）混合索引连接能显著改善性能。例如，通过在划分阶段（而不是将它留到探测阶段）就完成首个桶的元组匹配比较，这能节省掉第一个分区的读/写代价。（3）全关系算法指操作施加于整个关系上而非施加于单个元组上，关系中的多个不同元组可能会共同影响一个结果元组，或已处理过的元组对随后的元组处理有影响。如果希望一趟完成全关系算法，那么要求主存比较大。对于消除重复或分组聚合等一元操作，要求能容纳得下整个运算结果。对集合并交差，或连接等二元操作符，要求能至少能容纳整个较小输入关系。（4）略。（5）缓冲区置换策略影响连接性能的一个典型例子是：在简单的嵌入循环连接时，使用LRU和MRU。当关系表不能全部载入主存时，缓冲池置换策略是非常关键的。不妨假设我们有M个缓存页，而其中N个已被第一个关系占用，若第二个关系大小为M-N+P，这样，除了P个页外，第二个关系的所有页都能被读入缓冲池。由于我们必须多次扫描第二个关系，这时，若使用LRU,每当我们重新需要某个页时，这个页因为很长时间没有使用，可能早已被替换移出了，因此，可能每个页都需要重新读磁盘。而若是采用MRU――总先替换最近用过的页，长时间未用的那些老页可能一直留在缓冲池，这样第二次扫表内层关系时，开始的哪些 页大都能在缓冲池中找到。每次扫描内层关系（第二关系），可能只需要重复读P-1个页。6.2考虑一个每页10个记录、共有5,000,000条记录的关系R(a,b,c,d)。假设R.a是主码，其值从0～4999,999，且R数据文件基于R.a排序。若对R的元组，有三种可用存取方法：a)直接扫描排序文件R；b)利用R.a上的聚集B+树索引；c)利用R.a上的线性散列索引。试对每个以下关系代数查询：（1）σa<50,000(R)；（2）σa＝50,000(R)；（3）σa≠50,000(R)；（4）σa>50,000∧a<50,010(R)；分别通过定量的代价分析，说明它们赋值的最好存取方法。【解答】（1）对σa<50,000(R)选择，选用直接存取排序文件方式，可能比使用聚集B+树索引代价更小些，因为利用B+树毕竟还要进行B+树本身的额外操作。（2）对σa=50,000(R)选择，线性散列索引应是最好的存取路径。（3）对σa>50,000∧a<50,010(R)B+树应是最便宜的存取路径。（4）对σa≠50,000(R)因为选择需要扫描可用的所有数据项，直接扫描文件应该是代价最小的。6.3考虑一个包含10,000页的关系Executives(ename:string,title:string,dname:string,address:string)，及针对它的查询SELECTDISTINCTE.title,E.enameFROMExecutivesE。如果可用的缓存页数为10，并假设该关系的4个属性等长度，每个页可存储10个元组。同时采用如下的排序投影算法：初始排序阶段读入关系，并创建只包含ename/title属性的排序子表；随后的归并阶段将附带删除重复元组。试回答以下问题：（1）初始排序阶段将产生的子表数，以及每个子表的平均长度。（2）计算排序的I/O代价。为计算最终的投影，还需要多少额外的I/O代价？（3）如果有title上的聚集B+树索引，则该索引是否能为排序提供更便宜的代价？如果索引是非聚集的，或是一个散列索引，则结果又如何？（4）如果有ename上的聚集B+树索引，则该索引是否能为排序提供更便宜的代价？如果索引是非聚集的，或是一个散列索引，则结果又如何？（5）如果有上的聚集B+树索引，则该索引是否能为排序提供更便宜的代价？如果索引是非聚集的，或是一个散列索引，则结果又如何？【解答】（1）B=10,初始阶段将产生5000个排序子表，每个子表长度为10个页；读入10，000个页，投影后写出5000个页，需要总代价=10000＋5000＝15000。（2）为合并1000个子表，我们还需另外3个归并阶段，代价为2*3*5000=30000I/Os（3）可合理假设每页可存储10*4个title属性， B+树至少会有100,000/(10*4)=2500个叶节点。因此，扫描B+树本身至少需要2500I/Os代价。利用title上的聚集B+树索引扫描关系的代价为12500（超过简单堆文件扫描的10000次）。利用title上的非聚集索引扫描的代价更高，可能会超过2500＋100000,达到2500＋100000*10次（假定每页元组数10)。如果散列索引是聚集的且散列桶中直接存储元组，则使用散列索引检索并完成排序代价可能会很好。（1）利用ename上的聚集B+树索引，扫描代价为12500。因为ename为主码，扫描B+树检索出的对不会有重复，不需要在进行排序消除重复，因此，产生查询结果的总估计代价也是12500,代价远远低于简单排序归并的(15000+30000)次I/Os。但非聚集B+树检索所有目标元组的代价可能达到：1500＋10000*10=102500。（2）如果有的B+树索引，不论索引是否聚集的，产生消除重复结果都只需要2500次I/Os（因为只需要扫描索引，不需要扫描数据文件，且是超键，不会有重复）。6.4考虑连接R⋈R.a=S.bS，已知：l关系R有10,000个元组,每页可存10个元组，其数据文件为简单堆文件；l关系S有2,000个元组，每页可存10个元组，b是它的主键，其数据文件为简单堆文件；l有52个可用缓存页。试回答以下问题：（1）分别计算采用简单嵌套循环连接、页嵌套循环连接和块嵌套循环连接算法时的代价，实现相应算法需要的最小缓存页数分别是多少？（2）若采用排序-归并连接算法，则其代价和需要的最小缓存页数分别是多少？（3）若采用散列连接算法，则其代价和需要的最小缓存页数分别是多少？（4）估计连接结果的最大元组数，以及存储它们需要的页数。（5）如果R.a是引用S.b的外键，估计连接结果的最大元组数，以及存储它们需要的页数。【解答】令关系R和S的总页数分别为M、N，可用缓存页数为B，由题中已知条件，有：M=1000、N=200、B=52。（1）简单嵌套循环连接算法，总代价＝N+(N*PR)*M=200+(200*10)*1000=2000200需要的最小缓存页数＝3。页嵌套循环连接算法，总代价=N+(N*M)=200200，需最小缓存页数＝3。块嵌入循环连接，一次可读入外存关系的B-2个页，只需扫描内层关系⌈200/50⌉＝4总代价=N+M*⌈200/50⌉=200＋1000×4＝4200，需要的最少主存数＝52。（2）若B>（M）1/2>（N）1/2，我们可以使用改进的排序-归并算法：排序阶段划分R为20个子表（每个子表50个页），划分S为4个子表，每个近似50页。这24个子表可一次完成归并。另外，需留下一个缓存页作为输出。总代价＝(M+N)*3=3600;最少需要的缓存页数是25。 注意，如果S.b不是一个键，则在最坏情况下，排序-归并算法的归并阶段可能需要探测整个关系，这会导致在归并阶段产生M*N次I/O。（3）若B>(f*N)1/2，f主存散列因子，则散列连接算法的总代价＝(M+N)*3=3600若假设f=1.2，最少需要的缓存页数＝(1.2*500)1/2＝=＝25（1）因为S.b是主键，R中的任一个元组最多只能匹配S中的一个元组，因此，结果中的最大元组数等于R的元组数，即10000。结果关系的每个元组大小＝(R的元组大小)+(S的元组大小)－(连接属性大小)。因此，每个页可能只允许存储5个结果元组，存储所有结果可能需要2000个页。6.5针对习题6.4的已知信息，（1）如果存在R.a和S.b上的非聚集B＋树，与块嵌入连接/排序归并连接/散列连接相比，分别以不同关系作为内层的、基于索引的循环连接算法能提供更好的赋值实现吗？（2）对只有5个和15个缓存页两个情况，以上结果又如何？【解答】假设存取关于R和S的一个B+树叶节点，分别需要3次和2次I/Os。由于S.b是一个主码，我们可假设S中每个元组匹配R中的5个元组。索引嵌套循环连接包括为外层关系的每个元组分别探求内层关系的一次索引。探求的代价＝（存取一次叶节点的代价）＋（检索所有匹配元组的代价）。（1）在非聚集索引情况下，检索每个数据记录的代价可能会需要1次I/O。若以R为外层关系，则索引嵌套循环连接算法的总代价＝<读R>+10000次探求S索引的代价＝1000+10000*(2+1)=31000若以S为外层关系，则索引嵌套循环连接算法的总代价＝<读S>+2000次探求R索引的代价＝200+2000*(3+5)=16200无论哪种安排，其代价都比B=52时的块嵌套循环连接需要的4200次I/Os要更高。B=52>25排序-归并与散列连接的总代价都是(M+N)*3=3600（2）当B=15、5时，索引嵌套循环连接算法的总代价不变。但块嵌套循环连接代价会因B而变化，B=52,块嵌套循环连接代价＝4200B=15,块嵌套循环连接总代价=N+M*⌈200/13⌉=16200B=5,块嵌套循环连接总代价=N+M*⌈200/3⌉=67200――――――――――――――――――――――――――B=15可排序R用三个阶段，代价为2*3*M=6000;排序S用两个阶段,代价为2*2*N=800；归并已排序的R和S，代价M+N=1200;这时排序归并的总代价＝6000＋800＋1200＝8000。B=15散列连接，首先扫描较小关系S，划分为14个子桶，每个桶大小大约15个页。因为f*15已超过可用缓存页数，我们须再次应用散列连接算法到首次散列划分所创建的每对R、S的子桶对。总的代价＝两个划分阶段代价＋1次匹配阶段＝2*(2*(M+N))+(M+N)=6,000 而当，B=5时排序－归并和散列归并连接性能将变为非常差。计算略。☆如果在R.a和S.b上有聚集B+树索引，则存取每10个记录可能1次I/O就能完成，若以R为外层关系，则索引嵌套循环连接算法的总代价＝<读R>+10000次探求S索引的代价＝1000+10000*(2+1)=31000若以S为外层关系，则索引嵌套循环连接算法的总代价＝<读S>+2000次探求R索引的代价＝200+2000*(3+1)=8200无论哪种安排，其代价仍然比块嵌套循环连接需要的4200次I/Os高。☆如果S只有10个元组，则我们需要改变一些我们初始的假设。现在我们可假设S的所有元组都可存储在一个页中，且存取索引叶节点只需要1次I/O，每个S元组可能匹配1000个R元组，这时，以R为外层关系的索引嵌套循环连接总代价＝1,000+10,000∗(1+1)=21,000以S为外层关系的索引嵌套循环连接总代价＝1+10∗(3+100)=1031而块嵌入循环连接总代价=N+M*⌈N/(B-2)⌉=1+1000*1=1001，仍是代价最低方案。6.6考虑查询：select*fromempwheredeptno=10。假设当emp数据表比较大时，等值匹配条件deptno=10能查询出表中大部分的数据(约50%)。如该表共有4,000万行数据，数据表总大小约4GB，存放在500,000个数据页中（每个数据页为8k，每页可存放80个元组）。（1）如果采用组块方式进行全表扫描（令系统组块参数db_file_multiblock_read_count为200），则扫描共需要多少次组块I/O？（注：现代系统中，1次组块I/0时间已可接近单页I/O时间）（2）假设deptno列上的索引都已经cache到内存中，访问索引的开销可忽略不计。如果采用索引扫描，要读出4,000万行的一半，即约2,000万个元组，分别就索引聚集和非聚集两种情况，估算需要的I/O次数。（3）从以上计算，我们等得出什么结论。（提示：索引扫描未必总是优于全表扫描。用全表扫描的时间是固定的；而用索引扫描时，随着选出数据的增多查询时间会相应延长）【解答】（1）如果采用组块方式进行全表扫描，则需要的I/O次数：＝500000/db_file_multiblock_read_count=500000/200=2500次I/Os。（2）如果采用索引扫描，因假设deptno列上的索引都已经cache到内存中，可以忽略访问索引的开销。若要读出4000万行数据的50%，即2000万数据，即使我们假设在读这2000万数据时，有99.9%的命中率，则还是需要读取:2000,0000*0.0001=20000次I/OS,比(1)的全表扫描2500次多得多，也即在这种情况下，用索引扫描反而性能会差很多。（3）索引扫描未必总是优于全表扫描。用全表扫描的时间是固定的；而用索引扫描时，随着选出数据的增多查询时间会相应延长。 6.7假设在某DB环境“oracle8.1.7+linux+磁盘阵列柜”下，有一个包含明细数据的关系表S_DETAIL，在该表的主码id列上有聚集索引，另一个名为cn的列上也有索引。l现执行selectcount(id)fromS_DETAIL，发现该表包含有3200多万数据。查看计划执行细节时，发现系统使用了全表扫描，执行共花了大约1.50分钟。l再尝试执行selectcount(id)fromS_DETAILwherecn<"6"；却用了2个多小时。经分析发现系统执行这个语句时，先使用了cn列上的索引，然后利用查询得到的rowid再从表中查询数据。试分析以上原因（提示：可参考习题6.6）。【解答】Oracle8.1.7版本内部，还在同时使用基于规则优化器(RuleBasedOptimization,RBO)，以及基于代价的优化器(CostBasedOptimization,CBO)。本例情况说明，Oracle执行时启用的是RBO：执行selectcount(id)fromS_DETAIL时，选用全表扫描；而执行selectcount(id)fromS_DETAILwherecn<"6"时，因为找到可用索引S_DETAIL:cn，自动启用了索引扫描方式。由于cn非主码，S_DETAIL:cn上的索引很可能是非聚集索引。根据6.6题计算结果看，当数据量特别大是，索引扫描性能往往很差，加上非聚集索引因素，目标元组在主存的命中率往往不高。因此，这种情况下，执行需要两个小时多的长时间也就不足为奇了。 第7章查询处理与优化7.1简要回答以下问题。（1）简要描述查询处理的基本过程。（2）什么是查询语法树？试给出一个具体查询的语法树表示示例。（3）说明查询赋值逻辑计划与物理计划的区别。试给出：在图7.3（a）基础上，附加标注每个节点赋值方法、主存需求以及节点之间数据传递方法的更详细计划。（4）描述SQL查询基本块的概念，并说明将查询块转换为代数表达式树的基本过程。（5）请举一个反例，说明流水线方式未必总是最有效方法。（6）分别给出“下推选择有很好效果，及下推选择效果反而不好”的两个查询赋值例子。（7）解释说明许多典型优化器只选择左深树的原因。（8）如果在R.a和S.b上分别有稠密非聚集的非主码B+树索引。（a）若R、S数据文件的每个页恰好为1个元组，那么，利用这两索引执行R⋈R.a=S.bS排序归并连接是否为最有效赋值方法？（b）若R、S数据文件的每个页有多个元组，情况又当如何？【解答】（1）查询首先被解析(预编译)，如果能通过，将产生合法的语法分析树。通过初步查询计划生成器，可将语法分析树转换为初步的逻辑查询计划树（即关系代数表达式树）。初步逻辑查询计划通过查询优化处理，产生一个有效的、并添加了有关操作实现细节说明的‘最优’查询计划――查询赋值计划树。（2）查询语法树，指的是SQL查询表达经过查询预编译处理后产生的、类似编译语言语法树的树形表达形式。这种树形表达有助于我们更准确地观察查询语句的语法结构，也更适合机器自动分析处理。查询语法树的节点可以是以下两者之一：l原子类：属词法成份，相当于程序语言编译器的token，如关键字(SELECT/FROM/WHERE…)、关系或属性的名、常数、括号、运算符等。原子节点没有子节点。l语法类：在查询表达中起相似作用的查询子成份族名称。通常用角括号将描述名括起来表示。语法类子节点通常有子节点，并通过语法规则(产生式)进行描述。关于语法树表示示例，可参见书本p225图7.2。（3）逻辑查询计划：指由查询处理器通过将查询语法树中的节点和结构，按一定的替换规则分别替换为关系代数操作符后，所生成的代数表达式树。通常依据一定规则直接替换生成的代数表达式树，只是一种初步的逻辑查询计划，还需经过进一步的优化重写，才能得到比较合理的逻辑查询计划。物理查询计划：通常指由最终版本逻辑查询的计划，通过附加补充具体实现和执行细节说明，而得到的实际查询赋值执行计划。（4）基本块是一个简单的成份：有且只有1个SELECT和FROM关键字、最多一个WHERE子句、最多一个GROUPBY/HAVING子句；且WHERE子句的条件表达式具有合取规范形式。将查询块转换为代数表达式树的基本过程为：用一个关系代数表达式来替换一个查询块，其中，关系代数表达式自下而上由以下内容组成：u中提到的全部关系叉积，作为下级选择操作符选择sc的参数； u选择sc，其中，C是>结构成份中的条件表达式（整个选择作为下级投影操作符的参数）；u投影pL，其中，L是中的属性。附加处理其它扩展查询代数操作符（GROUPBY、HAVING）等，如有的话。（1）流水线方式允许我们避免创建和读取临时关系文件，能节省大量的磁盘I/O操作。从而有益于减少查询赋值代价。但这只是一个启发式定律。有时当物化代价不大且物化方式有助于利用某些其它特性――如索引聚集特性――时，或当主存严重不足而勉强使用流水线方式时，采用流水化方式代价可能反而会更大。举例：书本图7.6的查询赋值计划，若将连接左节点的输入数据：先物化并按sid字段排序，则计划赋值执行的总代价将会更低。（2）赋值查询时，连接是一个相对昂贵的操作。通过下推选择到连接之前，往往可以减小参与连接的关系大小，从而提高整个查询赋值的性能。但这仅是一个启发式定律，也存在一些情况，比如，选择没有索引可用，或先做选择可能导致原关系索引不可用等情况，下推选择策略也有可能反而会影响赋值效果。l“下推选择有很好效果”的例子，可参见书本P231-231，以及图7.5。l“下推选择反而影响效果”的例子，可参见书本P233-234，以及图7.6。（3）许多典型优化器只选择左深树的原因：l随着连接数目的增加，可选的计划数目急剧增加，从候选计划空间中剪枝变为非常关键和重要。l左深树内层节点总是基关系，允许我们产生所有完全流水化方式的计划，即所有连接都允许利用流水线方式赋值，在开始连接之前，不需要等待第二关系。（4）（a）当R和S的每个页都是只含1个元组时，利用索引是一个很好的赋值方案。因为每个数据页最多被读1次，扫描B+树检索数据的代价可能很小。（b）当R和S的每个页都有很多元组时，如果索引是非聚集的（没有排序数据文件可用），则单个数据页可能会被多次读取。而若将数据文件按索引键排序后（即索引为聚集索引），则每个匹配的数据页通常只需被读1次。7.2考虑关系模式：Employee(eid:integer,ename:string,sal:integer,title:string,age:integer)。假设有如下的索引（索引项均为键/指针对）：eid上的散列索引/age上的散列索引/sal上的B+树索引/上的聚集B+树索引。已知：关系总页数10,000，每个元组100字节；每个索引项20字节。（1）对如下的每个选择条件，若每当一个条件项有匹配索引时减小因子是0.1，计算检索满足条件元组的最有选择性存取路径代价。(a)sal>100；(b)age=25；(c)age>=20；(d)eid=1,000；(e)sal>200∧age>30；(f)sal>200∧age=20；(g)sal>200∧title=’CFO’；(h)sal>200∧age>30∧title=’CFO’（2）试针对上述各条件，描述计算“将满足条件元组按年龄分组的平均工资”的最便宜赋值方法，并估算总代价。（3）对如下两个选择条件：（i）sal>200∨age=20;（j）sal>200∨title=’CFO’ ，描述其最便宜赋值方法。【解答】（1）若假设每个数据页包含20个元组，则关系元组总数＝10000页×(20元组/页)＝200,000；因索引项为20字节，元组大小为100字节，故B+树的叶节点总数=10,000×20/100＝2,000。对于非聚集索引，根据每个满足条件指针检索对应元组，可能都要读取一个页。注意，对组合键索引项大小取40字节，叶节点总数=4000.（a）对于sal>100，减少因子按0.1估算，这时，利用非聚集索扫描的代价:=(B+树索引扫描代价)+(按指针检索满足条件的元组代价)=2+2,000×0.1+200,000*0.1=20202，这比文件扫描的10000代价大得多。对于选择sal>100，因为sal上不存在聚集索引，文件扫描或许是最好的。（b）对age=25，聚集B+树索引应是最好的选项，其代价：＝B+树搜索的2次＋B+树叶节点数*0.1＋10000页*0.1（选择性）＝2＋4000*0.1+10,000*0.1=1402利用（非聚集）散列索引是次好的选项，其代价：＝元组总数*0.1//每个元组读1个页＝200,000*0.1=20,000//若索引是聚集的，则代价可大幅降低（c）对age>20，聚集B+树索引应是最好的选项，其代价为1402：（d）对eid=1000，因为eid是候选键，可以假设每个桶中只有1个元组。这样，总的代价≈2.2（2或3）。（e）对sal>200∧age>30，利用上的聚集B+树索引检索代价最小，代价大小:1402。（f）对sal>200∧age=20，利用上的聚集B+树索引检索代价最小，但若以0.1*0.1作为减小因子，则代价只有：＝B+树搜索的2次＋B+树叶节总数*0.1*0.1＋10000页*0.1*0.1＝2＋4000*0.1*0.1+10,000*0.1*0.1=142（g）对sal>200∧title=”CFO”，文件扫描代价最小：10000。（h）对sal>200∧age>30∧title=”CFO”先利用上的聚集B+树索引检索满足sal>200∧age>30的元组，再对检索到元组检查title=”CFO”条件，进行过滤。代价：1402次I/Os。（2）（a）对于sal>100，因为结果只需要平均工资，利用sal上的B+树只索引扫描（index-onlyscan）就可实现赋值。减少因子按0.1估算，这时，利用非聚集索扫描的代价:=（定位起始叶节点的2次I/O）+(扫描满足条件的B+树索引叶节点)=2＋2,000×0.1＝202（b）对age=25，聚集B+树索引应是最好的选项，其代价：=（定位起始叶节点的2次I/O）+(扫描满足条件的B+树索引叶节点) =2＋4,000×0.1＝402次I/Os（a）对age>20，同（b），代价也是402次I/Os（b）对eid=1000，同（1）（d），总的代价≈2.2（2或3）。（c）对sal>200∧age>30，利用上的聚集B+树索引检索代价最小，代价大小:402。（d）对sal>200∧age=20，利用上的聚集B+树索引检索代价最小，但若以0.1*0.1作为减小因子，则代价只有：＝B+树搜索的2次＋B+树叶节总数*0.1*0.1＝2＋4000*0.1*0.1=42（e）对sal>200∧title=”CFO”，文件扫描代价最小：10000。（f）对sal>200∧age>30∧title=”CFO”先利用上的聚集B+树索引检索满足sal>200∧age>30的元组，再对检索到元组检查title=”CFO”条件，进行过滤。代价：1402次I/Os。（1）（g）对于sal>200∨age=20，该情况（即使是对单个条件sal>200）下，文件扫描应是最便宜的赋值方法。（h）对sal>200∨title=”CFO”，同样，文件扫描也是最好的赋值方法。7.3考虑关系模式Executives(ename,title,dname,address{假定这些属性均为字串且等长})，关系实例包含10,000个页，可用缓存页数为10。（1）对于查询SELECTE.title,E.enameFROMExecutivesEWHEREE.title=’EFO’，假设有10%的元组满足选择条件。（a）假定title上有B+树索引，试针对索引是聚集/非聚集两种情况，说明最好计划的代价；（b）假定ename上有聚集B+树索引，试说明最好计划的代价；（c）假定上有聚集B+树索引，试说明最好计划的代价。（2）对于查询SELECTE.enameFROMExecutivesEWHEREE.title=’EFO’andE.dname=’Toy’，假设有10%的元组满足条件E.title=’EFO’、有5%的元组满足条件E.dname=’Toy’。（a）假定只有title上的聚集B+树索引可用，试说明最好计划的代价；（b）假定只有dname上的聚集B+树索引可用，试说明最好计划的代价；（c）假定同时有title、dname上的聚集B+树索引可用，试说明最好计划的代价；（d）假定只有上的聚集B+树索引可用，试说明最好计划的代价；（e）假定只有上的聚集B+树索引可用，试说明最好计划的代价；（f）假定只有上的聚集B+树索引可用,试说明最好计划代价;（g）假定只有上的聚集B+树索引可用,试说明最好计划代价.（3）对于查询SELECTE.titleFROMExecutivesEWHEREE.dname>’W%’GROUPBY E.title，假设有10%的元组满足选择条件。（a）假定只有title上的聚集B+树索引可用，试说明最好计划的代价；（b）假定只有dname上的聚集B+树索引可用，试说明最好计划的代价；（c）假定只有上的聚集B+树索引可用，试说明最好计划的代价；（d）假定只有上的聚集B+树索引可用，试说明最好计划的代价。【解答】假设单字段搜索键的索引项大小＝元组大小*0.25，B+树索引叶节点总数＝10000/4=2500；双字段组合键索引项大小=元组大小*0.5，B+树索引叶节点总数＝5000。（1）①利用title上的非聚集B+树索引，代价:=2+2500*0.1+（元组总数）*0.1最好计划是文件扫描，代价：10,000次I/Os若有title上的聚集B+树索引可用，使用它应是最好计划，代价=2+2500*0.1+（数据文件总页数）*0.1＝2+250+1000=1252②这时索引不匹配选择条件，基本没有什么作用，最好计划是文件扫描，代价＝10,000I/Os③虽然索引不匹配选择条件，但仍可用只扫描索引来实现赋值，这时需要扫描所有的页节点。代价＝组合键B+树索引叶节点总数＝5000.（2）①若使用title上的聚集B+树索引，代价:=2+页节点数*0.1+（数据页数）*0.1*0.05＝2＋2500*0.1+10,000*0.1=1252次I/Os这个代价比文件扫描低，是最好计划。②情况类似①③题目有错（不可能同时有两个聚集索引）。④若上的聚集B+树索引可用，这时，由于有较大的选择性，使用该索引应是最好的计划，代价＝2＋5000*0.05+10,000*0.05=752次I/Os。⑤若上的聚集B+树索引可用，这时，虽然索引包含了输出字段，但仍需要检索实际元组以检查关于dname条件。故代价＝2＋5000*0.1+10,000*0.1=1502次I/Os。⑥若上的聚集B+树索引可用，这时，基于该索引的只索引扫描应是最好计划，代价＝2＋7500*0.05（可能更小）=402次I/Os。⑦若上的聚集B+树索引可用，虽然索引不匹配选择条件，但可用只索引扫描，基于该索引的只索引扫描应是最好计划，代价＝2＋7500=7502次I/Os。这个代价比文件扫描低些。（3）① 若使用title上的聚集B+树索引，因索引不匹配选择条件，对给定查询赋值的代价=代价为10000I/Os。最便宜计划代价应包括简单排序选择后结果文件，总代价:＝10,000+2*2*(10000/4)=20000.①这时，索引可匹配选择条件，最好计划应是先用该索引扫描选择，再对选择结果进行排序分组。相应代价大小:=2+2500*0.1+10,000*0.1+3*250=2250.②这时，最好计划应是先用该索引只索引扫描，再对选择结果进行排序分组。相应代价大小:=2+5000+3*250=12502.③这时，索引可匹配选择条件，最好计划应是先用该索引只索引扫描，再对选择结果进行排序分组。相应代价大小:=2+5000*0.1+3*250=1252.7.4考虑针对关系R(A,B,…)和S(C,D,…)的连接查询πA,B,C,D(R⋈R.A=S.CS)。假设基于排序实现带删除重复的投影，且有足够智能在排序的初始阶段就删除所有不用的属性，并在排序后通过流水线删除重复元组。已知：l页大小为1K。lR共有10个页，每个元组为300B(字节)；S共有100个页，每个元组为500字节；lS中的每个元组都能在R中找到匹配连接元组；l属性A,B,C,D总大小为450字节，其中，属性A与B的合计大小为200字节。（1）估算最后输出结果的大小。（2）假定只有基于页的嵌套循环连接可用，分别针对有3个及11个可用的缓存页情况，计算以下赋值方案的总代价：①“先投影后连接”；②“先连接后投影”；③“先连接后投影，且连接结果通过流水线传递给投影”。（3）假定只有基于块的嵌套循环连接可用，重新计算（2）中的各种情况。【解答】（1）从已知信息，R有30个元组，每页可存储3个R的元组；S有200个元组，每页可存储2个S元组。由于每个S元组恰好与R的一个元组连接，连接产生的元组总数等于S的元组数（200）、连接投影后的元组大小等于450，因此，最后输出的结果大小＝200×450＝90,000字节，约100个页。（2）①先投影后连接：根据题意，采用基于排序的删除重复投影算法，我们必须先排序作为连接内层的关系S(含C,D两个字段，共有100个页)，1）若只有3个缓存页，排序删除重复投影S的代价为2*100*log2 100=1400。假设删除重复可减少1/10元组，即可剩下180个元组，每个元组大小250字节，每页可存储4个元组。排序投影后的S关系大小为50页。针对R的排序删除重复投影做法类似，R（含A,B两字段，共有10个页，30个元组），排序代价为3*10*log210＝120（R作为外层，最后1次写出可以不算）。假设删除重复后只剩9/10的元组，即27个元组（每个元组大小200字节），1个页存储5个元组，总共有6个页。采用基于页的嵌套循环连接算法的代价＝6＋6×50＝306；执行该查询赋值计划的总代价＝1400＋120＋306＝1826次I/Os2）若只有11个缓存页，排序删除重复投影S的代价为2*100*log10100=400。……。针对R的排序删除重复投影做法类似，R（含A,B两字段，共有10个页，30个元组），排序代价为3*10*log1010＝30……。采用基于页的嵌套循环连接算法的代价＝6＋6×50＝306；执行该查询赋值计划的总代价＝400＋30＋306＝736次I/Os②先连接后投影，基于页嵌套循环连接算法的代价＝10+10*100=1010I/Os，结果关系的元组数为200，每个元组大小300＋500＝800字节，共有200个页。1）若只用3个缓存页，来排序删除重复结果关系。第一个阶段直接投影掉不用字段，产生只有450字节元组，2个元组/每页。这样，该阶段读入为200页，写出为100页（分33个子表、每个子表大小为1页）。这些子表需要另外进行log233=6个归并阶段。因此，排序删除投影的总代价＝200＋2×6×100＝1400，加上连接时的1010次I/Os，赋值的总代价为2410次I/Os2）若有3个缓存页，来排序删除重复结果关系。第一个阶段直接投影掉不用字段，产生只有450字节元组，2个元组/每页。这样，该阶段读入为200页，写出为100页（分10个子表、每个子表大小为11页）。这些子表需要另外进行log210=4个归并阶段。因此，排序删除投影的总代价＝200＋2×4×100＝1000，加上连接时的1010次I/Os，赋值的总代价为2010次I/Os③“先连接后投影，且连接结果通过流水线传递给投影”。这意味着可不计算排序删除重复投影的代价，赋值的总代价只有1010次I/Os。7.5考虑如下关系模式：Emp(eid:integer,sal:integer,age:real,did:integer);Dept(did:integer,projid:integer,budget:real,status:char(10));Proj(projid:integer,code:integer,report:varchar);已知：Emp元组总数20,000，每个元组20字节；Dept元组总数5,000，每个元组40字节，每个did值平均约对应有10%的元组；Proj元组总数1,000，其元组平均长度为2,000字节。另假定文件系统支持的页大小为4000字节，有10个可用的缓存页；另外，如果你认为必要，还可自己增设一些其它额外假定。（1）假定部门budgets值均匀分布在0～100,000范围，考虑如下查询：SELECTD.did,COUNT(*)FROMDeptD,ProjPWHERED.projid=P.projidANDD.budget>99,000GROUPBYD.did ①如果没有索引可用时，给出具有最小估计代价的计划。②如果有P.projid上的散列索引，给出具有最小估计代价的计划。③如果有D.budget上的散列索引，给出具有最小估计代价的计划。④如果有D.budget和D.projid上的散列索引，给出具有最小估计代价的计划。⑤如果有P.projid上的散列索引和上的聚集B+树索引可用，给出具有最小估计代价的计划。⑥如果有D.budget上的聚集B+树、D.projid上的散列索引和P.projid上的散列索引，给出具有最小估计代价的计划。（1）假定部门budgets值均匀分布在0～100,000范围，考虑如下查询：SELECTE.eid,D.did,P.projidFROMEmpE,DeptD,ProjPWHEREE.eid=D.didANDD.projid=P.projidANDD.budget>20,000ANDE.sal=50,000①列出本查询优化中，有含1个关系、2个关系和3个关系的子计划。②给出本查询的最优赋值方案及其估计代价。【解答】（1）①具有最小估计代价的计划：采用以Proj为外层的块循环嵌套连接，然后通过流水线给选择操作符σbudget>20,000，再对选择输出结果进行基于did上排序以实现聚合操作，连接输出只需保留did字段（其它所有属性都可删除掉），但要保留重复元组。②有Proj.projid上的散列索引的具有最小估计代价计划：首先，对Dept执行选择σbudget>20,000，并投影掉除了did、projid之外的所有其它属性，结果流水线方式传送给排序操作符，进行基于did的排序。对排序输出的每个元组，流水线方式，传递给索引连接操作符，用当前元组的did值探测Proj，更新每个did分组的计数。③有Dept.budget上的散列索引时的具有最小估计代价计划：利用budget上的索引，扫描Dept，并投影掉除了did、projid之外的所有其它属性，结果流水线方式传送给基于索引的嵌套连接操作符；最后，采用基于排序方法，完成聚合赋值。（假设有Proj.projid上的散列索引，如没有可临时键，但要计算代价）。④同②，索引Dept.projid没有作用，Proj.projid有用。⑤这种情况下的具有最小估计代价计划：按did顺序检索聚集B+树，检索满足条件的Dept元组，并将检索到的、只保留did,projid两字段的每个Dept元组，流水线方式传送给以Proj为内层的、基于索引的嵌套循环连接操作符，用当前元组的did值探测Proj，更新每个did分组的计数。⑥尽管Dept.budget非聚集索引，但因budget条件具有很强选择性，因此，这种情况下的具有最小估计代价计划应是：先通过Dept.budget索引，检索满足条件的Dept元组，并将检索到的、只保留did,projid两字段的每个Dept元组，流水线方式传送给以Proj为内层的、基于索引的嵌套循环连接操作符，用当前元组的did值探测Proj，更新每个did分组的计数。（2）①含1个关系的子计划：E.sal上的聚集索引;文件扫描Dept;文件扫描Proj。 含2个关系的子计划：1）以E.sal上的聚集索引扫描为左关系；用did上的索引探测Dept,并应用budget选择过滤Dept元组。2）应用budget选择条件，扫描Dept作为左关系，探测Proj。3）扫描Proj作为左关系；探测连接Dept（下推选择σbudget>20,000）；含3个关系的子计划：1）先连接Emp和Dept，探测Proj；2）先连接Dept和Proj，探测emp。②最优方案是：利用E.sal上的索引删除大部分元组，基于D.did探测Dept，并同时处理σbudget>20,000；结果元组再流水线方式传送给下级基于Proj.projid的索引连接。具体代价估计略。 第8章事务并发控制8.1简要回答以下问题。（1）说明事务的概念及事务的四个基本特性。（2）辨析串行调度、可串行调度、冲突可串行调度、可恢复调度、视可串行调度和严格调度概念。（3）①一个优先图无环的调度，肯定是冲突可串行化调度吗？为什么？②遵循2PL协议的调度，其优先图肯定是无环的吗？为什么？（4）比较strict-2PL、2PL和Conservative-2PL协议，它们作用效果差别主要体现在哪？（5）在基于封锁的调度系统中，如果系统采用strict-2PL协议调度，还会发生死锁吗？如果采用Conservative-2PL协议调度，情况又当如何？（6）简要分析比较基于等待-死亡、伤害-等待策略的死锁预防方法，以及基于等待图的死锁检测方法的优缺点。（7）什么是幻影问题？试给出两种处理幻影问题的策略。（8）简要描述树协议规则。【解答】（1）在DBMS中，事务通常指必须被原子化执行的一个DB操作动作序列，序列中的动作可能来自1条SQL语句，也可能是来自多条SQL语句组合。任何事务都具有原子性、一致性、孤立性和持久性等四个基本特性，即所谓的ACID特性。（2）²串行调度:指来自不同事务的动作没有交替的调度。²可串行调度:若调度S执行对DB造成的影响，与某个包含同组事务的串行调度相同，称调度S是可串行化的。²冲突可串行化调度：指在冲突语义上，与一个串行调度等价的调度。²视可串行调度:不满足冲突可串行化的可串行化调度。²可恢复调度:对调度中的任意事务T，如果读取了某个元素集{X}，则T必须等到调度中修改了元素集{X}的所有其它事务提交之后才能提交。²严格调度:对调度中的任意事务T，要求T所写的值，在T提交或中止之前，不会被S中其它事务读或重写。²‘可避免级联中止avoids-cascading-aborts’:事务只读已提交数据（无脏读）。这种事务不仅是可恢复的，且中止该事务不会级联中止其它事务。（3）① 一个优先图无环的调度，肯定是冲突可串行化调度。因为当优先图无环时，我们总可以通过相邻动作的合法交换（即冲突等价交换）来改变调度中动作的顺序，直到将原调度转换成一个串行调度。②遵循2PL协议的调度，其优先图不一定是无环的。因为将请求锁和释放锁分开为两个阶段，并不限制不同事务动作交替顺序。实际上，优先图无环是一个比2PL更严格的限定。（1）比较strict-2PL、2PL和Conservative-2PL协议，它们作用效果差别主要体现在哪？（1）严格-2PL是一种最广泛使用的封锁协议，它要求1)事务在读/修改DB元素之前，必须获得该元素的锁（共享或排它）；2）所有的锁在事务结束时才释放。（2）2PL也称一般2PL，它也是一种广泛使用的封锁协议，但它的限制比严格-2PL弱些，其差别主要表现在释放锁时间不同，一般2PL只要在最后一个请求锁申请完成后，就可以开始释放锁，或者说，事务一旦开始释放所拥有的第一个锁后，就不允许再申请锁。事务的被分为锁申请和锁释放两个阶段。（3）Conservative-2PL协议，则要求事务必须在获得所有需要持有的DB元素锁以后，才能开始执行读写DB元素操作。保守2PL执行之前可能需要多等待一段时间，但一旦开始执行，就不会被中止（除非自身原因）。在竞争很激烈的环境中，保守2PL可能效果反而会很好，而且可避免死锁发生。（2）在基于封锁的调度系统中，如果系统采用strict-2PL协议调度，仍有可能会发生死锁，因为该协议并不能满足预防死锁发生的条件。但如果采用Conservative-2PL协议调度，则可避免发生死锁，因为它要求获得所有需要的资源后才执行，这相当于破坏了请求和保持这个条件，因此，不会发生死锁。（3）略。参见书本8.3节。（4）幻影问题指的是：当事务存取某个DB元素集两次，会得到不同的结果，即使它遵守2PL协议，而且自己也没有该DB元素集做任何修改。这个问题通常源自一个动态数据库执行环境，在这里，事务无法封锁给定类型的所有对象（即使已封锁了目前已有的所有某类型元素，但可能还会有新插入该类元素的情况发生）。避免该问题的基本方法是采用更严格的封锁，比如，采用表封锁或谓词封锁，而不是简单的记录集封锁。（5）略。参见书本P271,8.4.2节。8.2考虑下面的（不完全）调度S：R1(X),R1(Y),W1(X),R2(Y),W3(Y),W1(X),R2(Y)（1）假定三个事务最终都正常提交，请画出它们的优先图。S是否为可串行化调度？如是，请进一步给出与它等价的串行调度。（2）分别根据以下所指定的每个条件，修改S为一个完全调度。如果修改不可能，则给出简要的解释说明；如果可能，则通过添加最少的动作数（动作可以是read,write,commit,abort等，且它们允许被插入到原S的任何位置），完成对S的修改。①结果调度能避免级联中止，但却是不可恢复的调度； ②结果调度是可恢复调度；③结果调度是冲突可串行化调度。【解答】（1）其优先图如右图所示。因为其优先图有环，所以，调度S不能肯定是可串行化调度。实际上，因R2(Y),W3(Y)不可交换，它也不是一个冲突可串行化调度。但它确实一个(视)可串行化调度，其等价的串行串行调度为:R1(X),R1(Y),W1(X),W1(X),R2(Y),R2(Y),W3(Y)（2）结果调度能避免级联中止，但却是不可恢复的调度。①没有这样的修改，因为调度如果能避免级联中止，那么它一定是可恢复的调度。②通过按如下方式插入提交动作，可将S修改为可恢复调度。R1(X),R1(Y),W1(X),R2(Y),W3(Y),commit(T3),W1(X),R2(Y),commit(T1),commit(T2).③不存在这样的修改。因为无论插入什么动作，R2(Y),W3(Y),...,R2(Y),三个动作的顺序无法修改。8.3针对以下调度，分别说明它们的调度类属。可能的类属包括：可串行化、冲突可串行化、视可串行化、可恢复调度、可避免级联中止调度和严格调度。如果你认为不能确定，请简要说明原因。（1）W1(X),R2(Y),R1(Y),R2(X)（2）R1(X),R2(Y),W3(X),R2(X),R1(Y)（3）R1(X),R1(Y),W1(X),R2(Y),W3(Y),W1(X),R2(Y)（4）R1(X),W2(X),W1(X),COMMIT(T2),COMMIT(T1)（5）R1(X),W2(X),W1(X),ABORT(T2),COMMI(T1)（6）R1(X),W2(X),COMMIT(T2),W1(X),COMMIT(T1),R3(X),COMMIT(T3)（注，如果调度中不包含commit或abort，则相应调度属于不完全调度，abort/commit必须跟在所有动作之后。）【解答】（1）调度:W1(X),R2(Y),R1(Y),R2(X).是可串行化、冲突可串行化、视可串行化调度；但它不满足严格调度；也不是‘可避免级联中止’的调度；且因为未指定abort/commit顺序，也不能确定它是否为可恢复调度。（2）调度:R1(X),R2(Y),W3(X),R2(X),R1(Y).情况同（1）。（3）调度:R1(X),R1(Y),W1(X),R2(Y),W3(Y),W1(X),R2(Y).不是冲突可串行化调度;也不是视可串行化调度，即它不是可串行化调度。另外，它不是严格调度，也不是‘可避免级联中止’调度，也不能确定是否为可恢复调度。（4）调度:R1(X),W2(X),W1(X),COMMIT(T2),COMMIT(T1) .不是冲突可串行化调度，但属于视可串行化调度，也即它是可串行化调度。它不是严格调度，但它是一个可恢复调度，且是‘可避免级联中止’调度。（1）调度：R1(X),W2(X),W1(X),ABORT(T2),COMMI(T1).不是冲突可串行化调度，不是视可串行化调度，即它不是可串行化调度。它不是严格调度，但它是一个可恢复调度，且是‘可避免级联中止’调度。（2）调度：R1(X),W2(X),COMMIT(T2),W1(X),COMMIT(T1),R3(X),COMMIT(T3).非冲突可串行化调度;但属于视可串行化调度，也即它是可串行化调度。它也满足严格调度，且是一个可恢复调度，还是‘可避免级联中止’调度。8.4考虑以下动作序列，假设它们按此顺序依次提交DBMS。S1:R1(X),W2(X),W2(Y),W3(Y),W1(Y),COMMIT(T1),COMMIT(T2),COMMIT(T3)S2:R1(X),W2(Y),W2(X),W3(Y),W1(Y),COMMIT(T1),COMMIT(T2),COMMIT(T3)对每个序列和每个以下并发控制机制，描述相应并发控制机制将如何控制序列。假设事务Ti的时间戳为i。对于封锁并发控制机制，添加相关DB元素的封锁和解锁请求。如果一个事务阻塞，则假设它的所有动作将进入等待队列直至等待条件满足，而DBMS可继续执行其它未阻塞事务的动作。（1）具有死锁检测特性的strict-2PL;（2）保守-2PL；（3）基于确认的优化并发控制；（4）时间戳并发控制；（5）可预防死锁的、带时间戳的strict-2PL。【解答】（1）使用基于等待图死锁检测的strict-2PL。事务允许等待，不会因等待而被中止；除非检测到死锁，而且事务被选中为牺牲事务。对序列S1:T1获得X的共享锁；T2等待X的排它锁；T3获得Y的排它锁；T1等待Y的排它锁；T3结束释放Y的锁；T1被唤醒，获得Y的排它锁；T1执行结束释放X,Y上的锁；T2获得X和Y的排它锁，T2执行完成、提交释放所拥有的所有锁。对序列S2:T1获得X的共享锁；T2获得Y的排它锁，T2等待X的排它锁；T3等待Y的排它锁；T1等待Y的排它锁。这时，发生了死锁：T1等待T2,而T2又等待T1。（2）使用保守-2PL。调度安排很简单：对序列S1和S2都是：T1获得X和Y的锁后，开始执行，完成提交后释放X,Y上的锁；然后是T2获得所有需要锁，执行/完成/提交/释放所有的锁；最后是T3获得所有需要锁，执行/完成/提交/释放所有的锁。（3）基于确认的优化并发控制。调度序列中的每个事务都将执行，从DB读相关元素的值并写到私有空间；它们然后获得一备个时间戳进入确认阶段。事务Ti的时间戳值为i。对调度序列S1/S2：因T1具有最早时间戳，它的确认不会有任何问题。但当T2准备有效确认时，因其写元素集和T1的读元素集有交集，而T1尚未完成，故T2无法通过有效确认，将被中止并在稍后重启。同样，T3也不能通过有效确认。直到T1完成之前，T2可能会被反复中止/重启多次。而T3则要等到T2完成之后重启才能通过有效确认。（4）多版本时间戳控制。对序列S1:T1读X，RTS(X)=1;T2允许写X，因为TS(T2)>RTS(X)。而后，RTS(X)和WTS(X) 被设置为2；因为TS(T3)>RTS(X)，T3也能写X；之后，将RTS(X)和WTS(X)被设置为3。现在T1准备写Y，因为TS(T1);脏页表：;崩溃点的事务表：;;脏页表：;;9.3考虑图9.8（a）的执行日志记录。（1）说明恢复管理器在分析阶段完成的工作（指明分析扫描开始与结束点LSN，并描述该阶段构造的有关表内容）（2）说明Redo阶段完成的工作，指明Redo扫描的开始点和结束点。（3）说明Undo阶段完成的工作，指明Undo扫描的开始点和结束点。【解答】（1）分析阶段从最近的、记录在日志主记录中的begin_checkpoint开始，并向前扫描，直到日志的最后一条记录。在向前扫描期间，它确定以下内容：a)Redo阶段的开始处理点；b)崩溃发生时，缓冲池中的脏页表；c) 崩溃发生时，仍然活跃的（未提交）事务。（以便在undo阶段撤销这些事务已完成动作）在图9.8(a)这个例子中，我们假设首条日志之前，脏页表和事务表都是空的。分析阶段将确定最后有效的begin_checkpoint为LSN00,对应的end_checkpoint为LSN10。事务表记录项；脏页表记录项。分析阶段将扫描直到日志记录LSN70，在扫描期间将完成以下事情：扫描LSN20:添加到事务表；添加到脏页表;扫描LSN30:添加到事务表；添加到脏页表;扫描LSN40:将事务表中T2的状态由’U’改为’C’;扫描LSN50:将事务T2从事务表中删除;扫描LSN60:添加到事务表；但不修改脏页表中P3对应的页！扫描LSN70:将事务表中修改为----------------------------------------------------------------------------最后，事务表中包含两个表项：脏页表中包含两个表项：（1）Redo阶段紧跟着分析阶段，该阶段要重做崩溃发生时对缓冲池中脏页所做的任何修改。本例中，Redo阶段从脏页表中最小的recLSN,即LSN20开始，LSN20修改P5动作，被重做，LSN30修改的P3,需要从磁盘读取该页以检查它的pageLSN，如果pageLSN>=30，则说明在崩溃前该页已被写盘，不需要重做这个修改P3动作，否则，如果pageLSN<30，则说明在崩溃前该页未被写盘，需要重做这个修改P3动作;LSN40,50没有动作;LSN60修改P3,因为LSN60>脏页表中P3页对应的30,要重做这个动作；LSN70没有动作。（2）Undo阶段紧跟着Redo阶段，该阶段负责撤销崩溃发生时仍活跃事务所做的任何修改。本例中，Undo从事务表中最大（后）的那条记录，即LSN70开始处理。开始时，丢失事务集为{70,60}。处理LSN70:根据事务prevLSN字段，增加LSN20到丢失事务集。―――丢失事务集变为：{60,20}处理LSN60:undo对P3的修改，增加CLR记录到日志尾。―――丢失事务集变为：{20}处理LSN20:undo对P5的修改，增加CLR记录到日志尾。―――丢失事务集变为：{null}—处理结束。 9.4考虑图9.8（b）的执行日志记录。（1）在图中增加prevLSN和undonextLSN标示。（2）描述回滚事务T2后执行的动作。（3）给出T2回滚后的日志（包括所有prevLSN和undonextLSN）。【解答】（1）增加了prevLSN和undonextLSN标志的图表如下：LSNprevLSNundonextLSN(与CLR对应的ULR)0010203040506070--00----30205060--00----(非update记录)2050(非update记录)（2）第一步从存储在LSN60中的旧值，恢复P3;第二步从存储在LSN50中的旧值，恢复P5;第三步从存储在LSN20中的旧值，恢复P5;（3）T2回滚后，将会在原有日志记录基础上，添加如下的一些日志记录到日志尾:LSNprevLSNtransIDTypepageIDundonextLSN8070T2CLRP3509080T2CLRP52010090T2CLRP5-110100T2END--图9.8习题9.3与习题9.4用图 9.5考虑图9.9（a）的日志片段。另外，在恢复期间当系统写两条日志记录到稳定存储后，再次发生崩溃。之后，在写另外两条日志记录到稳定存储后，又再次发生崩溃。（1）存储在主日志记录中的LSN值为多少？（2）分别描述在三个ARIES阶段的工作。（3）给出最终恢复完成后包含所有非空prevLSN和undonextLSN的日志记录。（4）如果系统在恢复期间反复发生崩溃，那么，在系统最终成功启动后，可能写入日志的最大记录数是多少（提示：考虑崩溃前的update记录数和其它日志记录数）（5）说明在begin_checkpoint和end_checkpoint记录之间为什么可能有其它日志记录。描述分析阶段如何通过分析这些记录来修改脏页表和事务表内容。（6）考虑图9.9（b），给出end_checkpoint记录的内容。图9.9习题9.5用图【解答】（1）存储在日志主记录中的LSN值为00。它是最后一个有效begin_checkpoint记录编号。（2）ARIES分析阶段工作描述：从LSN00开始向前扫描，遇到LSN20:添加(T1,20,’U’)到T.T.;添加(P1,20)到D.P.T;遇到LSN30:添加(T2,30,’U’)到T.T.;添加(P2,30)到D.P.T;遇到LSN40:添加(T3,40,’U’)到T.T.;添加(P3,40)到D.P.T;遇到LSN50:修改T.T.表中的(T2,30,’U’)为(T2,30,’C’);遇到LSN60:修改T.T.表中的(T3,40,’U’)为(T3,60,’U’);遇到LSN70:删除T.T.表中的(T2,30,’C’)遇到LSN80:修改T.T.表中的(T1,20,’U’)为(T1,80,’U’);添加(P5,80)到D.P.T;遇到LSN90:无动作; 分析阶段最终获得的事务表(T.T.)分析阶段最终获得的脏页表(D.P.T.)(T1,80,’U’)(T3,60,’U’)(P1,20)(P2,30)(P3,40)(P5,80)REDO阶段的工作描述：从脏页表中最小的记录好LSN20开始向前扫描处理，遇到LSN20:从磁盘检索P1，比较pageLSN与LSN20:IfpageLSN