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可序列化的原因。
下一篇:DBMS冲突串行化调度
扫描二维码
程序员编程王