DBMS串行化的测试

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

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

如果Ti在Tj执行读取(Q)之前执行写入(Q)，则创建节点Ti→Tj。
如果Ti在Tj执行写入(Q)之前执行读取(Q)，则创建节点Ti→Tj。
如果Ti在Tj执行写入(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可序列化的原因。