|
|
|
数据库系统必须控制事务的并发执行以保证数据库处于一致性状态。
|
|
|
|
|
|
多个事务的并发执行是正确的，当且仅当其结果与某一次序串行地执行它们时的结果相同，称这种调度策略是可串行化的调度（serializability schedule）。
|
|
|
|
可串行性是并发事务正确性的准则，按这个准则规定，一个给定的并发调度，当且仅当它是可串行化的才认为是正确调度。
|
|
|
|
|
|
冲突（conflict）：当Ii和Ij是不同事务在相同的数据项上操作的命令，且至少有一个是write命令时，则称Ii与Ij是冲突的。
|
|
|
|
考虑某调度S中含有分别属于事务Ti、Tj的两条命令Ii、Ij（i≠j）。若Ii、Ij分别访问不同的数据项，则交换Ii、Ij的执行次序不会影响调度执行的结果。若Ii、Ij访问相同的数据项，则Ii、Ij的执行次序可能会影响调度执行的结果。在此只讨论read和write命令在以下四种情况时Ii、Ij是否可交换：
|
|
|
|
（1）Ii=read（D），Ij=read（D）。在调度S中，Ii与Tj读到的是相同的数据D值，交换Ii、Ij的执行次序不会影响执行的结果。
|
|
|
|
（2）Ii=read（D），Ij=write（D）。在调度S中，若Ii先于Ij执行，那么Ii没有读到Ij写回的D值，可见Ii、Ij的执行次序是非常重要的。
|
|
|
|
（3）Ii=write（D），Ij=read（D）。在调度S中，Ii、Ij的执行次序是非常重要的，其原因与（2）类似。
|
|
|
|
（4）Ii=write（D），Ij=write（D）。由于Ii、Ij都是写操作，Ii、Ij的执行次序对Ii、Tj没有影响，但是，若调度S中的下一条命令是read（D），那么读取的值会受到影响，因为数据库中只保留了后一条write命令写入的值。
|
|
|
|
等价调度：设Ii与Ij是调度S的两条连续的命令，若Ii与Ij是不同事务的命令且不冲突，则可以交换Ii与Ij的顺序得到一个新的调度S*。我们称S与S*是等价的。
|
|
|
|
|
|
|
|
例如，考虑上图（a）调度S3，由于T1的write（A）与T0的read（B）不冲突，可以将T1的write（A）与T0的read（B）的执行次序交换，得到另一个等价调度S5，如下图所示。
|
|
|
|
|
|
|
|
|
|
①T0的read（B）与T1的read（A）执行次序交换。
|
|
|
|
②T0的write（B）与T1的write（A）执行次序交换。
|
|
|
|
③T0的write（B）与T1的read（A）执行次序交换。
|
|
|
|
经过上述一系列交换后得到的是一个如下图（a）所示的串行调度S1。这也说明了调度S5等价于一个串行调度，所以是一个正确的调度。请思考为什么调度S4是一个错误的调度。
|
|
|
|
|
|
|
|
冲突等价（conflict equivalent）：如果调度S经过一系列非冲突命令交换成S*，则称S与S*是冲突等价的。
|
|
|
|
冲突可串行化（conflict serializable）：若调度S与一个串行调度S*冲突等价，则S是冲突可串行化的。
|
|
|
|
|
|
在设计并发控制机制时，必须证明该机制产生的调度是否为可串行化的。为了确定一个调度S是否可串行化可以通过S构造一个有向图，也称优先图（precedence graph）。该图由G=（V，E）组成，其中，V是一个顶点集，由所有事务组成；E是一个边集，由满足下述三个条件的边Ti→Ij组成：
|
|
|
|
（1）在Ij执行Read（A）之前，Ti执行Write（A）。
|
|
|
|
（2）在Ij执行Write（A）之前，Ti执行Read（A）。
|
|
|
|
（3）在Tj执行Write（A）之前，Ti执行Write（A）。
|
|
|
|
如果优先图中存在边Ti→Tj，则任何等价于S的串行调度S'中，Ti必出现在Tj之前。
|
|
|
|
例如，调度S1（参见上图（a））优先图如下图（a）所示，图中只有一条边T0→T1，因为T0的所有命令均在T1之前执行；调度S2（参见上图（b））优先图如下图（b）所示，图中只有一条边T1→T0，意味着T1的所有命令均在T0之前执行。
|
|
|
|
|
|
|
|
但对调度S4（参见下图（b）），其优先图如上图（c）所示，由于T0执行Read（A）先于T1执行Write（A），所以优先图中有一条边T0→T1；又因为T1执行Read（B）先于T0执行Write（B），所以优先图中有一条边T1→T0。
|
|
|
|
|
|
|
|
如果调度S的优先图中有环，则调度S是冲突不可串行化的；如果图中无环，则调度S是冲突可串行化的。
|
|
|
|
可见，要判定冲突是否可串行化，首先需要构造有向图，然后调用环检测算法进行判定。有关环检测算法可参见相关书籍。
|
|
|
