2.2　调度

事务的并发执行需要保证同一事务中的操作顺序是固定不变的，但不同事务的操作可以交叉执行，这种操作的交叉执行可能会破坏数据的一致性状态。如果要保证事务并发执行的正确性，可以要求所有的事务串行执行，也就是逐个执行，事务的执行不存在交叉，我们称这种调度为事务的串行调度。假设有N个事务并发执行，那么就存在N！种串行调度。

串行调度能够保证不破坏数据库的一致性状态，但是，串行调度并不是最好的调度策略。随着CPU核数的不断增加，事务之间的并发执行越来越重要，串行调度很难充分利用CPU资源。为了提高计算资源的利用率、提高数据库的执行效率，事务必须要并发执行。

事务并发执行会引发各种异常现象，事务的调度就需要在并发执行的基础上避免这些异常现象的产生。如果存在这样一种调度：事务之间的操作存在交叉执行，但是最终的执行结果和某个串行调度的执行结果相同，那么这个调度被称为可串行化调度。

为了方便研究，我们把事务中的操作抽象成读操作和写操作，事务1中对A对象的读操作和写操作可以如下表示。

• R1(A)：事务1中对A对象做读操作。

• W1(A)：事务1中对A对象做写操作。

根据读写操作的顺序不同，又可以抽象出以下4种操作序列。

• 读-读操作：读操作和读操作是不冲突的，读操作不会改变元组的值，交换相邻读操作的顺序不会影响读取的结果，例如R1(A)R2(A)和R2(A)R1(A)的执行结果是等价的。

• 读-写操作：读操作读到的值会被写操作修改，因此它们之间的顺序不能随意调换。也就是说，读、写操作是冲突的，相邻的读、写操作不能交换顺序。

• 写-读操作：和读-写操作类似，写操作的值可能会被读操作读取，因此它们之间也是冲突的，相邻的写、读操作不能交换顺序。

• 写-写操作：两个写操作的顺序不同，会对这个调度的执行结果有影响，因此两个相邻的写操作是冲突的。

需要注意的是，我们假设以上4种操作序列中读写的都是相同的对象。这样可以得到冲突（Conflict）的定义：如果两个分属于不同事务的操作中有一个是写操作，且两个操作针对的是同一个数据库对象，那么这两个操作是冲突的。

冲突的操作不能交换执行顺序，不冲突的操作可以交换执行顺序（根据调度的定义，同一事务内的操作顺序是固定的，因此不考虑同一事务的操作交换执行顺序），因此可以通过交换不冲突的操作来获得等价的执行序列。假设有多个事务并发执行，一个调度S通过交换其中不冲突的操作得到一个等价的新的调度S'，就称S和S'是冲突等价的。

如图2-8所示，调度S中的R1(x)和R2(x)是不冲突的，因为它们都是读操作；R1(x)和R2(y)也是不冲突的，因为它们操作的不是同一个数据库对象（当然也因为它们都是读操作）；R1(x)和W2(y)也是不冲突的，因为它们操作的不是相同的数据库对象，因此可以把R1(x)通过3次交换，交换到S'调度的尾部。

图2-8　冲突等价的示例

如果一个调度和某一个串行调度是冲突等价的，那么这个调度就是冲突可串行化的。假设有一组事务，如果两个事务中含有冲突的操作，那么可以根据冲突操作的先后关系画出一条边。如果将事务看作图的顶点，那么这组事务就可以按照冲突操作的先后顺序构成一个优先图。如果优先图中没有环，则认为这一组事务的当前调度是冲突可串行化的。

如图2-9所示，有事务序列T1和T2，在并发执行的情况下存在调度S和调度S'。从图中可以看出，调度S中的R1(x)和W2(x)是冲突的，因此有一条T1->T2的边；W1(y)和R2(y)是冲突的，也有一条T1->T2的边；可以看出调度S的优先图中没有环，因此调度S是冲突可串行化的。而调度S'中R2(y)和W1(y)是冲突的，因此有一条T2->T1的边；R1(x)和W2(y)是冲突的，有一条T1->T2的边；可以看出调度S'是有环的，因此调度S'不是冲突可串行化的。

图2-9　冲突可串行化示例