DBMS串行化的测试

序列化图用于测试计划的可序列化。

假设一个时间表S,对于S,我们构造一个称为优先图的图。 该图有一对G =(V,E),其中V由一组顶点组成,E由一组边组成。 顶点集用于包含参与计划的所有事务。 该组边用于包含三个条件之一所有的所有边Ti - > Tj

如果TiTj执行读取(Q)之前执行写入(Q),则创建节点Ti→Tj
如果TiTj执行写入(Q)之前执行读取(Q),则创建节点Ti→Tj
如果TiTj执行写入(Q)之前执行写入(Q),则创建节点Ti→Tj

调度S的优先顺序图:

  • 如果优先图包含单个边Ti→Tj,则在执行Tj的第一个指令之前执行Ti的所有指令。
  • 如果调度S的优先级图包含循环,则S是不可序列化的。 如果优先级图没有循环,那么S称为可序列化。

示例

说明:

Read(A):在T1中,没有后续写入A,因此没有新的边界。
Read(B):在T2中,没有后续写入B,因此没有新的边界。
Read(C):在T3中,没有后续写入C,因此没有新的边界。
Write(B):随后通过T3读取B,因此添加边沿T2→T3
Write(C):随后通过T1读取C,因此添加边沿T3→T1
Write(A):随后由T2读取A,因此添加边沿T1→T2
Write(A):在T2中,没有后续读到A,所以没有新的界。
Write(C):在T1中,没有后续读到C,所以没有新的界。
Write(B):在T3中,没有后续读到B,所以没有新的界。

调度S1的优先顺序图:

调度S1的优先级图包含一个循环,这就是调度S1不可序列化的原因。

说明:

Read(A):在T4中,没有后续写入A,因此没有新的边界。
Read(C):在T4中,没有后续写入C,因此没有新的边界。
Write(A):随后由T5读取A,因此添加边T4→T5
Read(B):在T5中,没有后续写入B,因此没有新的边界。
Write(C):随后由T6读取C,因此添加边T4→T6
Write(B):随后由T6读取A,因此添加边T5→T6
Write(C):在T6中,没有后续读到C,所以没有新的边界。
Write(A):在T5中,没有后续读到A,所以没有新的边界。
Write(B):在T6中,没有后续读到B,所以没有新的边界。

调度S2的优先顺序图:

调度S2的优先级图不包含循环,这就是调度S2可序列化的原因。


上一篇:DBMS调度程序(Schedule)

下一篇:DBMS冲突串行化调度

关注微信小程序
程序员编程王-随时随地学编程

扫描二维码
程序员编程王

扫一扫关注最新编程教程