数据库并发控制的一个重要概念就是Serializability[可串行化]，先上两个教科书的解释

We can ensure consistency of the database under concurrent execution by making sure that any schedule that is executed has the same effect as a schedule that could have occurred without any concurrent execution. That is, the schedule should, in some sense, be equivalent to a serial schedule. Such schedules are called serializable schedules. – Database System Concepts 6th Edition

多个事务[Transaction]的并发执行是正确的，当且仅当其结果与按某一次串行地执行这些事务时的结果相同，称这种调度策略为可串行化的调度。–数据库系统概论第四版

其实两本书说的是一个意思，就是无论何种并发操作，其结果只要是和某一种串行操作的结果一样，那么我们就说这种并发操作的调度是可串行的。举个例子:

像图1一样，Txn1的操作都只行完，然后在执行Txn2，就是一种Txn1和Txn2的串行操作调度[The schedule are serial]。当然，先执行Txn2再执行Txn1也是一种串行。

但是，在数据库执行事务操作的时候不一定都是串行的[应该说大部分的时候都不是串行的]，如果两个以上的txn同时发生，那么数据库就是并行的执行他们，在这个过程中，txn基本上不会是串行操作。比如图2和图3都并发操作调度不是串行操作调度。但是图2的运行结果和图1的结果是一样的，所以图2的并行化调度就是可串行调度的，但是图三的结果和Txn1->Txn2或者Txn2->Txn1的结果都不一样，所以图3的并行化调度就不是可串行的。

Conflict Serializability

We say that I and J conflict if they are operations by different transactions on the same data item, and at least one of these instructions is a write operation. – Database System Concepts 6th Edition

冲突操作指的就是不同事务对于同一个数据的读写操作[read-write]和写写操作[write-write]，如果是读读操作[read-read]当然是没有问题的，也就不是冲突操作。冲突操作的执行顺序使不能更改的，先读后写和先写后读的结果往往是不一样的，更改两个以上写操作的顺序甚至会带来严重的错误。

If a schedule S can be transformed into a schedule S’ by a series of swaps of nonconflicting instructions, we say that S and S’ are conflict equivalent. We say that a schedule S is conflict serializable if it is conflict equivalent to a serial schedule. – Database System Concepts 6th Edition

一个调度S在保证冲突操作的次序不变的前提下，通过交换非冲突操作的次序得到另一个调度S’，同时如果S’是可串行的，那么我们就说S是一个冲突客串行化的调度。一个调度是冲突可串行化的，那么它一定是可串行化的调度。

还是举例说明:

上图左一，read(A)-write(A), read(B)-write(B), write(A)-write(A), write(B)-write(B)都是冲突操作，但是read(A)-read(A),read(A)-read(B),read(A)-write(B)都不是冲突操作。所以在左一图中，Txn1的read(A)和Txn2的write(B)并不是冲突操作，所以可以交换这两个操作的顺序，得到上图左二。同理，交换Txn1的read(B)和Txn2的read(A)，交换Txn1的write(B)和Txn2的write(A)，交换Txn1的write(B)和Txn2的read(A)，可以得到左三图。此时左三就是一个串行化的调度方式，如果我们忽略具体操作，它和图一的调度是一样的，所以我们说上图左一的调度方式是一个冲突可串行化调度[conflict serializability]因为通过交换非冲突操作的执行顺序可以得到一个可串行化的调度方式。最后图右一，因为read(Q)-write(Q)-write(Q)都是冲突操作，所以没法进行非冲突操作交换，同时也无法等价于Txn3->Txn4或者Txn4->Txn3这两个串行化操作方式任何一个的结果，所以图右一不是冲突可串行化。

Precedence Graph

一个简单的判断conflict serializablitiy的方法就是precedence graph，用一组边和点来表示事务的执行关系，比如如果以下三种中任何一种顺序，则有一边对应的边。

  1. Txn i executes write(Q) before Txn j executes read(Q)
  2. Txn i executes read(Q) before Txn j executes write(Q)
  3. Txn i executes write(Q) before Txn j executes write(Q)

所以如果在precedence graph中存在环，则这个并发操作调度不是conflict serializability的，如果不存在环，则这个并发操作调度是conflict seriablizability。