数据库复习题2

复习题2设关系r1(A，B，C)，r2(C，D，E)有如下特性：r1有200000个元组，r2有45000个元组，一块中可容纳25个r1元组或30个r2元组。试估算以下每一种策略计算r1|><|r2所需存取的块数：嵌套循环连接块嵌套循环连接归并连接散列连接解：r1需要8000个块，r2需要1500个块。假设有一个存储器有M页。如果M>8000，那么使用平坦嵌套循环，通过1500＋8000次磁盘存取就可以很容易的完成连接操作。因此我们只考虑M<=8000的情况。嵌套循环连接：使用r1作为外关系，我们需要进行200000×1500＋8000＝300，008，000次磁盘存取。如果r2是外关系，那么我们需要45000×8000＋1500＝360001500次磁盘存取。2）块嵌套循环连接：如果r1是外关系，我们需要×1500＋8000次磁盘存取，如果r2是外关系，我们需要×8000＋1500次磁盘存取。3）归并连接假设r1和r2最初没有按连接关键字进行排序，那么总的排序加上输出的耗费为Bs＝1500（2＋1）＋8000（2＋1）次磁盘存取。假设具有相同连接属性值的所有员组装入内存中，那么总的耗费是Bs＋1500＋8000次磁盘存取。4）散列连接我们假设不发生溢出。因为r2比较小，所以我们用r2作为创建关系，用r1作为探针关系。如果M>1500，那么就不需要进行递归分割，于是耗费为3（1500＋8000）＝28500次磁盘存取，否则耗费为2（1500＋8000）＋1500＋8000次磁盘存取。设关系r1(A，B，C)，r2(C，D，E)和r3(E，F)，其主码分别为A，C，E。假设r1有1500个元组，r2有2500个元组，r3有1000个元组。试估计r1|><|r2|><|r3的大小；给出一个有效计算r1|><|r2|><|r3的策略；答：1）因为连接具有结合律和交换性，所以不管我们怎样连接r1,r2和r3，最终连接r1，r2和r3得到的结果都是一样的。因此，我们只考虑基于（（r1r2）r3）连接策略下的大小。因为C为r2的关键字，所以连接r1和r2产生至多包含1500个元组的关系。同样，把前面得到的结果和r3进行连接，将产生至多包含1500个元组的关系，因为E为r3的关键字。因此，最终关系最多包含有1500个元组。2）计算这个连接的一个有效的策略是为关系r2上的属性C和关系r3上的属性E创建索引。然后对于r1中的每个元组，我们按照下面锝方法作：A．使用在C上创建的索引，在r2中查找最多一个元组，这个元组与r1中的C匹配。B．使用在E上创建的索引，在r3中查找最多一个元组，这个元组与r2中的E值匹配。Considerahash-joinoftworelationsRandShavingB(R)=1000andB(S)=500.ThevaluesinRandSareskewedsuchthatthehashfunctionassignsthreetimesasmanytuplestoeven-numberedhashbucketsastoodd-numberedbuckets.Howmuchmemorywouldberequiredtoperformthejoinintwopasses?Whatistheperformanceofthehash-joingiventheskewedhashing?Howwouldtheperformanceofusingthehash-joincomparetousingasorted-mergealgorithm?1。散列连接要用两趟完成，则需要递归划分，对关系s的划分所需趟数估计为，所以有，M=8.9。对关系r进行划分所需趟数估计为，且，M=11。因为散列算法要求内存满足小的操作对象，所以需要8.9*4KB=35.6KB的内存。2.增加分区的个数，使得每个分区的大小（包括该分区上的散列索引在内）小于内存容量。3.基于散列的算法使用一个散列函数将操作对象分割到桶中，然后操作被分别应用到桶和桶对上能被内存所容纳。基于排序归并连接的算法可对大于内存的关系进行排序，可知在关系以排序的情况下，归并连接是比较可取的。散列和排序在某种意义下是对偶的，因为能用散列实现的连接也可用排序来实现，反之亦然。基于散列的算法常常优于基于排序的算法，我们假设内存能容纳100个块，则用散列连接对S划分为5个划分，则代价为3（1000+500）=4500次块传输，用排序归并对R的排序需次快传输，对S的排序需次块传输，把排序写回磁盘需要1500次块传输，归并步骤还需1500次块传输以读回数据，因此归并排序总代价为5850次块传输。什么是可恢复调度？举例说明。答：假设在一个调度中，Tj读取了Ti写入的数据，Ti在提交前发生故障，我们必须中止Tj以保证事务地原子性。若Tj在Ti出现故障后是可中止的，那么我们就称该调度是可恢复调度。可恢复调度应满足：对于每个事务Ti和Tj，如果Tj读取了由Ti所写的数据项，则Ti先于Tj提交。Stateifthefollowingstatementsaretrueorfalse.ForanyscheduleS1andanyserialscheduleS2,ifS1isconflictequivalenttoS2,thenS1isconflictserializable.ForanyschedulesS1andS2,ifS1andS2areconflictserializable,thenS1andS2areconflictequivalent.Allserializableschedulesarerecoverable.Allrecoverableschedulesareserializable.AllserialschedulesareACR(avoidcascadingrollback).Anyschedulethatcanbeproducedbyatwo-phaselockingmechanismcanalsobeproducedbyavalidationmechanism.Anyschedulethatcanbeproducedbyavalidationmechanismcanalsobeproducedbyatwo-phaselockingmechanism.Anyschedulethatcanbeproducedbyatwo-phaselockingmechanismwithshared(read)andexclusive(write)locks,canalsobeproducedbyatwo-phaselock