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

目录

冲突可串行化

指令的顺序

冲突指令

冲突等价

冲突可串行化

优先图(precedence graph)

冲突可串行化判定准则

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


视图可串行化

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


冲突可串行化

指令的顺序

考虑一个调度S中的两条连续指令(仅限于readwrite操作)IiIj分别属于事务TiTj

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

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

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

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

情况下,IiIj的次序无关紧要。其余情况下,IiIj的次序不同,其执行结果也不同,数据库最终状态也不同

冲突指令

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

如在②、③、④情况下,IiIj 是冲突的

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

冲突等价

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

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

冲突可串行化

当一个调度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是冲突可串行化的

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

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

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

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