目录 冲突可串行化 指令的顺序 冲突指令 冲突等价 冲突可串行化 优先图(precedence graph) 冲突可串行化判定准则 与冲突可串行化等价的串行顺序 视图可串行化 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是冲突可串行化的 与冲突可串行化等价的串行顺序 串行顺序可由拓扑排序得到,求出与优先图的偏序相一致的线序