数据库复习题2

复习题2

1. 设关系r1(A，B，C)，r2(C，D，E)有如下特性：r1有200000个元组，r2有

45000个元组，一块中可容纳25个r1元组或30个r2元组。试估算以下每一种策略计算r1|><|r2所需存取的块数：

1) 嵌套循环连接 2) 块嵌套循环连接 3) 归并连接 4) 散列连接

解：r1需要8000个块，r2需要1500个块。假设有一个存储器有M页。如果M>8000，那么使用平坦嵌套循环，通过1500＋8000次磁盘存取就可以很容易的完成连接操作。因此我们只考虑M<=8000的情况。

1） 嵌套循环连接：

使用r1作为外关系，我们需要进行200 000×1500＋8000＝300，008，000次磁盘存取。如果r2是外关系，那么我们需要45 000×8 000＋1 500＝360 001 500次磁盘存取。 2） 块嵌套循环连接：

如果r1是外关系，我们需要??×1500＋8000次磁盘存取，如果r2是外?8000/(M?2)?关系，我们需要??1500/(M-2)??×8000＋1500次磁盘存取。 3） 归并连接

假设r1和r2最初没有按连接关键字进行排序，那么总的排序加上输出的耗费为Bs＝1500（2 ??logM-1(1500/M)??＋1）＋8000（2 ??logM-1(8000/M)??＋1）次磁盘存取。假设具有相同连接属性值的所有员组装入内存中，那么总的耗费是Bs＋1500＋8000次磁盘存取。

4） 散列连接

我们假设不发生溢出。因为r2比较小，所以我们用r2作为创建关系，用r1作为探针关系。如果M>1500，那么就不需要进行递归分割，于是耗费为3（1500＋8000）＝28 500次磁盘存取，否则耗费为2（1500＋8000）??logM-1(1500/M)+2??＋1500＋8000次磁盘存取。

2. 设关系r1(A，B，C)，r2(C，D，E)和r3(E，F)，其主码分别为A，C，E。

假设r1有1500个元组，r2有2500个元组，r3有1000个元组。

1) 试估计r1|><|r2|><|r3的大小；

2) 给出一个有效计算r1|><|r2|><|r3的策略；

答：1）因为连接具有结合律和交换性，所以不管我们怎样连接r1,r2和r3，最终连接r1，r2和r3得到的结果都是一样的。因此，我们只考虑基于（（r1 r2）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值匹配。

3. Consider a hash-join of two relations R and S having B(R) = 1000 and B(S) =

500. The values in R and S are skewed such that the hash function assigns three times as many tuples to even-numbered hash buckets as to odd-numbered buckets.

1) How much memory would be required to perform the join in two passes? 2) What is the performance of the hash-join given the skewed hashing? 3) How would the performance of using the hash-join compare to using a

sorted-merge algorithm?

1。散列连接要用两趟完成，则需要递归划分，对关系s的划分所需趟数估计为

logM?1(b(s))?1，所以有500?(2log99500/100?1)?8502?logM?1500?1， M=8.9。

对关系r进行划分所需趟数估计为logM?1(b(r))?1，且2?logM?11000?1，M=11。 因为散列算法要求内存满足小的操作对象，所以需要8.9*4KB=35.6KB的内存。

2. 增加分区的个数，使得每个分区的大小（包括该分区上的散列索引在内）小于内存容量。 3.基于散列的算法使用一个散列函数将操作对象分割到桶中，然后操作被分别应用到桶和桶对上能被内存所容纳。基于排序归并连接的算法可对大于内存的关系进行排序，可知在关系以排序的情况下，归并连接是比较可取的。散列和排序在某种意义下是对偶的，因为能用散列实现的连接也可用排序来实现，反之亦然。基于散列的算法常常优于基于排序的算法，我们假设内存能容纳100个块，则用散列连接对S划分为5个划分，则代价为3（1000+500）=4500次块传输，用排序归并对R的排序需1000?(2log991000/100?1)?2000次快传输，对S的排序需500?(2log99500/100?1)?850次块传输，把排序写回磁盘需要1500次块传输，归并步骤还需1500次块传输以读回数据，因此归并排序总代价为5850次块传输。

4. 什么是可恢复调度？举例说明。

答：假设在一个调度中，Tj读取了Ti写入的数据，Ti在提交前发生故障，我们必须中止Tj以保证事务地原子性。若Tj在Ti出现故障后是可中止的，那么我们就称该调度是可恢复调度。可恢复调度应满足：对于每个事务Ti和Tj，如果Tj读取了由Ti所写的数据项，则Ti先于Tj提交。

5. State if the following statements are true or false.

1) For any schedule S1 and any serial schedule S2, if S1 is conflict

equivalent to S2, then S1 is conflict serializable. 2) For any schedules S1 and S2, if S1 and S2 are conflict

serializable, then S1 and S2 are conflict equivalent. 3) All serializable schedules are recoverable. 4) All recoverable schedules are serializable.

5) All serial schedules are ACR (avoid cascading rollback). 6) Any schedule that can be produced by a two-phase locking

mechanism can also be produced by a validation mechanism. 7) Any schedule that can be produced by a validation

mechanism can also be produced by a two-phase locking mechanism.

8) Any schedule that can be produced by a two-phase locking

mechanism with shared (read) and exclusive (write) locks, can also be produced by a two-phase locking mechanism with exclusive locks only.

1）ANSWER: true 2）ANSWER: false 3）ANSWER: false 4）ANSWER: false 5）ANSWER: true 6）ANSWER: false 7）ANSWER: true 8）ANSWER: true

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据库复习题2在线全文阅读。