目录

冲突可串行化

指令的顺序

冲突指令

冲突等价

冲突可串行化

优先图(precedence graph)

冲突可串行化判定准则

与冲突可串行化等价的串行顺序

视图可串行化

https://blog.csdn.net/stone_fall/article/details/88560088

冲突可串行化

指令的顺序

考虑一个调度S中的两条连续指令（仅限于read与 write操作）Ii与Ij，分别属于事务Ti与Tj

①Ii = read(Q), Ij = read(Q);

②Ii = read(Q), Ij = write(Q);

③Ii = write(Q), Ij = read(Q);

④Ii = write(Q), Ij = write(Q);

在① 情况下，Ii与Ij的次序无关紧要。其余情况下，Ii与Ij的次序不同，其执行结果也不同，数据库最终状态也不同

冲突指令

当两条指令是不同事务在相同数据项上的操作，并且其中至少有一个是write指令时，则称这两条指令是冲突的

如在②、③、④情况下，Ii与Ij 是冲突的

非冲突指令交换次序不会影响调度的最终结果

冲突等价

如果调度S可以经过一系列非冲突指令交换转换成调度S'，则称调度S与S'是冲突等价

冲突可串行化

当一个调度S与一个串行调度冲突等价时，则称该调度是冲突可串行化的

如并行调度3是冲突可串行化的

存在结果相同，但非冲突等价的调度

优先图(precedence graph)

一个调度S的优先图是这样构造的：它是一个有向图G =（V，E），V是顶点集，E是边集。顶点集由所有参与调度的事务组成，边集由满足下述条件之一的边Ti-> Tj组成：

①在Tj执行read(Q)之前，Ti执行write(Q)

②在Tj执行write(Q)之前，Ti执行read(Q)

③在Tj执行write(Q)之前，Ti执行write(Q)

如果优先图中存在边Ti->Tj ，则在任何等价于S的串行调度S'中，Ti都必须出现在Tj之前

冲突可串行化判定准则

如果调度S的优先图中有环，则调度S是非冲突可串行化的。如果图中无环，则调度S是冲突可串行化的

与冲突可串行化等价的串行顺序

串行顺序可由拓扑排序得到，求出与优先图的偏序相一致的线序