数据库 | 数据库保护 | 冲突可串行化 - 好文

目录

冲突可串行化
<https://blog.csdn.net/stone_fall/article/details/88559909#%E5%86%B2%E7%AA%81%E5%8F%AF%E4%B8%B2%E8%A1%8C%E5%8C%96>

指令的顺序
<https://blog.csdn.net/stone_fall/article/details/88559909#%E6%8C%87%E4%BB%A4%E7%9A%84%E9%A1%BA%E5%BA%8F>

冲突指令
<https://blog.csdn.net/stone_fall/article/details/88559909#%E5%86%B2%E7%AA%81%E6%8C%87%E4%BB%A4>

冲突等价
<https://blog.csdn.net/stone_fall/article/details/88559909#%E5%86%B2%E7%AA%81%E7%AD%89%E4%BB%B7>

冲突可串行化
<https://blog.csdn.net/stone_fall/article/details/88559909#%E5%86%B2%E7%AA%81%E5%8F%AF%E4%B8%B2%E8%A1%8C%E5%8C%96>

优先图(precedence graph)
<https://blog.csdn.net/stone_fall/article/details/88559909#%E4%BC%98%E5%85%88%E5%9B%BE(precedence%20graph)>

冲突可串行化判定准则
<https://blog.csdn.net/stone_fall/article/details/88559909#%E5%86%B2%E7%AA%81%E5%8F%AF%E4%B8%B2%E8%A1%8C%E5%8C%96%E5%88%A4%E5%AE%9A%E5%87%86%E5%88%99>

与冲突可串行化等价的串行顺序
<https://blog.csdn.net/stone_fall/article/details/88559909#%E4%B8%8E%E5%86%B2%E7%AA%81%E5%8F%AF%E4%B8%B2%E8%A1%8C%E5%8C%96%E7%AD%89%E4%BB%B7%E7%9A%84%E4%B8%B2%E8%A1%8C%E9%A1%BA%E5%BA%8F>

视图可串行化 <https://blog.csdn.net/stone_fall/article/details/88560088>

https://blog.csdn.net/stone_fall/article/details/88560088
<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是冲突可串行化的

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

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

热门工具换一换