|
|
知识路径： > 数据库技术 > 事务管理 > 数据库的并发控制 > 并发操作、并发调度与并发控制 > 并发调度的可串行性 >
|
|
相关知识点：3个
|
|
|
|
|
在设计并发控制机制时，必须证明该机制产生的调度是否为可串行化的。为了确定一个调度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是冲突可串行化的。
|
|
|
|
可见，要判定冲突是否可串行化，首先需要构造有向图，然后调用环检测算法进行判定。有关环检测算法可参见相关书籍。
|
|
|
