DBMS可串行性测试 DBMS可串行性测试|DBMS

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

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

文章图片

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

例如：

文章图片
计划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的优先级图：