事务的调度
在一个支持并发的 DBMS 系统中，同一时刻可能存在多个事务正在被执行，则它们的执行顺序被称为 调度（Schedule） 。如果这些事务是按顺序一个一个的被执行，则这种调度被称为 串行调度（Serial Schedule） 。如果有 n 个事务，则有 n! 种不同且有效的串行调度。如果这些事务是交叉执行的，则这种调度被称为 非串行调度（Non-serial Schedule） 。而对来自全部事务的子操作进行调度，最终的结果会远远大于 n!。
等价调度
对于等价的两个调度而言，它们最终产生的数据库状态一定是一致的，反之不然 （即两个不等价的调度，也可能偶然的产生相同的最终状态） 。以下是两种的判定等价调度的方式。
冲突等价（Conflict Equivalence）
为简化问题的分析，可以将所有数据库的操作抽象为 读 和 写 这 2 种最基本的操作，假设有 T1 和 T2 两个事务，a 是 T1 事务中的一条操作，b 是 T2 事务中的一条操作，a 和 b 都会对相同的数据项 D 进行读或写，有如下 4 种情况：
a = read(D)，b = read(D)：- a 和 b 的执行顺序是无关紧要的，即 a 和 b 是不冲突的；
- 在进行调度时交换 a 和 b 的执行顺序对最终的结果没有影响；
a = read(D)，b = write(D)：- a 和 b 的执行顺序是重要的，即 a 和 b 是冲突的；
- 在进行调度时交换 a 和 b 的执行顺序会影响最终的结果，比如：
- 先 b 后 a，之后再次执行一个 a 操作，此时事务 T1 两次读取的结果是一致的；
- 先 a 后 b，之后再次执行一个 a 操作，此时事务 T1 会发现两次读取的结果不一致；
- 先 a 后 b，之后事务 T2 发生回滚，此时 T2 的回滚不会影响事务 T1；
- 先 b 后 a，之后事务 T2 发生回滚，此时 T2 的回滚会导致事务 T1 处理了一个脏数据；
- 产生上述问题的根本原因在于并发事务之间的隔离性不足，一个事务可以读取其他事务未提交的数据；
a = write(D)，b = read(D)：- 和上一种情况是完全对称的操作；
a = write(D)，b = write(D)：- a 和 b 的执行顺序是重要的，即 a 和 b 是冲突的；
- 在进行调度时交换 a 和 b 的执行顺序会影响最终的结果，比如：
- 先 a 后 b，事务 T2 的写操作会覆盖事务 T1 的写操作，使得事务 T1 的更新丢失；
- 先 b 后 a，同理会导致事务 T2 的更新丢失；
- 先 a 后 b，之后事务 T2 发生回滚，此时 T2 的回滚不会影响事务 T1；
- 先 b 后 a，之后事务 T2 发生回滚，此时 T2 的回滚会导致事务 T1 的更新丢失；
- 产生上述问题的根本原因在于并发事务之间的隔离性不足，一个事务的更新覆盖了其他事务未提交的更新；
可以发现，只要 a 和 b 有一个是写操作，a 和 b 就是冲突的，而交换了 a、b 执行顺序的两个调度就是不等价的。所以对于不同事务中的两个操作而言：
- 如果两个操作作用于相同的数据项，且存在一个写操作，则这两个操作是冲突的；
- 如果两个操作作用于不同的数据项，或它们是作用于相同数据项的两个读操作，则这两个操作是不冲突的；
通过交换调度 S 中的非冲突操作，就可以将 S 转换为另一个冲突等价 的调度 S'。换而言之，如果两个调度中所有冲突操作的执行顺序相同，则这两个调度就是冲突等价的。
视图等价（View Equivalence）
视图等价是另一种判定调度等价的方式。虽然视图等价的判定更为宽松，它不要求所有冲突操作的顺序与某个串行调度的相同，也能保证最终状态的一致。但由于其算法复杂度的限制（属于 NPC 问题），导致应用价值不高。
调度的可串行化
可串行化的概念最初是由 Kapali Eswaran 等人提出的，尽管当时用的并不是这个名称，当时的论文《The Notions of Consistency and Predicate Locks in a Database System》还证明了 两阶段封锁协议 ；
可串行化（Serializability） 指的是多个事务并发执行时的结果与按某种顺序串行执行的结果一致，需要注意的是：
- 可串行化是针对调度而言的：多个事务并发执行时，其中某些调度可能是可串行化的，而剩余的不是。通过检查该调度的“冲突图”是否有环就可以判断出它是否可串行化；
- 全部调度均可串行化是针对并发控制机制而言的 （比如两阶段封锁协议、时间戳排序协议、MVCC） ：即该并发机制能否保证可能出现的全部调度都是可串行化的。如果某个并发机制可以保证，那么多个事务并发执行时，整个数据库表现的就像任意时刻只有一个事务在执行，所以也就不存在隔离性所面临的相互干扰问题，这也是数据库最高的隔离级别；
和等价调度的判定方式一致，也有两种判定某个非串行调度和某个串行调度等价的方式。
冲突可串行化（Conflict Serializability）
- 如果调度 S 与某个串行调度是 冲突等价 的，则称 S 为 冲突可串行化 的调度；
- 冲突可串行化的判定算法：
- 将调度 S 构造成一个有向图，有时也被称为 冲突图（Conflict Graph） 或 优先图（Precedence Graph） ：
- 每个顶点都是一个事务；
- 有向边意味着两个事务存在数据竞争，边的方向表示了两个操作存在依赖关系，必须一先一后的被执行。如果调度中，事务 T1 的某个操作与事务 T2 的某个操作发生冲突，并且 T1 的操作在 T2 的操作之前执行，那么图中就存在一条从 T1 -> T2 的有向边，即满足以下任意条件之一：
- T1 先执行 write(D)，T2 后执行 read(D)；
- T1 先执行 read(D)，T2 后执行 write(D)；
- T1 先执行 write(D)，T2 后执行 write(D)；
- 接着只需要判断有向图是否存在环即可，无环表示 S 是冲突可串行化的，有环表示不是，因为有向无环图总是可以通过拓扑排序生成一个串行序列，虽然结果可能不唯一，但每种结果都恰好对应着一种可能的串行调度，而这些结果都是和 S 冲突等价的串行调度 （其中环检测算法的时间复杂度为 O(n2)） ；
- 将调度 S 构造成一个有向图，有时也被称为 冲突图（Conflict Graph） 或 优先图（Precedence Graph） ：
- 冲突可串行化的判定方式是比较严格的，它是调度可串行化的充分非必要条件；
视图可串行化（View Serializability）
- 类似的，如果调度 S 与某个串行调度是 视图等价 的，则称 S 为 视图可串行化 的调度；
- 由于算法的低效，所以这里没有给出视图可串行化的判定算法；
- 视图可串行化也是调度可串行化的充分非必要条件；
两种方式的比较
冲突可串行化和视图可串行化都是调度可串行化的充分非必要条件，但冲突等价可串行化调度一定是视图可串行化的，反之不然；
- 由于视图等价算法复杂度的限制，所以 DBMS 通常会采用冲突可串行化作为并发控制的标准，而可串行化通常指的就是冲突可串行化；
