DBMS可串行性测试

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

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

1. 如果Ti在Tj执行读（Q）之前执行写（Q）, 则创建节点Ti→Tj。
2. 如果Ti在Tj执行写入（Q）之前执行Ti（读取）（Q）, 则创建节点Ti→Tj。
3. 如果Ti在Tj执行写（Q）之前执行写（Q）, 则创建节点Ti→Tj。

• 如果优先级图包含单个边Ti→Tj, 则在执行Tj的第一条指令之前先执行Ti的所有指令。
• 如果时间表S的优先级图包含一个周期, 则S是不可序列化的。如果优先级图没有循环, 则S被称为可序列化。

例如：

说明：

Read（A）：在T1中, 没有后续写入A, 因此没有新的边沿Read（B）：在T2中, 没有后续写入B, 因此没有新的边沿Read（C）：在T3中, 没有后续写入C, 因此没有新的边沿Write（B）：B随后被T3读取, 因此添加边沿T2→T3 Write（C）：C随后被T1读取, 因此添加边沿T3→T1 Write（A）：随后被读取的边沿T3 T2, 因此添加边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）：A随后被T5读取, 因此添加边沿T4→T5读（B）：在T5中, 没有后续写入B, 因此没有新边沿Write（C）：C随后被T6读取, 因此添加了边沿T4→T6写入（B）：A随后被读取T6, 因此添加边T5→T6 Write（C）：在T6中, 没有后续读取到C, 因此没有新的边Write（A）：在T5中, 没有任何后续读取到A, 因此没有新的边Write（B）：在T6, 以后没有读取到B, 因此没有新的边

计划S2的优先级图：

计划S2的优先级图不包含任何循环, 这就是为什么ScheduleS2可序列化的原因。