可串行化测试

序列化图用于测试调度图的可串行性。

假设有一个调度 S。对于 S，我们构建一个称为优先图的图。该图具有 G = (V, E) 的对，其中 V 包含一组顶点，E 包含一组边。顶点集用于包含调度中参与的所有事务。边集用于包含所有边 Ti ->Tj，其中满足以下三个条件之一：

1. 如果 Ti 在 Tj 执行 (Q) 之前执行写操作，则创建边 Ti → Tj。
2. 如果 Ti 在 Tj 执行写操作之前执行读操作 (Q)，则创建边 Ti → Tj。
3. 如果 Ti 在 Tj 执行写操作之前执行写操作 (Q)，则创建边 Ti → Tj。

• 如果优先图包含单条边 Ti → Tj，则 Ti 的所有指令均在 Tj 的第一条指令执行之前执行。
• 如果调度 S 的优先图包含一个环，则 S 是不可串行化的。如果优先图没有环，则 S 被称为可串行化的。

例如

说明

读(A)：在 T1 中，没有对 A 的后续写入，因此没有新边。
读(B)：在 T2 中，没有对 B 的后续写入，因此没有新边。
读(C)：在 T3 中，没有对 C 的后续写入，因此没有新边。
写(B)：B 之后被 T3 读取，因此添加边 T2 → T3。
写(C)：C 之后被 T1 读取，因此添加边 T3 → T1。
写(A)：A 之后被 T2 读取，因此添加边 T1 → T2。
写(A)：在 T2 中，没有对 A 的后续读取，因此没有新边。
写(C)：在 T1 中，没有对 C 的后续读取，因此没有新边。
写(B)：在 T3 中，没有对 B 的后续读取，因此没有新边。

调度 S1 的优先图

调度 S1 的优先图包含一个环，因此调度 S1 是不可串行化的。

说明

读(A)：在 T4 中，没有对 A 的后续写入，因此没有新边。
读(C)：在 T4 中，没有对 C 的后续写入，因此没有新边。
写(A)：A 之后被 T5 读取，因此添加边 T4 → T5。
读(B)：在 T5 中，没有对 B 的后续写入，因此没有新边。
写(C)：C 之后被 T6 读取，因此添加边 T4 → T6。
写(B)：A 之后被 T6 读取，因此添加边 T5 → T6。
写(C)：在 T6 中，没有对 C 的后续读取，因此没有新边。
写(A)：在 T5 中，没有对 A 的后续读取，因此没有新边。
写(B)：在 T6 中，没有对 B 的后续读取，因此没有新边。

调度 S2 的优先图

调度 S2 的优先图没有环，因此调度 S2 是可串行化的。