习题解答

1. 在数据库中为什么要采用并发控制?并发控制技术能保证事务的哪些特性?

数据库是共享资源，通常有许多个事务同时在运行。当多个事务并发地存取数据库时，就会产生同时读取和/或修改同一数据的情况。若对并发操作不加控制，就可能会存取和存储不正确的数据，破坏数据库的一致性，所以数据库管理系统必须提供并发控制机制。
并发控制可以保证事务的一致性和隔离性。

2. 并发操作可能会产生哪几类数据不一致?用什么方法能避免各种不一致的情况?

并发操作带来的数据不一致性主要有丢失修改、脏读、不可重复读、幻读等多种情况：

• 丢失修改：两个事务$T_1$和$T_2$读入同一数据并各自进行修改，$T_2$提交的结果破坏（覆盖）了$T_1$提交的结果，导致$T_1$的修改被丢失。
• 脏读：事务$T_1$修改某一数据并将其写回磁盘，事务$T_2$读取同一数据后，$T_1$由于某种原因被撤销，这时被$T_1$修改过的数据恢复原值，$T_2$读到的数据就与数据库中的数据不一致，$T_2$读到的数据为“脏”数据。
• 不可重复读：事务$T_1$读取数据后，事务$T_2$执行更新操作，当事务$T_1$再次读该数据时，得到与前一次不同的值。
• 幻读：事务$T_1$读取数据后，事务$T_2$执行插入或删除操作，使$T_1$无法再现前一次读取结果。

避免不一致性的方法是并发控制，常用的并发控制技术包括封锁技术、时间戳方法、乐观控制方法、多版本并发控制方法等。

3. 事务的隔离级别都有哪些?事务隔离级别与数据一致性的关系是什么?

SQL标准给出了事务的4类隔离级别，由低到高分别是读未提交、读已提交、可重复读、可串行化。
事务隔离级别是用来描述DBMS对并发操作进行控制的程度，控制越严格，事务的隔离性越强，数据的一致性就越有保障，但系统的效率也会随之下降。各类隔离级别与数据不一致性的关系如下：

事务隔离级别	丢失修改	脏读	不可重复读	幻读
读未提交	否	是	是	是
读已提交	否	否	是	是
可重复读	否	否	否	是
可串行化	否	否	否	否

4. 什么是封锁?基本的封锁类型有几种?试述它们的含义。

封锁是指事务T在对某个数据对象（例如表、记录等）操作之前先向系统发出请求，对其加锁。加锁后事务T就对该数据对象有了一定的控制，在事务T释放其锁之前，其他事务不能更新和/或读取此数据对象。
最基本的封锁类型有两种：排他型锁（X锁）和共享型锁（S锁）：

• 排他型锁（写锁）：若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放A上的锁为止。
• 共享型锁（读锁）：若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁为止。

5. 如何用封锁机制保证数据的一致性?

DBMS按照一定的封锁协议对并发操作进行控制，使得多个并发操作有序地执行，避免丢失修改、不可重复读和读“脏”数据等数据不一致性问题。DBMS在对数据进行读写操作之前，首先对该数据执行封锁操作，保证事务对数据的操作按序进行，从而保证数据一致性。

6. 什么是活锁?试述活锁的产生原因和解决方法。

活锁是指某个等待事务等待的时间太长，似乎被锁住了，实际上可以被激活（如事务$T_2$请求封锁数据R，$T_1$释放R的锁后系统先批准$T_3$的请求，$T_2$持续等待，甚至永远等待）。
产生原因：当一系列封锁不能按照其先后顺序执行时，可能导致一些事务无限期地等待某个封锁。
解决方法：采用先来先服务的策略，当多个事务请求封锁同一数据对象时，封锁子系统按请求封锁的先后次序对事务排队，数据对象上的锁一旦释放，就批准申请队列中第一个事务获得锁。

7. 什么是死锁?请给出预防死锁的若干方法。

死锁是指两个或多个事务相互等待对方释放所持有的锁，导致这些事务永远不能结束（如$T_1$封锁$R_1$，$T_2$封锁$R_2$，$T_1$请求封锁$R_2$，$T_2$请求封锁$R_1$，双方互相等待）。
预防死锁的方法：

• 一次封锁法：要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。
• 顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按这个顺序实施封锁。

8. 请给出检测死锁发生的一种方法。当发生死锁后如何解除死锁?

检测死锁的方法：超时法（如果一个事务的等待时间超过了规定的时限，就认为该事务发生了死锁）；事务等待图法。
解除死锁的方法：选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有的所有锁，使其他事务得以继续运行下去。

9. 什么样的并发调度是正确的调度?

可串行化的调度是正确的调度。可串行化调度的定义：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行这些事务时的结果相同。

10. 设$T_1$、$T_2$、$T_3$是如下的三个事务（A的初值为0）:

$T_1:A:=A+2;$
$T_2:A:=A\ast 2;$
$T_3:A:=A\ast A(即A\leftarrow A^2)$
①若这三个事务允许并发执行,则有多少种可能的正确结果?请一一列举出来。
②请给出一个可串行化的调度,并给出执行结果。
③请给出一个非串行化的调度,并给出执行结果。
④若这三个事务都遵守两段锁协议,请给出一个不产生死锁的可串行化调度。
⑤若这三个事务都遵守两段锁协议,请给出一个产生死锁的调度。

答案：
①A的最终结果可能有2、4、8、16。
②可串行化调度示例：

执行结果：A=16。

③非串行化调度示例：

执行结果：A=0。

④不产生死锁的可串行化调度（遵守两段锁协议）示例：

⑤产生死锁的调度（遵守两段锁协议）示例：

11. 今有三个事务的一个调度$R_3(B)R_1(A)W_3(B)R_2(B)R_2(A)W_2(B)R_1(B)W_1(A)$，该调度是冲突可串行化的调度吗?为什么?

该调度是冲突可串行化的调度。理由：在保证冲突操作次序不变的情况下，交换不冲突操作的次序，可得到串行调度$S{c}_2=R_3(B)W_3(B)R_2(B)R_2(A)W_2(B)R_1(A)R_1(B)W_1(A)$，因此原调度是冲突可串行化的调度。

12. 试证明若并发事务遵守两段锁协议,则对这些事务的并发调度是可串行化的。

以两个并发事务$T_1$和$T_2$为例（多事务可类推）：
根据可串行化定义，事务不可串行化仅可能发生在两种情况：
情况1：$T_1$写数据对象A，$T_2$读/写A；
情况2：$T_1$读/写数据对象A，$T_2$写A。
设$T_1$和$T_2$访问的潜在冲突公共对象为{A1,A2,⋯ ,An}\{A_1,A_2,\cdots,A_n\}{A1​,A2​,⋯,An​}，X={A1,⋯ ,Ai}X=\{A_1,\cdots,A_i\}X={A1​,⋯,Ai​}符合情况1，Y={Ai+1,⋯ ,An}Y=\{A_{i+1},\cdots,A_n\}Y={Ai+1​,⋯,An​}符合情况2。
$\forall x\in X$，$T_1$需Xlock x，$T_2$需Slock x/Xlock x：
①若$T_1$的Xlock x先执行，$T_1$获锁，$T_2$等待。因遵守两段锁协议，$T_1$获X、Y及非潜在冲突对象所有锁后才释放，若$T_2$未获任何潜在冲突对象锁，则$T_1$处理完后$T_2$执行，等价于$T_1$、$T_2$串行；若$T_2$已获部分锁则死锁（死锁不属于不可串行化范畴）。
②$T_2$操作先执行的情况与①对称。
综上，遵守两段锁协议的并发事务调度是可串行化的。

13. 举例说明对并发事务的一个调度是可串行化的,而这些并发事务不一定遵守两段锁协议。

示例：
事务$T_1$：Slock B → Unlock B → Xlock A → Unlock A
事务$T_2$：Slock A → Unlock A → Xlock B → Unlock B

调度执行过程：

$T_1$	$T_2$
Slock B
读B=2
Y=B
Unlock B
Xlock A
	Slock A
	等待
A=Y+1
写回A=3
Unlock A
	Slock A
	读A=3
	X=A
	Unlock A
	Xlock B
	B=X+1
	写回B=4
	Unlock B

该调度执行结果A=3、B=4，等价于$T_1$、$T_2$串行执行结果，是可串行化调度，但$T_1$、$T_2$均未遵守两段锁协议（加锁阶段释放了锁）。

14. 考虑如下的调度,说明这些调度集合之间的包含关系。

• 正确的调度
• 可串行化的调度
• 遵循两段锁(2PL)的调度
• 串行调度

答案：
遵循两段锁(2PL)的调度 ⊂ 正确的调度 = 可串行化的调度；
串行调度 ⊂ 正确的调度。

15. 考虑如下的$T_1$和$T_2$两个事务:

$T_1:R(A);R(B);B=A+B;W(B)$
$T_2:R(B);R(A);A=A+B;W(A)$
①改写$T_1$和$T_2$,增加加锁操作和解锁操作,并要求遵循两段锁协议。
②说明$T_1$和$T_2$的执行是否会引起死锁,给出$T_1$和$T_2$的一个调度并说明之。

答案：
①遵循两段锁协议的$T_1$、$T_2$加解锁操作：

$T_1$	$T_2$
Slock A	Slock B
R(A)	R(B)
Xlock B	Xlock A
R(B)	R(A)
B=A+B	A=A+B
W(B)	W(A)
Unlock A	Unlock B
Unlock B	Unlock A

②$T_1$和$T_2$的执行可能引起死锁。调度示例：

$T_1$	$T_2$
Slock A	Slock B
R(A)	R(B)
Xlock B	Xlock A
等待	等待

说明：$T_1$申请Xlock B后等待$T_2$释放B的锁，$T_2$申请Xlock A后等待$T_1$释放A的锁，双方互相等待，引发死锁。

16. 为什么要引进意向锁?意向锁的含义是什么?

引进意向锁的目的是提高封锁子系统的效率。在多粒度封锁方法中，若无意向锁，系统对数据对象加锁时需检查该对象及所有上下级结点的封锁冲突，效率低；引进意向锁后可简化检查过程。
意向锁的含义：对任一结点加锁时，必须先对它的上层结点加意向锁；对一个结点加意向锁，说明该结点的后裔结点正在被加锁。

17. 试述常用的意向锁(IS锁、IX锁、SIX锁),给出这些锁的相容矩阵。

• IS锁：对一个数据对象加IS锁，表示它的后裔结点拟（意向）加S锁（如对元组加S锁前，需先对其所在关系和数据库加IS锁）。
• IX锁：对一个数据对象加IX锁，表示它的后裔结点拟（意向）加X锁（如对元组加X锁前，需先对其所在关系和数据库加IX锁）。
• SIX锁：对一个数据对象加SIX锁，表示对它加S锁，再加IX锁（SIX=S+IX）。

相容矩阵：

KaTeX parse error: Undefined control sequence: \T at position 4: T_1\̲T̲_2	S	X	IS	IX	SIX
S	Y	N	Y	N	N
X	N	N	N	N	N
IS	Y	N	Y	Y	Y
IX	N	N	Y	Y	N
SIX	N	N	Y	N	N

（注：Y表示相容，N表示不相容）

补充习题及答案

1. 问答题

①意向锁中为什么存在SIX锁,而没有XIS锁?
答案：如果对数据对象加SIX锁，表示对它加S锁，再加IX锁，即对数据对象加S锁，后裔结点拟加X锁。X锁与任何其他类型的锁都不相容，如果数据对象被加上X锁，后裔结点则不可能被以任何锁的形式访问，因此XIS锁没有意义。

②完整性约束是否能够保证数据库在处理多个事务时处于一致状态?
答案：完整性约束能够保证操作后的数据满足某种约束条件，但并不保证多个事务被正确调度，无法保证数据库处于一致状态。

2. 综合题

考虑下面的三级粒度树,根结点是整个数据库D,包括关系$R_1$、$R_2$、$R_3$等,分别包括元组$r_1,r_2,\cdots ,r_{100}$和$r_{101},\cdots ,r_{200}$以及$r_{201},\cdots ,r_{300}$。使用具有意向锁的多粒度封锁方法,对于下面的操作,说明产生加锁请求的锁类型和顺序。
①读元组$r_{50}$
答案：D上加IS锁，$R_1$上加IS锁，$r_{50}$上加S锁。

②读元组$r_{90}$到$r_{210}$
答案：D上加IS锁；$R_1$上加IS锁，$R_2$上加S锁，$R_3$上加IS锁；$r_{90}$到$r_{100}$上加S锁，$r_{201}$到$r_{210}$上加S锁。

③读$R_2$的所有元组,并修改满足条件的元组。
答案：D上加IS锁和IX锁，$R_2$上加SIX锁。

④删除$R_1$、$R_2$、$R_3$中所有元组。
答案：D上加IX锁，$R_1$、$R_2$、$R_3$上加X锁。