数据库系统实现-全

2011级南航工硕士好心人数据库系统实现习题PAGE15-2.3.4假定我们有一个由10000000个元组构成的大关系，并且按照排序码（唯一地标识记录）的顺序存储。同时假设，关系R存储在一个块的序列中。假定磁盘块是4096字节。这样，我们可以将40个100字节的记录装填到块中，剩余的96字节可以作为某些簿记功能或留着不用。这样，关系占据250000个块。块的位置是已知的，因此对于任何一个i，用一个磁盘I/O来定位和检索R的第i块是可能的。给出一个码值K，通过使用标准的二分法搜索技术，我们能够找到包含该码值的元组。要找到包含码K的元组所需要的最大磁盘I/O数是多少？

答案:Binarysearchrequiresprobingtheblockinthemiddleofthe250,000blocks,thentheoneinthemiddleofthefirstorsecondhalf,andsoon,forlog_2(250,000)=18probes,untilwecannarrowdownthepresenceofthedesiredrecordononeblock.Thus,werequire18diskI/O's.二进制搜索需要探测在250,000块，然后在第一或第二的一半的中间一个中间块，等log_2（250,000）=18探头，直到我们能够缩小所需的存在一个块的纪录。因此，我们需要18磁盘I/O的。2.4.2假设我们使用两台Megatron747磁盘互相作为镜像。然而，我们使第一个磁盘的磁头保持在柱面的靠内的一半，第二个磁盘的磁头保持在柱面靠外的一半，而不是允许从两个磁盘都能读任何的块。假设读请求是对随机的磁道，我们始终不必去写：a）系统能够读块的平均速率是多少？b）这个速率与无任何约束的镜像Megatron747磁盘的平均速率相比如何？c）你预计该系统的缺点是什么？RecallthattheMegatron747hasatransfertime(inmilliseconds)of0.5,andanaveragerotationallatencyof7.8.Iftheaverageseekmoves1/3ofthewayacross4096tracks,theaverageseektimefortheMegatron747is1+.002*(4096/3)=3.7.Thus,theanswertopart(a)isoneblockper0.5+7.8+3.7=12milliseconds,or83blockspersecond,oneachdisk.Thus,thesystemcanread166blockspersecond.Fora``regular''Megatron747,theaveragelatencyis0.5+7.8+6.5=14.8milliseconds.However,ifwehavetwo,mirroreddisks,eachcanbehandlingarequestatthesametime,oronereadper7.4milliseconds.Thatgivesus135blockspersecondastheanswerto(b).Forpart(c),restrictingeachdisktohalfthetracksmeansthatifthereisnotalwaysaqueueofwaitingrequests(whichslowstheapplicationsthatthediskissupporting),thentheremightbetworequestsforthesamehalfofthedisk,inwhichcaseonediskisidleandarequestwaits由于Megatron747磁盘有一个转换时间是0.5毫秒,并且一个平均转动延迟是7.8毫秒。如果需要搜寻4096道的三分之一，平均所需要的时间是1(1ms启动磁头)+0.002(移动每个磁道时间)*（4096/3）=3.7毫秒。所以，第一个问题的答案是每个磁盘每块12毫秒（0.5+7.8+3.7=12）或者每秒83块。因此，系统每秒可以读到83*2(两个磁头)=166个块。有“约束的”Megatron747磁盘，平均转动时间是14.8毫秒（0.5+7.8+6.5（6.5=1+（65536/3）/4000）），无论如何，如果我们有两个镜像盘，每一个都可以同时读请求，或者以7.4毫秒的速度读请求。那么问题b的答案是135个块每秒。对问题c，限制每个盘读一半的道意味着如果不是总是有等待的序列（该序列减慢了磁盘可以支持的请求），那么同样的半个磁盘可能会有两个请求，在这样的情况下就有一个请求在等待但是磁盘处于闲置状态。2假设磁盘某一年故障百分率为F，更换一个盘要花费H小时。a）如果我们使用镜像盘，作为F和H的函数，数据丢失的平均时间是多少？b）如果我们采用RAID4级和5级方案，使用N个磁盘，数据丢失的平均时间是多少？解：若要计算丢失的平均时间，我们可以计算出在一年中系统出现故障的可能性。平均无故障时间将为该概率的逆。请注意一年有8760小时。如果第二个磁盘出现故障，第一个磁盘正在被修理，那系统将出问题。一年出现故障的概率为2F。第二个磁盘将在另外一个在编写的H小时失败的概率是H/8760。因此，任何一年的失败的概率是2FH/8760，该失效是4380/跳频。平均无故障时间为4380/FH.如果在H小时内有三个磁盘损坏，系统将会丢失数据。一年中所有的磁盘出故障的概率为NF.如果是这样，还有的（n-2）/两对其他磁盘可能会失败在H小时内，并他们中任何一个将这样做的可能性为：FH/8760。因此，两个另外的磁盘失败的可能性是（N-1）(N-2)F^2H^2/(2*8760^2)，或者大约（NFH）^2/1.5*10^8.平均无故障时间将为该概率的逆。2.6.4假设我们使用RAID4级方案，有4个数据盘和一个冗余盘。与例2.17一样，假设块为单字节。如果数据盘的相应块如下，给出冗余盘的块。a)01010110，11000000，00111011和11111011。b)11110000，11111000，00111111和00000001。a) 01010110110000000011101111111011采用偶校验 01010110b) 11110000111110000011111100000001采用偶校验001101102.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，101010103.2.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。3.2.2对字段序列：一个8字节实数，一个长度为17的字符串，单独一个字节，一个SQL2日期，重做习题3.2.1。3.2.5假设字段如3.2.1，记录有个首部，它由两个四字节的指针和一个字符组成，且我们希望在一个4096个字节的块中装入尽可能多的记录，使用的块首部由10个4字节的整数组成，对习题3.2.1中的三个情况，我们各能将多少记录装入块中参考3.2.1题答案(4096–40)/35(4096–40)/40(4096–80)/483.4.1p92（？）一个病人记录包含以下定长字段：病人的出生日期、社会保险号码和病人ID，每一个字段都是10字节长。它还有下列变长字段：姓名、住址和病史。如果记录内一个指针需要4个字节，记录长度是一个4字节整数，不包括变长字段空间，这条记录需要多少字节？可以假设不需要对字段进行对齐。Thefixed-lengthfieldsrequire30bytes.Forthevariable-lengthfieldsweneedintheheaderarecordlengthandpointerstoallbutthefirstofthethreevariable-lengthfields,oranother12bytes.Thus,weneed42bytespluswhateverspacethevariable-lengthfieldsthemselvestake.固定长度的字段需要30个字节。对于可变长度字段，除了三个可变长度的第一个字段，我们需要在首部产生12字节的记录长度和指针。因此，我们需要42个字节，加上自己采取任何空间的可变长度字段。10*3+12=423.4.2假设使用习题3.4.1的记录。变长字段姓名、住址和病史的长度都符合均匀分布。对姓名来说，其范围为10～50个字节；对住址来说，其范围是20～80个字节；对病史来说，范围是0～1000字节。一个病人记录的平均长度是多少？Theaveragenamefieldtakes30bytes,theaverageaddress50bytes,andtheaveragehistory500bytes.Thus,theaveragelengthofarecordis42+30+50+500=622bytes.平均姓名字段需要30个字节，平均地址的50个字节，平均病史500bytes。因此，记录的平均长度是42+30+50+500=622字节。3.5.2关系数据库系统总是倾向于尽可能使用定长元组，给出这种优先考虑的三种理由答案：在插入、删除、修改记录时不会涉及记录滑块和溢出块等问题，提高数据性能。4.11假定每个存储块可存入3个记录或10个键-指针对。设记录数为n，保存一个数据文件和a)一个稠密索引b)一个稀疏索引各需要多少块（表示为n的函数）？a、稠密索引为每个记录数设一个键-指针对，所以共需要索引块n/10+记录块n/3=13n/30b、稀疏索引只为每个记录的存储块设一个键-指针对，所以共需要索引n/3/10+记录块n/3=11n/304.随着数据文件的插入和删除，辅助索引也需要修改。请提出一些使辅助索引与数据文件的改变同步的方法WhenweinsertarecordwithkeyK,wemustinsertarecordintothesecondaryindexfilewiththatvalueKandapointertothedatarecord.Anytechniqueforinsertingintoasequentialfileisappropriate.当我们根据关键字K插入记录时，我们必须在辅助索引文件插入指向数据记录关键字K的指针。任何插入到一个连续的文件的技术都是适用的4.2考虑如图所示的聚集文件组织结构，且假定每个存储块可以放10个制片厂记录或电影记录。再假定每个制片厂制作的电影数都在1～m之间均匀分布。如果表示成m的函数，则检索某个制片厂和它所制作的电影所需的平均磁盘I/O数是多少？如果电影记录随机分布在大量块中，这个平均磁盘I/O数又是多少？Thisquestionaskswhatistheaveragenumberofblocksoverwhichm+1recordsextend,if10fitinablock,andtheystartatarandomslotonablock.Ifm=0,theanswerisclearly1,andifm=10,theanswerisclearly2.Asthefunctionmustbelinearinm,wecaninferthattheaverageisalwaysm/10.Iftherecordsweredistributedondifferentblocks,thenumberofdiskI/O'swouldbem+1.这个问题问的是假设一个存储块可存放10个记录，且从存储块的空槽开始存放，那么扩大到m+1个电影记录所需的存储块的平均数是多少。如果m=0，结果显然为1，如果m=10，则结果为2。因此如果表示成m的函数，我们可以推论出制作电影所需的平均磁盘I/O数是m/10。如果电影记录随机分布在大量块中，这个平均磁盘I/O数则是m+1。4.3.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树是稀疏索引，但数据文件的每个基本块有一个溢出块。平均来讲，基本块是满的，而溢出块只半满。不过，记录在基本块和溢出块中没有特定的顺序。Exercise4.3.1(a)Notethatpart(a)contradictsthestemoftheexercisebyclaimingthesequentialfilehas100records/block.Weshallassume10records/block,asinthestem,iscorrect.First,thereare100,000datablocks.Ifthereareanaverageof70pointersperblockinthebottom-levelnodesoftheB-tree,thenthereare14286B-treeblocksatthatlevel.ThenextleveloftheBtreerequires1/70thofthat,or2041blocks,andthethirdlevelhas1/70thofthat,or30blocks.Thefourthlevelhasonlytherootblock.Thenumberofblocksneededistherefore100,000+14,286+2041+30+1=116,358blocks.SincetheB-treehasfourlevels,wemustmakeatotaloffivediskreadstogothroughtheB-treetothedesireddatablock.Exercise4.3.1(e)Tobegin,thereare1,000,000/15primaryblocks,or66,667primaryblocks,eachwith10records,andthesamenumberofoverflowblocks,eachwith5records.Thenumberoffirst-levelB-treeblocksis66,667/70=953.Atthesecondlevelthereare953/70=14,andthethirdlevelhasonlytheroot.Thus,thereare133,334datablocksand968indexblocks,foratotalof134,302blocks.AsearchrequiresthreediskI/O'stogothroughtheB-treetothedatafile.Oncethere,wesurelyneedtoreadtheprimaryblock,and1/3ofthetimeweshallneedtoseetheoverflowblockaswell.Thus,theaveragenumberofdiskI/O'sis13/3.首先，有100,000个数据块。如果在B树的底部节点只有平均充满程度为70％指针块，这样就会有1000000/70=14286的B树块在这一水平。在它的上层就会有70%的底层块为14286/70=205块，第三个层面会有70%的第二层面块为205/70=3。第四层次就是根块。因此，需要的块数为100000+14286+205+3+1=114495块.B树有四个层次，通过该B树我们必须使共五个磁盘I/O数读取所需的数据块，4.3.4B-树中（i）内结点和（ii）叶结点的键和指针的最小数目在下列情况下分别是多少？*a)n=10；即每块可存放10个键和11个指针。b)n=11；即每块可存放11个键和12个指针。Interiornodes:atleast5keysand6pointers.Leaves:atleast5keysandpointers,notcountingtheoptionalextrapointertothenextleafblock.编者注：内节点至少有「(n+1)/2个指针「(n+1)/2-1个键叶节点至少有(n+1)/2」个指针，(n+1)/2」-1个键。内节点:至少5键和6个指针.叶结点:至少5个键和指针，不计算额外的可选指针到下一叶块(编者注：这句意思可能是因为没有兄弟叶叶就不需要在该叶上存储指向兄弟叶的指针)4.4.1假若在图散列表中发生下列插入和删除，请说明将产生什么情况：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记录5.2.1图中PC机中的12台的规格说明，假若我们希望只在速度和硬盘大小上设计索引。

a）选择5条网格线（两维的总数）以便使任何桶中不超过两个点。b）如果只使用4条网格线，每桶至多有2个点，你能分隔这些点吗？如果可能，则画出如何分隔；否则，解释为何不可能？c）提出一个分段散列函数，它能划分这些点到4个桶中且每桶不超过4个点。Amongthemanywaystoaccomplishthistaskistoputonegridlineinthehard-diskdimensionat8,andfourgridlinesinthespeeddimension,at280,320,360,and420.在众多的方法来完成这项任务的其中一个方法是是把一个硬盘尺寸网格线设在8，和四个速度网格线设在280，320，360，和420。型号速度内存硬盘A300326.0B333644.0C4006412.7D3503210.8E4509614.0F40012812.7G45012818.1H233324.0I266646.0J300646.0K3506412.0L4001286.05.2.4假定我们用一个只有速度和内存的二维网格文件来存上题图中的数据。速度维上的划分为310、375和425，内存维上的划分为40和75。还假定每桶只能存放两个点。如果插入速度为250且内存为48的点，试提出好的分裂如果插入速度为333且内存为48的点，试提出好的分裂Thebestchoiceistosplitaccordingtospeed,byintroducingagridlineat260orthereabouts.Thatlinedividestwooftherectanglesnontrivially,whileanygridlineintheRAMdimensionwillonlysplittheoneoverflowingbucket.根据速度，最好的选择是网格线分裂在260点左右，这条线分成两个重大的矩形，其他任何的RAM尺寸的格线只会分裂一个溢满桶。5.3.3假设我们有一个关系R（x，y，z），其属性x和y一起形成键。属性x的范围是从1到100，属性y的范围是从1到1000。对于每一个x，有100个y值不同的记录；对于每个y，有10个x值不同的记录。注意R有10000个这样的记录。我们希望使用一个多键索引来帮助我们回答如下形式的查询：SELECTZFROMRWHEREX=CANDY=D其中C和D为常量。假定每块能够存放10个键-指针对，并且我们希望在每一级创建稠密索引，可能在它们之上有高层的稀疏索引，因此每个索引从单个块开始。还假定最初所有的索引和数据块都在磁盘上：a）如果第一个索引是建立在y上，回答上述形式的查询需要多少个磁盘I/O？b）如果第一个索引是建在x上，回答上述形式的查询需要多少磁盘I/O？c）假设你一直被允许有6个内存缓冲块，如果你想使额外需要的磁盘I/O数最小化，你将选择哪些块？你生成x或y的第一个索引吗？Fortheindexonxweneed10first-levelindexblockstoholdall100valuesofxandtheircorrespondingpointerstoindexesony.Thus,weneedasecond-levelindexwithoneblock.Findingthey-indexforthex-valuex=CthusrequirestwodiskI/O's.Now,wemustenterthey-indexforthisx-value.Sincethereare10y-valuesforeachx-value,thisindexisasingleblock,whichmustberetrieved.WehavenowmadethreediskI/O's.Ifthereisindeedarecordwithx=Candy=D,thenafourthdiskI/Oisneededtoretrievethez-value.b）为了在x上建立索引，我们需要10个一级索引块(每块能够存放10个键-指针对)来支承所有的100个值和他们的对应到y的索引指针。因此，我们需要一个二级索引块。通过x=c中的x值来寻找y的索引，这样需要两次磁盘I/O。编者注：一块存储块能存10个索引，三级1块y索引，二级10块x索引，这样可以满足x值有100的可能，对每个x索引，对应一级10块x索引，所以查询索引的磁盘I/O共需要3次a）现在，我们必须为这个x值创建y索引。因为每个y值对应10个x值，这个必须检索索引是一个唯一块。我们现在做了三次磁盘I/O。如果的确有一个纪录满足x=c和y=d，则第四次磁盘I/O是需要的检索Z值。编者注：一块存储块能存10个索引，所以四级一块y索引，三级10块y索引，二级100块y索引，这样可以满足y值有1000的可能，对每个Y索引，对应一级1块x索引，所以查询索引的磁盘I/O共需要4次编者备注：一级是低级索引块二级及以后是高级索引；英文答案和问题反掉了5.3.5下图中什么样的新点将会被插入到：a)点（30,260）所在的块；b)点（50，100）和点（50，120）所在的块。Togettotheblockwith(30,260),youhavetogorightatanodewithsalary=150andleftatanodewithsalary=300.Thusthesalarymustbeatleast150,andlessthan300.Also,youmustgoleftatanodewithage=47,sotheagemustbelessthan47.插入到块（30,260）中的节点是一个在工资=150的节点右侧，和在一个工资=300的节点左侧，。因此，工资的范围是大于150和小于300。此外，你必须在一个年龄=47的节点的左侧，那就是说年龄必须小于47。a.年龄小于47，工资在150-300之间b.年龄在38-60之间，工资在80-150之间6.1.1下面是两个关系：R(a,b):{(0,1),(2,3),(0,1),(2,4),(3,4)}S(a,b):{(0,1),(2,4),(2,5),(3,4),(0,2),(3,4)}计算下列各项：a)R∪SS b)R∪BS c)R∩sS d)R∩BS e)R-SS f)R-BSg)R-SR h)R-BR i)Πa+b,a2,b2(R) j)Πa+1,b-1(S) k)σa<bAND(a+b>a*bORa+b≥6)(R) l)σa<bAND(a+b>a*bORa+b≥6)(S)m)σa>1ORb>4ORb=2(R) n)σa>1ORb>4ORb=2(S)Exercise6.1.1(a)Technically,theU_Soperatorassumesthattheargumentsaresets,aswellastheresult.Sincetheargumentsarereallybags,thebestwecandoisusetheSQLunionoperator,whichremovesduplicatesfromtheoutputevenifthereareduplicatesintheinput.Theansweris{(0,1),(2,3),(2,4),(3,4),(2,5),(0,2)}.Exercise6.1.1(i){(1,0,1),(5,4,9),(1,0,1),(6,4,16),(7,9,16)}.Exercise6.1.1(k){(0,1),(0,1),(2,4),(3,4)}.NotethatallfivetuplesofRsatisfythefirstcondition,thatthefirstcomponentislessthanthesecond.Thelasttwotuplessatisfytheconditionthatthesumofthecomponentsisatleast6,andthetuple(0,1)satisfiestheconditionthatthesumexceedtheproduct.Onlythetuple(2,3)satisfiesneitherofthelattertwoconditions,andthereforedoesn'tappearintheresult.a)：{(0,1),(2,3),(2,4),(3,4),(2,5),(0,2)}b)：{(0,1),(0,1),(0,1),(0,2),(2,3),(2,4),(2,4),(2,5),(3,4),(3,4),(3,4)}c)：{(0,1),(2,4),(3,4)}d)：{(0,1),(2,4),(3,4)}e)：{(2,3)}f)：{(0,1),(2,3)}g)：{}h)：{}i):{(1,0,1),(5,4,9),(1,0,1),(6,4,16),(7,9,16)}.j):{(1,0),(3,3),(3,4),(4,3),(1,1),(4,3)}k):{(0,1),(0,1),(2,4),(3,4)}l):{(0,1),(2,4),(2,5),(3,4),(0,2),(3,4)}m):{(2,3),(2,4),(3,4)}n):{(2,4),(2,5),(3,4),(0,2),(3,4)}编者注：∪并，∩交，Π投影，σ选择UB是包并，合并所有元组US是集合并，合并所有元组，并唯一R∩BS是包交，输出R和S中数量最少的R∩SS是集合交，输出R和S都有的，并唯一R-BS是包差,输出R中数量减去S中的元组 R-sS是集合差,输出R中S没有的，并唯一6.1.6使用下面的“电影关系”：Movie(title,year,length,studioname)Moviestar(name,address,gender,birthdate)starsin(title,year,starname)studio(name,address)使用本节的代数操作符,将下面的饿查询转变为表达式树SELECTADDRESSFROMMOVIE,STUDIOWHERESTDIONAME=NAMEANDTITLE=’BONEWITHTHEWIND’(SELECTNAMEFROMMOVIESTAR)UNION(SELECTSTARTNAMEFROMSTARSIN)c)(SELECTNAMEFROMMOVIESTAR)UNIONALL(SELECTSTARTNAMEFROMSTARSIN)d)SELECTSTARNAME,SUM(LENGTH)FROMMOVIENATURALJOINSTARSINGROUPBYSTARNAMEHAVINGCOUNT(*)>=3a.∏address|stdioname=name∧title=”thewiththewind”|X/\Moviestudio6.假设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编者注:6.4.4章节公式:B(S)+7使用本节所给出的简单SQL语法,画出关于关系R(a,b)与S(b,c)查询语句的语法树SELECTa,cFROMR,SWHERER.b=S.bSELECTafromRwherebIN(SELECTafromR,SWHERER.b=S.b)答案：a. b.∏a,c|R.b=S.b|X/\Rs∏a|R.b=S.b|X/\R∏a|R.b=S.b|X/\RS7.2.6针对表达式πL(R(a,b,c)⋈S(b,c,d,e)),尽可能下推投影，其中L是:a)b+c→xc+d→y。 b)a,b,a+d→z。Wecannotpushdownb+c-&>x,becausebothbandcareusedinthejoin.Noticethatifwereplacedb+cbytheirsumbeforejoining,wewouldjointupleswhosesumb+cagreed,butthathaddifferentvaluesofbandc.Whatwecanpushdownis:1.TheeliminationofafromR.2.TheeliminationofefromS.3.Thereplacementofc+dbyyinS.Thus,theansweris:pi_{b+c->x,y}(pi_{b,c}(R)JOINpi_{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+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))7.4.1下面是4个关系W、X、Y、Z的关键统计值:估计下列表达式结果关系的大小：a)W⋈X⋈Y⋈Zb)σa=10(W)c)σc=20(Y)d)σc=20(Y)⋈Ze)WXYf)σd>10(Z)g)σa=1andb=2(W)h)σa=1andb>2(W)Exercise7.4.1(a)Startbytakingtheproductofthesizesoftherelations:100*200*300*400=2,400,000,000.Sinceattributebappearsintworelations,dividebythelargerofV(W,b)andV(X,b),whichis60.Similarly,forcdividedby100,andforddivideby50.Theresultis8000tuples.Exercise7.4.1(b)TheestimateisT(W)/V(W,a)=100/20=5.Exercise7.4.1(g)StartwiththenumberoftuplesofW,whichis100.Wemustthenmultiplybytheestimatedprobabilitythatanyonetuplewillsatisfybothoftheconditionsa=1andb=2.Sincethereisnoreasontobelievetheseconditionsarenotindependent,wedivide100byV(W,a)*V(W,b).Theresultisthefraction1/12.Thatis,theestimatedsizeoftheresultislessthanonetuple.Thisconclusionmakessense,sincethereare1200possibletuplesthatcouldbeconstructedfrom20a-valuesand60b-values;(1,2)isonlyoneofthem.练习（a）

开始的关系的大小：100×200×300×400=2,400,000,000。由于属性b在两个关系中，除以V（W，B）和V（X，B）的较大的60。同样的c为100,D为50。结果是8000元组。练习（b）

估计是T(W)/V(W.a)=100/20=5。

练习（g）元组的W的数量是100。我们必须再乘以任何一个元组满足这两个条件A=1，B=2估计的概率。因为没有理由相信这些条件都不是独立的的，我们用100/V(W,A)*V(W,B)。结果是1/12的比例。也就是说，估计结果的大小不到一元组。这个结论是有道理的，因为有1200种可能的元祖，他们的a值有20可能，b值有60个可能;（1,2）只是其中之一。7.4.2下面是4个关系E、F、G、H的统计值利用本节中的估计技术,估计这些元祖连接会产生多少元祖Startbymultiplyingthesizesoftherelations,whichis1000*2000*3000*4000=24,000,000,000,000.Attributeaappearsthreetimes,sowedividebythetwolargestofV(E,a),V(F,a),andV(G,a).Thesenumbersare1000,50,and50,sowedivideby50,000.Similarly,forbwedividebythetwolargestof50,100,and40,or5000.Forcwedividebythetwolargestof20,300,and100,or3000,andfordwedividebythetwolargestof200,500,and400,or200,000.Theresultisafraction:8/50000.Thatis,theexpectednumberoftuplesisunder1.Thatshouldnotbesurprising,sincetherearesomanyequalitiesthatmustbesatisfied,inorderforfourtuples,onefromeachrelation,tojoin.首先乘以关系的大小为1000*2000*3000*4000=24000000000000。属性a出现三次，所以我们在V(E,a),V(F,a)和V(G,A)划分两个最大的。它们对应的数字是1000，50，50，所以我们得到50,000。同样，我们对B50，100和40取两个最大的得到5000。对于C20，300和100取两个最大的得到30000，和对于d200,500和400我们两个最大的200,000，结果是一个分数：8/10000。也就是说，预期的元组数小于1。这并不奇怪，因为有这么多的等式必须满足四元组的每个关系。7.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=1andb=2andd=3(R)b)σa=1andb=2andc>=3(R)c)σa=1andb<=2andc>=3(R)Useanindex-scanusingthenonclusteringindexonc.SinceV(R,c)=5000,onlyoneblockshouldberetrieved.Filtertheretrievedtuplesfora=1andd=3.TheexpecteddiskI/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/O8.2.4下面是两个事务T和U的一系列日志记录：<STARTT>;<T,A,10>;<STARTU>;<U,B,20>;<T,C,30>;<U,D,40>;<COMMITU>;<T,E,50>;<COMMITT>.描述恢复管理器的行为，包括对磁盘盒日志所做的改变，假设发生故障且出现在磁盘上的最后一条日志记录为(编者注：故障发生在下列语句的后一句，试描述如何恢复)：a)<STARTU>b)<COMMITU>c)<T,E,50>d)<COMMITT>Uisidentifiedascommitted,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还没有提交的数据要恢复,数据时老数据8.3.3使用redo日志重做上题SinceTisnotcomplete,wecanbesurethatnoneofitschangesreacheddisk,andwecanignorelogrecordsaboutT.Ontheotherhand,Uwascommitted,anditslogrecordreacheddisk,sosomeofitschangesmayhavereacheddisk.Tobesure,wemustredoalloftheactionsofU.Thus,wefirstsetBto20andthensetDto40.因为T没有完成，我们可以肯定他的任何变化都没有达到磁盘，我们可以忽略关于T的日志记录，另一方面，U提交了，他的日志写道了磁盘上。它的一些变化也到达磁盘的。可以肯定的是，我们必须重做U的所有行动，因此，我们首先B=20，然后到D=40编者注：redo已经提交的数据要重新做，数据时新数据8.下面是两个事务组T和U的一组记录<STARTT>;<T,A,10,11>;<STARTU>;<U,B,20,21>;<T,C,30,31>;<U,D,40,41>;<COMMITU>;<T,E,50,51>;<COMMITT>.描述回复管理器的行为，包括对磁盘和日志所做的改变，假设故障发生，且出现在磁盘上