《数据库原理与应用》课件第6章

第6章数据库事务管理6.1事务6.2并发控制6.3数据库恢复系统习题6.1事务

DBMS是以事务的方式来管理用户对数据库操作的。事务的主要特点是并发执行，并且在系统发生故障时能够进行恢复。在本章，我们先介绍事务的概念和性质，然后讨论事务的并发控制和数据系统恢复技术。6.1.1事务概念事务(Transaction)是DBMS的最小逻辑工作单位，由一系列数据库操作组成。在RDBMS中，一个事务可以是一个SQL、一组SQL语句或一个完整的程序。事务可以看做是DBMS执行的内部程序，相当于操作系统里的“进程”。但事务跟普通的应用程序是完全不一样的，一个应用程序通常可以包含或不包含，也可以包含一个或多个事务。在DBMS中，用户可以显示地定义事务的开始和结束，也可以由DBMS按缺省规定方式进行划分。例6.1有一个商品销售事务T，销售了一定数量(如10)的某种商品，用X、Y表示该商品的库存量和销售量。其操作如下：

T：

READ(X)；

X:=X-10；

WRITE(X)；

READ(Y)；

Y:=Y+10；

WRITE(Y)；例6.1是一个事务的例子，其中READ(X)表示从数据库读X，WRITE(X)表示向数据库写X(下文也遵循本约定)。在该事务T中，对数据库有4个操作。其中，两个READ表示从数据库中读取数据，两个WRITE表示将数据写回到磁盘数据库物理文件中。6.1.2事务的状态与特性

1．事务的状态事务在执行过程中可分为5个状态：活动、局部提交、成功执行、失败和异常中止。这5个状态的转化关系如图6.1所示。下面对各个状态进行说明。

(1)活动状态。事务在BEGINTRANSACTION(开始事务)之后便进行活动状态。活动状态中事务要执行一系列对数据库的读/写操作及其对数据的处理。注意，此时的“写”数据库存放系统缓存，并未写入物理磁盘。

(2)局部提交。事务在执行完所有语句之后，并不能表示事务也成功执行，只是进行局部提交状态。事务执行结束并不能代表数据已写入磁盘，因此需要将数据按一定顺序写入磁盘，这就是局部提交。

(3)失败状态。事务在执行过程中或局部提交过程中，由于某种原因导致事务执行发生故障，事务就进入失败状态。失败状态的事务对数据库的操作不能进行提交，必须进行撤销。

(4)成功执行。事务在局部提交过程中不发生任何故障，对数据库的操作均已写入数据库物理存储磁盘，事务完全提交成功，事务就“成功结束”。

(5)异常中止。进入“失败状态”的事务必须撤销(即回滚)对数据库的已进行的操作，才不会破坏数据库。在下文，我们会发现数据库的原子性也说明了这一点：事务中的所有对数据库的操作必须全部执行成功。如果有某个数据库操作失败，其他已执行的操作必须进行回滚。事务回滚完所有已执行的数据库操作，数据库恢复到事务开始前的状态，事务异常中止。对异常中止事务分两种情况进行处理。第一种情况是由事务实现程序存在逻辑错误引起的异常中止。对这类异常终止的处理是查检事务实现程序是否存在错误，如果有则进行改正，再重新执行事务。第二种情况是由硬件、运行环境或系统故障引起的异常中止。通常，出现这类异常之后，先检查并排除故障，然后再重新执行事务。

2．事务的ACID性质为保证数据的完整性，DBMS中的事务应具备如下4个性质(简称ACID)：

(1)原子性(Atomicity)。事务中的所有数据库操作是一个整体，不可分割。事务执行时，要么执行所有的数据库操作，要么所有的操作都不执行。事务的原子性保证事务在执行结束时不存在一部分数据库操作被成功执行，而另一部分数据库操作没有成功执行的情况。因此，用户不必担心事务是否完全执行而对数据库完整性造成的破坏。在例6.1中的事务T中，对数据库操作的4个语句，要么全都执行，要么一个也不做。事务的原子性是由DBMS的事务管理子系统来实现的。

(2)一致性(Consistency)。每个单独执行的事务的执行结果应该使数据库从一个一致性状态转换到另一个一致性状态。换句话说，数据库中的数据不会因事务的执行而遭受破坏。事务的一致性可由编写事务程序的应用程序员完成。在例6.1的例子中，事务T执行前后都应该满足X=Y+Z。

(3)隔离性(Isolation)。在有多个事务并发执行时，一个事务的执行不被其他事务所干扰，并发执行的结果应与这些事务以不同顺序执行得到的结果相一致，这称做事务达到了隔离性要求。事务的隔离性是由DBML的并发子系统实现的。在例6.1中，如果T在执行的同时，还有其他事务也正在执行，T的执行不受其他事务所影响，那么表明，事务间是隔离的。

(4)持久性(Durability)。事务的持久性是指数据库中一旦一个事务执行成功，它对数据库中数据的改变是永久的，不受后来对数据库的操作或发生故障所影响。事务的持久性是由DBMS的恢复子系统实现的。事务的持久性是由DBMS的恢复子系统实现的。如例6.1，执行成功了，那么它对数据库的影响是永久的。也就是，销售量增加10，库存量减少10。6.1.3原子性与持久性的实现在前面我们分析了事务产生异常的原因。由于事务应具备原子性，事务对数据库的操作应该是一个整体。事务运行时的异常中断就会造成数据库处于不一致状态。DBMS必须能够将这些未完成的事务从数据库中清除出去，也就是说必须确保事务的原子性：要么执行所有的数据库操作，要么所有的操作都不执行。DBMS通过撤销(Undo)所有异常中断的事务中的数据操作来达到事务的原子性。这要求有机制能够实现事务是如何运行的，对数据库执行了怎样的操作。为了实现这个机制，DBMS将事务对数据库的“写”操作都记录到日志里，当事务执行过程中产生异常需要撤销操作时，通过查询日志得到“写”之前的值，并将这个值重新“写”入数据库。如果在已经结束的事务还没将修改的数据写入磁盘之前，系统发生故障，系统恢复时可以利用日志恢复已经进行的修改，从而保证事务的持久性。事务的原子性和持久性是通过数据库恢复子系统实现的。我们将在6.3节介绍数据库恢复系统。6.1.4并发性与可串行化

1．事务的并发性

DBMS以两种方式来执行多个事务：一种称为串行方式，即一个事务执行完成之后再执行另一个事务；另一种称为并发执行，即多个事务交叉执行对数据库的操作。很明显，并发执行可提高DBMS的执行效率。DBMS是通过对事务的“调度”来执行多个事务的。定义6.1调度是指事务的执行顺序。如果多个事务是依次执行的，称为串行调度。如果多个事务以交叉执行的，称为并行调度。例6.2

仍然以商品库存和销售为例。事务T1是销售一定数量(如10个单位)的商品，事务T2是进货一定数量(如200个单位)的商品。X、Y分别表示该商品的库存量、销售量。图6.2所示是T1和T2串行调度时的情况，其中图6.2(a)所示是先T1后T2的串行调度，图6.2(b)所示是先T2后T1的串行调度。图6.3所示是T1和T2两种并发调度时的情况。图6.2T1和T2的串行调度图6.3T1和T2的两种并发调度串行调度虽然效率低，但总能保持多事务的成功执行的结果是正确的。并发调度可以提高系统执行效率，但执行结果并不总是正确的。在例6.2中，假设T1和T2成功执行之前，X和Y的值分别为100，200。两种调度成功执行后：X的值为290，Y值为210，总数量为500。但在图6.2所示的并发调度中，图6.3(a)所示事务的成功执行结果是：X的值为300，Y的值为210，总数510，比实际数量多了10。图6.3(b)所示事务的成功执行结果是：X的值为290，Y为210，总数量为500，与实际数量相符。由图6.2所示可知，并发调度的结果并不总能保持数据库的一致性，哪如何判断一个并发调度能否保持数据库的一致性呢？“并发事务的可串行化”可解决这一问题。2．事务的可串行化事务的串行调度总能保持数据库的一致性。因此，对于一个并发调度而言，如果它是可串行化的，则该调度在任何处于一致性状态的数据库上的执行结果必须与该调度中的事务按照某个完全串行调度执行的结果相同。在图6.3(a)所示的并发调度不是可串行化的，其执行结果与图6.1所示的两种串行调度结果都不相同，而图6.3(b)所示的并发调度是可串行化的，其执行与T1和T2串行执行相同。因此，这里给出“可串行化”调度的定义。定义6.2

多个事务按某个并发调度进行执行，如果执行结果与这些事务按某种串行执行的结果相同，那么就称这个并发调度是可串行化的调度。多个事务的串行执行方式有多种(n!)，无论按哪种方式执行其结果都可以保证数据库的一致性。通常，我们无法保证事务并发执行的结果一定与指定的哪种串行调度执行结果相同。因此，一个并发调度，只要其执行结果与事务的某种串行调度的结果相同，都是可接受的。6.1.5可串行化的判定可串行性是并发调度正确性的准则。这样，给定一个并发调度，当且仅当它是可串行化的，才认为是正确调度。判定一个并发调度是否可串行化，关键是要找到一个与该并发调度等价的串行调度。下面来讨论与并发调度等价的可串行化：冲突可串行化和观察可串行化。

1．冲突可串行化在一个事务中，对数据库中的数据一致性造成影响的是对数据库进行了操作的语句：READ和WRITE。因此，在下文中，假设事务中只有READ和WRITE语句。定义6.3

假设Si和Sj分别是事务Ti和Tj中的READ和WRITE语句，并且它们在Ti和Tj的一个并发调度中相邻。如果Si和Sj是对同一数据对象进行操作，并且至少有一个是WRITE语句时，称Si和Sj是一对“冲突”语句。否则，称Si和Sj为“非冲突”语句。定义6.3表明，如果Si和Sj是“非冲突”语句，那么交换它们的执行顺利不改变事务对数据库的修改，而“冲突”语句交换执行顺序后会改变事务执行后对数据库的修改：

(1)如果Si和Sj对不同数据对象进行操作，很明显，交换Si和Sj的执行顺序不会改变事务执行对数据的影响，即Si和Sj是“非冲突”语句。

(2)如果Si和Sj对同一数据对象进行操作，但两者都是READ，不会改变数据库的数据，因此，交换Si和Sj的执行顺序不会改变事务执行对数据的影响，即Si和Sj是“非冲突”语句。

(3)如果Si和Sj是对同一数据对象进行操作，两者中只要出现一个WRITE，交换Si和Sj的执行顺利都会改变事务执行对数据库的影响，即Si和Sj是“冲突”语句。图6.4只保留了图6.3所示数据库操作的语句。图6.4(a)所示T1的第1行和T2的第1行都是对X的READ语句，是“非冲突”语句，因而可交换位置。T1的第2行和T2的第2行都是对X的WRITE，是冲突语句，因而，不可交换位置。图6.4仅有READ和WRITE语句的T1和T2的两种并发调度定义6.4

给定两个调度D1和D2，D2是通过交换并发调度D1中的非冲突语句后得到的，那么称D1和D2为“冲突等价”的调度。如果D2与D1中的事务的某个串行调度相一致，那么称D1是“冲突可串行化”的调度。图6.5(a)中，T1的第3，4行是对Y进行操作的，而T2的第1，2是对X进行操作的，因此，可对其进行互换。这样，得到该并发调度的一个等价调度，如图6.5(b)所示。观察该图可以发现，该调度与T1、T2按先执行T1后执行T2进行串行执行等价。因此，该设计是“冲突可串行化”的调度。图6.5一个冲突可串行化的并发调度

2．观察可串行化我们先设图6.5(a)所示的调度为D1，图6.5(b)所示的调度为D2。考察D1和D2，可以发现它们满足以下两个条件：

(1)对于数据对象X的READ，在D1中是T1读的初始值，在D2中也是T1读的初始值；D1中T2读的是T1写入的，在D2中T2读的也是T1写入的；数据对象Y在两调度中都只有T1读了其值。

(2)对于数据对象X的WRITE，在D1中是T2对其进行最后写入，在D2

中也是T2对其进行最后写入；数据对象Y，在两调度中只有T1写了其值。条件(1)保证，在D1和D2中T1和T2读到同样的数据值，在引用数据时保持了数据的一致性；条件(2)保证，在D1和D2中对数据库的修改保持一致性。此时，我们也称D1和D2是“观察等价”调度。更普遍地，可将“观察等价”做如下定义。定义6.5给定两个调度D1和D2，如果D1和D2满足下列3个条件，则称D1和D2是“观察等价”调度：

(1)对于同一数据对象X，如果在D1中是T1读的初始值，在D2中也是T1读的初始值。

(2)对于同一数据对象X，如果在D1中是T1读T2写的X，在D2中也是T1读了T2写的X值。

(3)对于同一数据对象X，如果在D1中是T1对X进行最后的写，在D2中也是T1对X进行最后的写。定义6.6

设D1和D2是两个“观察等价”调度。如果D1是一个并发调度，而D2是个串行调度，则称D1是“观察可串行化”的调度。一个观察可串行化的调度如图6.6所示。图6.6一个观察可串行化的调度定义6.6可以得出“冲突可串行化”的调度一定是“观察可串行化”的调度，但反之不然。在图6.5所示的并发调度与按T1、T2、T3的顺序串行调度等价，因此，该调度是观察可串行化的。但是，很不幸，不能通过交换非冲突语句得到该串行调度，因此，该调度不是冲突可串行化的调度。定义6.4、定义6.5和定义6.6给出了可串行化调度的判定方法，它们帮助我们快速判定一个调度是否是正确的，事务的执行是否会保持数据库的一致性。只有可串行化的调度，我们才认为是正确的调度。6.1.6事务的隔离性的实现事务的隔离性是为了保证事务成功执行结束后对数据库的修改能保持数据库的一致性。在6.1.5节，我们讨论过，一个多事务并发调度是正确的，它的执行结果应该与多个事务串行执行结果是一样的。显然最简单的隔离就是将所有事务都串行执行：先来先执行，一个事务执行完了才允许执行下一个。但这样执行，数据库的效率低下，如两个不同的事务只是读取同一批数据，是完全可以并发进行的。在DBMS中，使用不同隔离级别对并发执行的效果进行控制。事务隔离级别就是对事务并发控制的等级。ANSI/ISOSQL将其分为串行化(SERIALIZABLE)、可重复读(REPEATABLEREAD)、读已提交(READCOMMITED)、读未提交(READUNCOMMITED) 4个等级。为了实现隔离级别数据库通常采用锁(Lock)。一般在编程的时候只需要设置隔离等级，至于具体采用什么锁则由数据库来设置。下面对上述4个隔离等级进行简述：

(1)串行化。所有事务都一个接一个地串行执行，这样可以避免幻读(PhantomReads)。对于基于锁来实现并发控制的数据库来说，串行化要求在执行范围查询(如选取年龄在10到30之间的用户)的时候，需要获取范围锁(RangeLock)。如果不是基于锁实现并发控制的数据库，则检查到有违反串行操作的事务时，需要滚回该事务。

(2)可重复读。所有被SELECT获取的数据都不能被修改，这样就可以避免一个事务前后读取数据不一致的情况，但是却没有办法控制幻读，因为这个时候其他事务不能更改所选的数据，不过可以增加数据，这是因为前一个事务没有范围锁。

(3)读已提交。被读取的数据可以被其他事务修改。这样就可能导致不可重复读。也就是说，事务读取数据的时候获取读锁，但是读完之后立即释放(不需要等到事务结束)，而写锁则是在事务提交之后才释放。释放读锁之后，就可能被其他事物修改数据。该等级也是SQLServer默认的隔离等级。

(4)读未提交。这是最低的隔离等级，允许其他事务看到没有提交的数据。这种等级会导致脏读(DirtyRead)。6.1.7SQL中的事务定义在RDBMS中，定义事务的语法如下：

BEGINTRANSACTION

COMMIT

ROLLBACK一个事务以BEGINTRANSACTION开始，以COMMIT或ROLLBACK结束。如果以COMMIT结束，表示向数据库提交结果，把更新的数据写回到磁盘的物理数据库中，执行成功；如果以ROLLBACK结束，表示事务执行过程中发生了故障，事务不能完整地执行下去，将数据库回滚到事务开始时的状态。

例6.3

用SQL定义下列事务：向供应(商品代码，门店编号，供应数量)插入两条新记录(“002001”，“01”，400)和(“002003”，“03”，50)。

BEGINTRANSACTION

INSERTINTO供应VALUES("002001"，"01"，400)；

INSERTINTO供应VALUES("002003"，"03"，50)；

IF(SQLCODE=0)THEN

COMMIT；

ELSE

ROLLBACK；上面的SQL代码中，SQLCODE是SQL的内部变量，用来表示是否正常执行，若该值为0，则表示对数据库的操作正常结束，则提交(COMMIT)；否则，有异常产生，则回滚(ROLLBACK)。6.2并发控制并发事务在执行过程中，由于事务的隔离性受到破坏，可能产生一些异常问题。下面介绍由于事务隔离性受到破坏时，并发执行可能带来的3个问题(在下面的例子中，设X在事务执行前的初始值都为100)。

1．丢失更新问题例6.4考查图6.7所示的两个事务T1和T2的并发调度。在时间s1～s3，由于只执行了READ(X)的操作，没有执行WRITE(X)操作，数据库中X的值保持不变，仍然为100。在时间s4由于T1执行了WRITE(X)的操作，数据库中X的值就变为90。在时间s5时，数据库中X的值保持为90。在s6时，T2执行了WRITE(X)，数据库中X的值就变成了300。我们发现，T1对数据X的修改(90)被T2对数据X的修改覆盖了，这种情况称为“丢失更新”。丢失更新产生的直接问题是数据的不一致性。在本例中，T1和T2的调度产生的结果应该是X = 290而不是300。图6.7“丢失更新”的并发执行

2．读了过时数据例6.5

在图6.8所示的两个事务T1和T2的并发调度中，T1在时间s1读取了数据库中X的值为100，T2在时间s2读取了数据库中X的值为100。在时间s3，T1对读取的X值进行了修改(-10)，并将修改结果(90)在时间s4写入数据库。在时间s5，T2继续处理在时间s2时读取的X值(为100)。不难发现，其实在时间s5，数据库中X的值已经变成了90。但T2处理的仍然是100，这种数据不一致的原因就是T2读取了“过时数据”。读取“过时数据”造成事务的后续处理不能与数据库中的实际数据保持一致，产生错误信息。图6.8“读过时数据”的并发执行

3．读未提交数据例6.6

分析图6.9所示的T1和T2的并发执行情况。在时间s1～s3，事务T1先读取的数据库中X的值为100，将其减10，并将结果(90)写入数据库。在时间s4，T2读取了数据X的值为90。但在时间s5由于某种原因导致T1发生回滚，这样，X的值应回到初始状态(为100)。但是在T2中处理的X值仍然为90，是T1未提交的数据，这样，数据库中的数据与T2处理的数据就产生了不一致。产生这种情况的原因是，T2在读取T1未提交的数据之后，T1又进行了回滚。在数据库技术中，把回滚事务中产生的对数据库的修改数据，称为“脏数据”。图6.9读未提交数据6.2.1基于锁的协议

DBMS的并发控制子系统可以采取一些措施保证事务的隔离性，从而解决上述问题。常用的方法有两种：封锁法和时间印法。这里，我们先介绍封锁法及其相关协议。

1．排它锁和共享锁常见数据库中的锁有两种：一种是排它锁(X锁)，另一种是共享锁(S锁)。它们的定义如下：定义6.7

如果事务Ti给数据对象O加了X锁，那么其他事务必须等到Ti释放了该X锁之后，才能对O进行加锁。如果事务Ti给数据对象加了S锁，那么其他事务可以对O加S锁，但不能加X锁，要加X锁必须等待所有其他事务均释放了对O的S锁。将使用锁的规则称为协议。使用X锁的规则，称为PX协议，使用S锁的协议称为PS协议。

定义6.8任何需要对数据库中的某个数据对象进行更新操作的事务，必须先获得对该数据对象的X封锁，即执行LOCK_X(O)。如果未获准对X封锁，那么这个事务进入等待状态，一直到封锁成功，事务才继续下去，这就是PX协议。对丢失更新问题(例6.4)可以通过PX协议得到解决。为了便于理解，我们将例6.4中的数据对象X在此改为数据对象O。如图6.10所示，在T1对数据O进行操作之前先对数据对象O加X锁(s1时间)，并加锁成功。同样，T2要对O进行更新操作，也需要获得对O加X锁(s2时间)，由于之前T1已成功获得对O的X锁，因此，T2必须等待(s3～s4时间)，直到T1释放它对O加的X锁(s5时间)之后才能获得对O的X锁(s6时间)。图6.10X锁和PX协议如果事务正常提交，不会造成数据的不一致。但是如果事务在释放对数据对象的X锁之后，出现异常而发生了回滚，就很可能造成数据库中的数据与事务处理中的数据不一致的问题。因此，在PX协议的基础上，又提出了PXC协议。

定义6.9PXC协议规定是指X封锁必须保留到事务终点(COMMIT或ROLLBACK)才释放。

COMMIT或ROLLBACK隐含了释放对数据对象的X锁。因此，X锁不用UNLOCK操作显式地进行解除。不难发现，PX协议和PXC协议可以解决并发执行中造成的3个问题。但是PXC和PX协议过于严格，大量使用会造成并发度的降低，从而影响DBMS的效率。特别是，当只对数据库中的数据只进行读操作时，没必要一定加X锁。下面我们来讨论基于S锁封锁的PS协议和PSC协议。定义6.10PS协议规定任何要对某个数据对象O进行更新操作的事务必须先执行LOCK_S(O)，以获得对O的S锁。如果没有成功获得S锁，那么该事务就进入等待状态，直到成功获得S锁再继续执行下去。对O进行修改前，必须将S锁升级为X锁才能进行修改。对PXC协议，在使用S锁时也有PSC协议。定义6.11PSC协议规定S封锁必须保留到事务终点(COMMIT或ROLLBACK)。图6.11是在例6.4所示的并发执行事务中，采用PS协议进行封锁的结果。从该图可以发现，一个事务(如T1)对某个数据对象(如数据对象O)进行操作之前，需申请S锁。若需要更改数据库里的值，需要将S锁升级为X锁，才能对数据库进行更新。图6.11S锁和PS协议

PX(PXC)和PS(PSC)协议保证了对未提交更新的封锁必须保持到事务终点，但并没有限制其他封锁，因此，其他封锁可以较早地释放。锁释放之后仍然可以申请封锁。也就是说，申请锁和释放锁是混合的，这种方式很容易引起错误。例6.7

在图6.12所示的事务并发调度是符合PX(PXC)和PS(PSC)协议的。很明显在时间s11，T1中使用的数据对象O的值已经是过时的数据了(对应的时间是s2)，造成最后的结果不正确(最后结果是O=300、Y=110，正确的应该是O=300、Y=310)。为了解决上述错误，引入两阶段封锁协议。图6.12非两段式封锁

2．两阶段封锁协议定义6.12在两阶段封锁协议中，每个事务分成前后两个阶段：增生阶段和收缩阶段。在增生阶段只能申请加锁，不能释放锁，所以也称申请封锁阶段；在收缩阶段只能释放锁，不能申请锁，所以也称释放封锁阶段。在两阶段封锁中，事务一开始就进行增生阶段，并根据需要申请对数据对象的加锁，一旦有锁被释放了，那么就进入了收缩阶段。我们把遵循两阶段封锁的事务，称为两阶段事务。根据定义6.12，将图6.12变为符合两阶段封锁协议的并发调度，如图6.13所示。观察该调度可发现，事务T1在第一次释放封锁之前(时间s1～s7)，只是申请加锁，处于T1的增生阶段。一旦释放了一个封锁，该事务不再申请封锁了(时间s7～s8)，只能继续释放锁，处于T1的收缩阶段。同理，事务T2也满足两阶段封锁协议。在整个并发执行过程中，事务中处理的数据始终能与数据库中的数据保持一致，不会产生错误。图6.13两阶段式封锁事务

3．两阶段封锁与可串行化之间的关系在一个调度中，如果所有事务都是两阶段事务，那么这个调度一定是可串行化调度，反之不一定成立，即可串行化调度中的事务不一定是两阶段事务。两阶段封锁是可串行化的充分条件，但不是必要条件。一个调度中，如果存在非两阶段事务，那么这个调度可能是可串行化的，也可能不是可串行化的。

4．锁的实现在DBMS中锁管理器负责数据锁的管理。锁管理器将所有锁汇聚到一起组成一个锁表，这个锁表实际上是一个以数据对象标识为码的哈希表。DBMS中所有事务在申请封锁之前，检查这个锁表，以确定不会对同一个锁多次请求。加锁表中的每一项针对一个数据对象(可以是一页，一个关系，一个记录等)，包括如下属性信息：有多少事务拥有该数据对象的锁、锁的类型(X锁，还是S锁)及一个指向对该数据有封锁请求的事务队列。按照两阶段封锁协议，事务T在对数据库中的某一数据对象

O进行读写之前，必须先获得锁(写为X锁或读S锁)，并将获得的锁保持到T最终提交或者中止。当事务需要对某个数据对象进行加锁时，需要将请求提交给锁管理器。如果请求的是S锁，而当前请求队列为空，而且数据对象没有被加X锁时，锁管理器将同意加锁请求，并更新锁表中与该数据对象相应的数据项(如果之前没有被加S锁，则在锁表中插入该数据对象S锁的事务数目1，如果已被加S锁，则将拥有该数据对象的S锁的事务数目数加1)。如果请求的是X锁，并且没有事务拥有对该数据对象的锁，那么锁管理器同意加锁，并更新锁表中与该数据对象相对应的数据项。其他情况，例如请求的是X锁，但已有事务拥有对该数据对象的锁，加锁不能立即得到满足，加锁请求将被添加到该对象的加锁请求队列中，同时将请求加锁的事务挂起。当事务结束时，会释放所有自己拥有的锁。当某个数据对象的锁被释放时，锁管理器就会更新锁表中与该数据对象相应的数据项，并检查该数据对象的加锁请求队列。如果某事务的请求能被满足，那么该事务就得到锁并被唤醒。显然，如果请求队列中申请的都是S锁，则都能得到满足。6.2.2多粒度锁对于加锁，还有一种特殊机制，称为多粒度锁。多粒度锁能够有效地对不同粒度级别上的对象进行加锁。一个数据库包含若干关系，一个关系中包含许多元组。当事务需要访问某个关系的大多数元组时，应该对整个关系加锁，而不是对所需要的单独元组加锁。这样，其他需要访问该关系的事务，就会被阻塞。如果事务只访问关系中相当少的元组时，那么最好只对这些元组加锁，这样可以提高事务的并发性。可以用多粒度树来表达多粒度封锁的含义。例如，图6.14所示是一棵拥有三级结点的多粒度树。多粒度树中每个结点包含所有孩子结点，孩子结点具有更小粒度的数据对象。事务获得了某个结点上的锁，就意味着获得了该结点所有后代结点的锁。图6.14一棵三级多粒度树除了X锁和S锁，多粒度封锁协议还使用另外两种类型的锁：意向排他锁(IX锁)和意向共享锁(IS锁)。IX锁和S锁和X锁有冲突，IS锁仅和X锁有冲突。使用这两种封锁协议要求事务对某个结点加S(或X)锁，必须先对该结点下的所有后代结点加IS(或IX锁)。这样，如果有事务对某个结点加了S锁，那么其他事务就不能对该结点下的任何后代结点加X锁；同理，如果有事务对某个结点加了X锁，那么其他事务就不能对该结点下的任何后代结点加任何形式的锁了。采用这种机制，保证了当需要某结点S或X锁时，其他事务不会在它的祖先结点上持有会发生冲突的锁。通常，事务需要读取整个关系并修改其中少量元组。也就是说，事务需要获得关系的S锁和IX锁，然后再对其中的某些元组加X锁。为了方便起见，可定义一个新的SIX锁，它在逻辑上等同于持有S锁和IX锁。这样，事务在申请加锁时，获得一个单独的SIX锁来代替S锁和IX锁。多粒度封锁在释放锁时必须以从叶子到根的顺序来释放。为什么这样呢？看一个例子，事务T1从多粒度树根到关系R1的顺序对所有结点加IS锁，对关系R1加S锁，然后释放根结点的锁。另一个事务T2现在可以获得根的X锁，这意味着T2拥有R1的X锁，这与当前T1拥有R1的S锁相冲突。为了确保可串行化，多粒度封锁协议必须和两阶段封锁协议结合起来使用。两阶段封锁协议指出什么时候使用多粒度封锁协议获得锁，什么时候释放锁，这种释放必须按照从叶子到根的顺序进行。在多粒度封锁协议中，一个重要问题是如何确定封锁的粒度。可采用一种称为“锁的提升”的方法来解决这个问题：在事务开始时获得较细粒度锁(如元组级)，然后在事务获得该粒度一定数目的锁之后，再开始获得更高粒度的锁(如关系级)。6.2.3死锁再来看图6.10所示的调度。在时间s6事务T1需要升级对数据对象O的加锁，但此时，T2又拥有数据对象O的S锁，因此，T1只有等待，直到T2释放了对O的S锁。同理，在时间s8事务T2需要升级对数据对象O的加锁，但此时，T1又拥有数据对象O的S锁，因此，T2只有等待，直到T1释放了对O的S锁。这种，T1和T2就会无限期等下去，这种情况称为事务的“死锁”。图6.15所示是另一个死锁的例子。在该调度中，T1在时间s1获得了对数据对象O的S锁，T2在时间s3获得了对数据对象Y的S锁。在时间s5T1请求对数据对象Y加X锁，但此时Y已被T2加了S锁，因此，T1进入等待状态。在时间s6T2请求对数据对象O加X锁，但此时O已被T1加了S锁，因此，T2进入等待状态。这样，T1和T2彼此等待对方释放锁之后才能继续执行，如不采取措施，T1和T2将无限期等待下去，即发生死锁。图6.15一个死锁的例子目前，解决死锁主要采用两种方法：一种是采取一定措施预防死锁产生；另一种是定期检测系统中有无死锁，若有则采取一定的方法解除之。

1．死锁的预防死锁是两个或多个事务已获得了部分数据的锁，然后又请求已被其他事务加锁的数据对象而造成事务间无限期的等待。预防死锁就是要破坏死锁发生的条件。常用预防死锁的方法有两种：一次封锁法和顺序封锁法。

1)一次封锁法预防死锁的一次封锁法要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行下去。图6.16所示是采用一次封锁法对图6.15所示的事务进行加锁的调度，不难发现该调度不会发生死锁。图6.16一次封锁法尽管一次封锁法有效地防止了死锁的发生，但也带来了一些问题：

(1)由于一次将事务中要用到的所有数据对象加锁，降低了系统的并发性；

(2)由于数据库是动态变化的，无法事先精确地确定每个事务所要封锁的数据对象，一般采取扩大封锁范围的方法来满足后来的需要，这在一定程度上也降低了系统的并发性。

2)顺序封锁法顺序封锁法预先对数据库中的数据对象建立封锁顺序，所有事务按照这个封锁顺序来请求对数据的加锁。例如，如图6.16所示，预先规定数据库的数据对象加锁顺序为O，Y，…，那么由于T1对O已经加了S锁，因此，当启动T2时，首先要获得对O的X锁，但此次O已被T1加了S锁，T2就处于等待状态，因此，T2也不会获得对Y的加锁，事务T1可获得对Y的X锁，事务得以继续执行。顺序封锁法的缺点：

(1)由于数据库中数据对象很多，而且不断有新的数据插入和旧的数据修改，因此，维护加锁顺序表代价很大；

(2)事务的执行是动态的，通常无法精确预计要封锁的对象，因此，很难按照规定的顺序进行加锁。上述分析发现，无论是一次封锁还是顺序封锁法都具有明显的不足，在DBMS中解决死锁问题普遍采用的是诊断并解除死锁的方法。

2．诊断并解除死锁

DBMS中有死锁测试程序，该程序可在一定时间间隔内检查并发的事务之间是否发生死锁。如果发生死锁，那么就撤销发生死锁中的一个事务，做回滚操作，并解除它的所有封锁，恢复到该事务的初始状态。这样，就可以把释放出的数据对象的锁分配给其他事务，从而消除了死锁现象，这就是诊断并解除死锁的基本思想。诊断并解除死锁有两种机制：超时机制和等待图机制。

1)超时机制在超时机制中，如果一个事务为获得一个数据对象的锁等待了太长的时间(超过某一预定的时间阈值)，可以认为事务处于死锁状态，可中止该事务。超时机制有个明显的不足——可能误判。因为，有时事务处理时间本来就很长，而并不是处于死锁状态。

2)等待图机制等待图中的结点对应于正处于执行状态的事务，并且当Ti等待Tj释放锁时，存在一条从Ti到Tj的有向边。锁管理器在将加锁请求加到等待队列中时，往图中添加一条边，满足加锁请求时，删除一条边。如果某个时间，图中出现一个回路时，就表明出现了死锁。死锁解决的方法是通过中止循环中一个代价较小的事务并释放其拥有的锁。图6.17描述了图6.15所示的并发调度中的等待图，由于T1、T2间出现了回路，因此，T1、T2发生了死锁，通过中止T1或T2来释放锁，使另一事务得以继续执行。图6.17死锁等待图6.2.4基于时间印的协议上述方法尽管可以解决死锁，但也带来了额外的开销。例如，需要测试程序终止处于运行状态的程序、撤销事务等，死锁是封锁技术带来的问题。解决并发的另一种方法是时间印的方法。时间印不采用封锁技术，因此，不会发生死锁。

1．时间印在事务运行时，都有唯一一个时间标志，称之为时间印。对于事务Ti，我们用Ts(Ti)来表示。时间印可按下列两种方式来实现：

(1)将事务开始运行时的系统时间，作为事务的时间印。

(2)每个事务都有一个逻辑编号，逻辑编号可以是运行事务的顺序编号。如果两个事务T1和T2的时间印分别为Ts(T1)和Ts(T2)，如果Ts(T1)<Ts(T2)，那么系统必须保证产生的调度等价先T1后T2。如果违反了这个顺序，需要中止事务并重新启动。

2．时间印顺序协议为了使用时间印实现并发控制，对每个数据库对象O给定一个读时间印R_Ts(O)和一个写时间印W_Ts(O)。为了保证任何冲突的读和写都能以时间印顺序进行，需要并发事务遵守时间印顺序协议：

(1)在事务T对数据对象O进行读操作时：(i)如果事务T希望读数据对象O，并且Ts(T)<W_Ts(O)，那么这个读操作和最近的写操作间的顺序违反了事务T和写数据对象O的事务间的时间印。这时，需要中止T，再将一个新的更新的时间印分配给T，并重新启动；(ii)如果Ts(T)≥W_Ts(O)，T可以读O，并且R_Ts(O)的值设成原来的R_Ts(O)和Ts(T)之间的较大者。

(2)在事务T对数据对象O进行写操作时：(i)如果Ts(T)<R_Ts(O)，那么T产生的O值应在以前的时间内写入，这已不可能。因而，应该拒绝T的写操作，中止T，将一个新的更新的时间印分配给T并重新启动T；(ii)如果Ts(T)<W_Ts(O)，那么T试图写过时的O值。这时，也应拒绝T的写操作，中止T，将一个新的更新的时间印分配给T并重新启动T；(iii)否则，执行写操作，并置W_Ts(O)为Ts(T)。例6.8在图6.18中，T2在T1之后启动，即Ts(T2)>Ts(T1)，结果将在时间s6使事务T1的写失败，T1将重新启动，这是并发执行过程中的丢失更新问题。我们不难发现时间印顺序协议具有如下特点：

(1)在解决冲突操作时，是按时间印顺序处理的，因此时间印顺序协议能保证调度是可串行化的。

(2)在处理冲突的操作时，采用重新启动方式，因此没有事务处于等待状态，不会产生死锁。

(3)遵循时间印顺序协议的调度，可串行化调度。图6.18一个基于时间印的并发控制6.2.5多版本控制多版本并发控制是另外一种使用时间印(事务启动时分配的)来保证可串行化调度的方法。该方法通过对每个数据对象维护具有不同写时间印的若干版本，并允许事务T读取时间印Ts(T)之前最新的版本。这样可以保证事务在读数据对象时不用等待。如果事务Ti希望写一个数据对象，必须保证该数据对象没有被满足于Ts(Ti)<Ts(Tj)的事务Tj读过。这是因为，在这种情况下，如果允许Ti写Tj读过的对象，那么考虑到事务的可串行化，Ti更新的结果应该对Tj可见。但是，实际上Tj中处理的还是以前的数据对象，并不是Ti的更新结果，这就不能保证事务的可串行化。为了解决上述问题，每个数据对象必须具有一个读时间印。当一个事务读某个数据对象时，要对读时间印和执行启动的事务的时间印进行比较，并将数据对象的时间印的值更新为两者中较大的一个。如果Ti希望写数据对象O，并且Ts(Ti)<R_Ts(O)，Ti将被中止，并重新启动，以获得较大的时间印。否则，Ti对数据对象O进行修改，并将数据对象O的写时间印设置为Ts(Ti)。6.3数据库恢复系统

DBMS中采取了各种措施来防止数据库的安全性和完整性被破坏，保证并发事务的正确执行，但是由于系统中的软硬件故障、介质故障及人为故障会造成事务的非正常中止，影响事务的正确性，有时还会造成数据库的破坏，DBMS必须具有把数据库从错误状态恢复到某一已知的正确状态的功能，这就是数据库的恢复，DBMS中完成恢复功能的子系统称为数据恢复子系统。数据恢复子系统是DBMS的重要组成部分，它采取的恢复技术的可靠性，影响着整个系统的可靠性，是衡量系统性能好坏的重要指标。6.3.1故障与恢复概述

1．故障的种类数据库系统在运行过程中,可能会遇到各种各样的故障，有些会使数据库中数据遭受破坏。这些故障大致可分为以下几类。

1)事务故障事务故障指由于事务执行过程中发生的逻辑错误或系统错误造成事务的执行失败。其中逻辑错误包括数据输入错误、内存溢出、资源不够等；系统错误，如死锁等。事务故障意味着事务没有达到预期的终点(COMMIT或ROLLBACK)，此时，数据库可能处于不正确状态。恢复程序要在不影响其他事务运行的情况下，强行回滚该事务，即撤销该事务已经做出的任何对数据库的修改，使数据恢复到该事务执行前的状态，这一恢复操作称为事务的撤销(UNDO)。

2)系统故障系统故障是指由于硬件故障、软件错误等造成系统停止运转的任何事件，使得系统要重新启动。这类故障影响正在运行的所有事务，但不会造成对数据库的破坏。这时，内存中的数据特别是数据库缓冲区中的内容都会丢失，所有未结束的事务都非正常终止。在发生故障时，有一些尚未完成的事务的结果可能已送入物理数据库，破坏了数据库的一致性，需要清除所有这些事务对数据库的所有修改。在系统重启后，所有此类事务应进行回滚，强行撤销(UNDO)。有些已完成的事务可能有一部分数据保存在缓冲区中，还未来得及存入物理数据库中，系统故障导致这些事务对数据库的修改产生丢失，因此使数据库处于不一致状态。对于这类事务，恢复子系统必须在系统重新启动时，需要重做(REDO)所有已提交的事务，以将数据库真正恢复到一致状态。

3)介质故障介质故障指的是诸如磁盘损坏、磁头碰撞、瞬时强磁场干扰等外存故障，这类故障破坏数据库或部分数据库，并影响正在存取这部分数据的所有事务。这类故障的特点是发生的可能性小，但破坏大。这类故障的恢复需要将存放在其他磁盘或第三级介质中的内容拷贝到数据库中。

2．数据恢复实现数据恢复的基本原理是冗余。也就是说，数据库中的任何不正确的或被破坏的数据可以根据备份在其他地方的冗余数据来重建。建立冗余最常的方法是数据备份和登记日志。

1)数据备份数据备份指的是数据管理员将数据库复制到磁盘、磁带或其他存储介质上保存起来以备将来使用的过程。通过备份得到的数据库称为备份数据库(或后备副本)。当数据库遭受破坏后，可将备份数据库载入DBMS，使数据库还原至最后一次备份时的状态。如果要将数据库恢复到故障发生时的状态，那么需要重新执行数据库备份点之后到故障发生点之前执行的事务，图6.19说明了这个过程。数据备份有多种方式。按备份时是否允许执行事务，可分为静态数据备份和动态数据备份。静态数据备份在数据备份过程中，不允许应用程序访问数据库，数据库中没有正在执行的事务，数据库的所有事务均已提交。动态数据备份在数据备份过程中，允许应用程序正常访问数据库，可以有事务同时执行。图6.19数据库备份和恢复由于静态数据备份时所有事务均已完成，可以保证备份数据一致性，因此在恢复时直接将备份数据库载入数据库管理系统就可以了。静态备份的明显缺点是在进行备份时需要停止应用程序对数据库的访问，降低了数据库的可用性，有时会给用户带来很大不便。由于动态备份允许在备份时有事务正在运行，备份时不用停止应用系统，提高了数据库的可用性。但不足之处是不能总保持备份的数据是一致的。因此，需要建立日志将备份过程中各个事务中发生的数据操作记录下来。在数据恢复时，将备份数据库载入之后，结合日志文件中对备份结束时的事务活动记录，对事务执行撤销(UNDO)或重做(REDO)，以实现满足一致性需求的数据库。按每次备份时是备份全部数据库，还是备份上次备份后产生的数据，将数据库备份分为海量备份和增量备份。海量备份是指每次备份不加选择，备份整个数据库。增量备份指仅备份上次备份后数据库中产生的新的可变化的数据。海量备份由于是备份整个库，实现起来比较简单，数据恢复只要将一个备份转入数据库就可以了，比较容易完成。也正是因为这个原因，导致海量备份的数据量过大，备份代价比较高。增量备份除第一备份外，每次仅备份数据库中上次备份有差异的部分，备份的数据量相对较小，执行代价较小。但其恢复时需要以前备份的所有备份数据库，没有海量备份方便。无论是静态数据备份还是动态数据备份，既可以是海量备份，也可以是增量备份。但由于数据库备份是很耗时的动作，同时也需要较大的资源代价，因此，应该根据实际应用需求选取备份方式。

2)日志文件

DBMS将事务对数据库的修改信息以一定的数据结构记录下来，形式“日志文件”。日志文件记录事务对数据对象的每个操作，称为“日志”记录。从物理上说，日志文件是保存在稳定存储介质中的记录文件，一般与数据库文件分离，并且能避免系统故障造成的崩溃。将日志文件备份到不同磁盘上形成多个版本，可以保证日志不被损坏。通常一个事务的日志包括以下内容：

<Ti，START>表示事务Ti开始。

<Ti，Oj，V_new，V_old>表示事务Ti对数据对象Oj进行了修改，V_new表示修改前的值，V_old表示修改后的值。

<Ti，COMMIT>表示事务Ti执行提交。

<Ti，ABORT>表示Ti中止执行。数据库在写数据时，将向磁盘保存日志文件，后向数据库写数据。这样保证所有对数据库的操作均记录在日志中。在撤销(UNDO)事务时，对于修改操作，根据记录<Ti，Oj，V_newj，V_oldj>，采用V_oldj替代V_newj，使数据库恢复到Ti启动时的状态。6.3.2基于日志的恢复本节介绍两种使用日志进行数据库恢复的技术。

1．写日志优先协议事务在把数据写入到磁盘上的数据库文件之前，必须先将对数据修改的日志写入稳定存储介质中，这就是写日志优先协议。这个协议确保在事务未完成前系统发生故障或事务异常中止时，修改的信息只写入日志，尚未写入磁盘，这时可忽视日志中的信息。在发生故障后，DBMS的恢复子系统可以从日志文件中判断哪些事务需要重做。重做就是将事务要更新的数据对象Oj设置为<Ti，Oj，V_newj，V_oldj>中的新值V_newj，即可以利用日志记录在系统发生故障后重新写入修改后的值，以保持数据库的一致性。

2．立即写数据库协议允许事务还没完成的情况下，向数据库文件执行写操作，向磁盘写入新的值。在数据库中，把未完成的事务写的数据修改称为“未提交的修改”。在故障后的恢复中，必须撤销(UNDO)这些事务，用日志记录中的旧值替代新值。立即写数据库协议中，在事务执行写操作时，先把相应的日志记录写入日志文件，然后立即执行写操作,把数据写入磁盘。在发生故障后，可以利用日志记录恢复数据库的一致性。事务分两大类：UNDO和REDO。UNDO(Ti)：将事务T修改的数据对象设置为日志记录<Ti，Oj，V_newj，V_oldj>中的旧值V_oldj；REDO(Tk)：将事务Tk修改的数据对象设置为日志记录<Ti，Oj，V_newj，V_oldj>中的新值V_newj。哪些事务需要UNDO，哪些事务需要REDO呢？可以用下列规则进行判断：

(1)如果日志文件中包含事务Tk的开始记录<Tk，START>，但没结束记录<Tk，COMMIT>，那么应撤销事务Tk。

(2)如果日志文件中既有事务Tk开始记录<Tk，START>又结束记录<Tk，COMMIT>，那么事务Tk应重做。6.3.3恢复技术根据前面对数据库备份和日志的讨论，可以发现在数据库系统发生故障后，可以利用备份数据库和日志文件将数据库恢复到事务开始前的正确状态。现在来介绍在数据库恢复过程中用到几个技术。

1．UNDO与REDO

1) UNDO事务在6.3.2节，我们指出如果日志文件中包含事务的开始记录<Tk，START>，但没结束记录<Tk，COMMIT>，那么应撤销(UNDO)事务Tk。按如下步骤可实现对Tk的撤销：

(1)从日志文件的尾部向头部反向扫描日志文件，查找事务Tk的数据更新操作。

(2)对遇到的Tk中的数据更新操作做逆向操作：对于修改操作，将修改前的值写入数据库；对于插入操作，将相应记录从数据库删除；对于删除操作，则将被删除的记录插入数据库。

(3)继续反向扫描日志文件，查找该事务的其他更新操作，并做与(2)相同的处理，直到读到<Tk，START>。

2) REDO事务相对UNDO事务，REDO事务比较简单。其基本操作步骤是正向扫描日志文件，查找事务Tk的更新操作，遇到Tk的数据更新操作重新执行，直到读到<Tk，COMMIT>为止。

2．事务回滚回滚事务(ROLLBACK)是事务结束的一种方式，它表示事务由于某种原因导致对数据库的操作失败，需要采用一定手段让数据库回退到事务开始前的状态。事务撤销是由于故障造成事务未执行完成(即没COMMIT，也没ROLLBACK)，在数据库重新启动后，通过执行反向操作，使数据库恢复到故障前的正确状态。可见，事务回滚和事务撤消在概念上是不同的。但是，在基于日志上的事务回滚和事务撤销上却是相似的。在事务Tk失败后需要回滚时，反向扫描日志文件，