《数据库理论与技术》复习题-2008小妖版

《数据库理论与技术》复习题-2008小妖版

1. 考虑用二元联系（图1）对三元联系（图2）的表示：

图A 1

RA

RB B E

图1 A

R B

图2

RC C C 1) 分别给出图1中E，A，B，C，RA，RB和RC的一个实例，这些实例不对应图2中A，B，C和R的任何实例；

2) 更改图1中的ER图，引入适当的约束以确保满足约束的E，A，B，C，RA，RB和RC的任何实例都对应于A，B，C和R的一个实例； 3) 更改以上的转化以表示在三元联系上的全参与约束；

解：

1） 令 E = {e1, e2}, A = {a1, a2}, B = {b1}, C = {c1}, RA = {(e1, a1), (e2, a2)},Rb={(e1,b1)}, Rc={(e1,c1)}；

可以看出，由于元组（e2,a2）的原因，不存在任何实例对应于E,Ra,Rb,Rc 2） 如下图所示：通过引入E 和关系 Ra ， Rb ， Rc之间的全部参与的约束条件，以便在 E 中的每个元组都和A ，B，C有关系。

3） 假设A全部参与关系R，则在A和Ra之间引入全部参与约束

4） 将 E看作弱实体集，而将Ra,Rb,Rc看作标志联系集。如下图所示

2. 分别判断下列图中G1和G2是否互模拟(bisimulation)，并说明理由

G1=

b

a a c

a

G2=

b c

G1 a

b

c

c d

d a G2

b c d

解: （１）在图中标出各点的状态,我们构造关系S={(P0,Q0),(P1,Q1),(P2,Q1),(P3,Q2),(P4,Q3)}

可知G2可以模拟G1,下面我们讨论

S+1={( Q0, P0),(Q1, P1),(Q1, P2),(Q2, P3),(Q3,P4)}

是否可模拟,在G2中Q0有一个a变换可对应到G1中2个变换,即(Q1,P1)∈S-1, (Q1,P2)∈S-1。但Q1有两个变换b,c，而在Ｇ１中公存在只有b或只有c的状态点，可知Ｇ１和Ｇ２不能互模拟。

（２）如图，标出各状态点，构造有关系

S={(P0,Q0),(P1,Q1),(P1,Q2),(P2,Q3),(P2,Q4), (P3,Q5)},

可知其中Ｇ１中的点均可由G2中的点模拟，下面我们考虑

S+1={( Q0, P0),(Q1, P1),(Q2, P1),(Q3, P2),(Q4,P2),(Q5,P3)}，

可知同样其中Ｇ２中的点均可由Ｇ１中的点模拟，所以Ｇ１和Ｇ２互模拟。

3. 什么是可恢复调度？为什么要求调度的可恢复性？存在要求允许出现不可

恢复调度的情况吗？说明理由。

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

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

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

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

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

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

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

5. 设关系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值匹配。

6. 设一个嵌入式SQL应用程序中80%的时间花在运行SQL代码上，20%的时间花在运行主语言代码上。如果只对SQL代码实施了并行，那么可以期望得到多大的加速比？说明理由。

答：由于不能被并行话的部分占总运行时间的20%，所以可获得的加速比最多不会超过5。

7. 假设一个系统运行三种类型的事务：A类事务以50/s的速度运行，B类事务

以100/s的速度运行，C类事务以200/s的速度运行。假设系统所处理的事务中A、B、C三类事务所占比例分别为30%，30%，40%。

1) 如果A、B、C三类事务之间互不干扰，系统的平均事务吞吐量是多

少？

1) 什么因素会使不同类型事务之间产生相互干扰，导致计算出的平均

事务吞吐量不准确？

2) 如果不同类型事务之间相互干扰的因素非常复杂，那么用什么方法

可以得到比较准确的平均事务吞吐量？

n答：1）?91

n*30%n*30%n*40%??501002002）引起事务之间干扰的最重要的原因之一是封锁竞争。在前面的例子中，假设事务A

和事务B都是更新事务，而事务C是查询事务。由于处理器和磁盘之间的速度不匹配，很可能会出现下面的情况：A类型的一个事务持有一个“热”数据项的锁，并且在等待将其写道磁盘中来完成操作，在在这个时候B类或C类一个事务正在等待事务A持有的封锁。在这种情况下，一些CPU循环就被浪费了。因此，观察到的事物吞吐量会比计算出来的吞吐量要小。

相反，如果A类型的事务和B类型的事务是大量消耗磁盘资源的事务，而C类型事务时大量消耗CPU资源的事务，那么观察到的事物吞吐量将会比计算到吞吐量大。 封锁竞争也会导致死锁，在这种情况下一些事务将不得不被终止。事务的终止和重启将会导致观察到的吞吐量比计算出来的吞吐量要小。 数据结构大小的限制，事务管理器事务记录函数花费时间的变化情况等因素都会导致观察到的吞吐量和计算出来的吞吐量之间的不同。

3）如果不同类型事务之间的相互干扰因素非常复杂，那么我们可以采用性能模拟的办法对系统得吞吐量进行测试。首先需要建立模型，然后再模型上进行各种实验，可以通过改变不同的实验环境来估算出系统得平均吞吐量。

8. 对于下列每一种任务，哪一种并行形式(查询间并行、操作间并行、操作内并

行)可能是最关键的？说明理由。

1) 提高一个执行许多小的查询的系统吞吐量；

2) 在磁盘和处理器数目都很大的情况下，提高一个执行少量大的查询

的系统吞吐量； < …… 此处隐藏：1950字，全部文档内容请下载后查看。喜欢就下载吧 ……