2022年数据库复习题借鉴 .pdf

《2022年数据库复习题借鉴 .pdf》由会员分享，可在线阅读，更多相关《2022年数据库复习题借鉴 .pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、复习题 2 1.设关系 r1(A， B，C)，r2(C，D，E)有如下特性： r1 有 200000个元组， r2 有45000 个元组，一块中可容纳25 个 r1 元组或 30 个 r2 元组。试估算以下每一种策略计算 r1|8000 ，那么使用平坦嵌套循环，通过 1500 8000 次磁盘存取就可以很容易的完成连接操作。因此我们只考虑 M1500 ，那么就不需要进行递归分割，于是耗费为3（1500 8000 ）28 500次磁盘存取，否则耗费为2（1500 8000）M-1log(1500/ M)+2 1500 8000 次磁盘存取。2.设关系 r1(A，B，C)，r2(C，D， E)和

2、r3(E，F)，其主码分别为A，C，E。假设 r1 有 1500 个元组， r2 有 2500个元组， r3 有 1000 个元组。1)试估计 r1|r3的策略；答： 1）因为连接具有结合律和交换性，所以不管我们怎样连接r1,r2 和 r3，最终连接 r1， r2和r3 得到的结果都是一样的。因此， 我们只考虑基于 （ （r1 r2）r3）连接策略下的大小。因为 C为 r2的关键字，所以连接r1和r2产生至多包含 1500 个元组的关系。同样，把前面得到的结果和 r3进行连接，将产生至多包含1500 个元组的关系，因为E为r3 的关键字。因此，最终关系最多包含有1500 个元组。2）计算这个连

3、接的一个有效的策略是为关系r2上的属性 C和关系 r3上的属性 E创建索引。然名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 3 页 - - - - - - - - - 后对于 r1中的每个元组，我们按照下面锝方法作：A使用在 C上创建的索引，在r2中查找最多一个元组，这个元组与r1 中的 C匹配。B使用在 E 上创建的索引，在r3 中查找最多一个元组，这个元组与r2 中的 E 值匹配。3.Consider a hash-join of two relations R a

4、nd 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 ha

5、sh-join given the skewed hashing? 3)How would the performance of using the hash-join compare to using a sorted-merge algorithm? 1。散列连接要用两趟完成，则需要递归划分，对关系s的划分所需趟数估计为1log( ( )1Mb s，所以有99500 (2log500/1001)85012log500 1M， M=8.9 。对关系 r 进行划分所需趟数估计为1log( ( )1Mb r，且12log1000 1M，M=11 。因为散列算法要求内存满足小的操作对象，所以需要8

6、.9*4KB=35.6KB的内存。2. 增加分区的个数，使得每个分区的大小（包括该分区上的散列索引在内）小于内存容量。3.基于散列的算法使用一个散列函数将操作对象分割到桶中，然后操作被分别应用到桶和桶对上能被内存所容纳。基于排序归并连接的算法可对大于内存的关系进行排序，可知在关系以排序的情况下，归并连接是比较可取的。散列和排序在某种意义下是对偶的，因为能用散列实现的连接也可用排序来实现，反之亦然。 基于散列的算法常常优于基于排序的算法，我们假设内存能容纳100 个块，则用散列连接对S 划分为 5 个划分， 则代价为3 （1000+500 ）=4500 次块传输，用排序归并对R 的排序需9910

7、00 (2log1000/1001)2000次快传输，对 S 的排序需99500 (2log500/1001)850次块传输， 把排序写回磁盘需要1500 次块传输，归并步骤还需1500 次块传输以读回数据，因此归并排序总代价为5850 次块传输。4.什么是可恢复调度？举例说明。答：假设在一个调度中，Tj 读取了 Ti 写入的数据， Ti 在提交前发生故障，我们必须中止Tj以保证事务地原子性。若Tj 在 Ti 出现故障后是可中止的，那么我们就称该调度是可恢复调度。可恢复调度应满足：对于每个事务Ti 和 Tj，如果 Tj 读取了由Ti 所写的数据项，则Ti先于 Tj 提交。5.State if

8、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 S 1 is conflict serializable. 2)For any schedules S1 and S 2, if S1 and S 2 are conflict 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - -

9、- 第 2 页，共 3 页 - - - - - - - - - serializable, then S1 and S 2 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 mec

10、hanism 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

11、 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 3 页 - - - - - - - - -