1并发控制的概念和理论 12事务可串行化理论 有以下推论: 个可串行化调度必定与某个串行调度等价, 且是一致性调度 致性调度不一定是可串行化调度 同一事务集几个可串行化调度,他们的结果未 必相同
• 有以下推论： – 一个可串行化调度必定与某个串行调度等价， 且是一致性调度 – 一致性调度不一定是可串行化调度 – 同一事务集几个可串行化调度，他们的结果未 必相同 1.2 事务可串行化理论 1 并发控制的概念和理论
1并发控制的概念和理论 13分布式事务的可串行化调度测试 优先图P(S) 调度S的优先图是一个有向图G(N,E),其中 N:一组节点N={T1T2…,Tn},S中的事务 E:一组有向边E={e1e2…,en},Ti→>T是图中的 条边,当且仅当彐p∈Tpq∈T使得pq冲突, 并且p<sq
优先图 P(S) • 调度 S 的优先图是一个有向图G(N,E) ，其中 – N: 一组节点N={T1T2 ,…,Tn}, S中的事务 – E: 一组有向边E={e1 ,e2 ,…,en}, Ti → Tj 是图中的 一条边，当且仅当 p Ti , q Tj 使得p, q 冲突， 并且 p <S q 1.3 分布式事务的可串行化调度测试 1 并发控制的概念和理论
1并发控制的概念和理论 13分布式事务的可串行化调度测试 测试调度S的可串行化 对于调度S中的事务Ti,在图中创建一个节点Ti 对于每一种这样的情形:如果S中的在T执行了W(X)操作 后执行T的R(X)操作,那么在优先图中创建一条边 (Ti→T) 对于每一种这样的情形:如果S中的在T执行了R(X)操作 后执行T的W(X)操作,那么在优先图中创建一条边 对于每一种这样的情形:如果S中的在T执行了W(X)操作 后执行T的W(X操作,那么在优先图中创建一条边 (Ti→Ti) 当且仅当优先图中没有闭环时,调度S是可串行化的
测试调度S的可串行化 • 对于调度 S中的事务Ti，在图中创建一个节点Ti • 对于每一种这样的情形：如果S中的在Ti执行了W(X)操作 后执行Tj的R(X)操作，那么在优先图中创建一条边 （Ti→Tj ） • 对于每一种这样的情形：如果S中的在Ti执行了R(X)操作 后执行Tj的W(X)操作，那么在优先图中创建一条边 （Ti→Tj ） • 对于每一种这样的情形：如果S中的在Ti执行了W(X)操作 后执行Tj的W(X)操作，那么在优先图中创建一条边 （Ti→Tj ） • 当且仅当优先图中没有闭环时，调度S是可串行化的 1.3 分布式事务的可串行化调度测试 1 并发控制的概念和理论
1并发控制的概念和理论 13分布式事务的可串行化调度测试 测试调度S的可串行化 ·优先图中存在环路,说明调度是不可串行化的,否则是可 串行化的 ·环路是指有向图中每条边的起始节点(第一条边除外) 都与前一条边的终止节点连接,而第一条边的起始节点于 最后一条边的终止节点连接,即事务序列是以同一个节点 作为开始和结束的 调度S中事务T在事务T之前,与S等价的调度中T也必须 在T之前 某项数据导致了调度中的一条边的生成,就把数据项标注 到优先图中这条边的旁边 如果调度S中不存在环路,那么就可能存在若干个与S等价 的串行调度
测试调度S的可串行化 • 优先图中存在环路，说明调度是不可串行化的，否则是可 串行化的。 • 环路是指有向图中每条边的起始节点（第一条边除外）， 都与前一条边的终止节点连接，而第一条边的起始节点于 最后一条边的终止节点连接，即事务序列是以同一个节点 作为开始和结束的 • 调度S中事务Ti在事务Tj之前，与S等价的调度中Ti也必须 在Tj之前 • 某项数据导致了调度中的一条边的生成，就把数据项标注 到优先图中这条边的旁边 • 如果调度S中不存在环路，那么就可能存在若干个与S等价 的串行调度 1.3 分布式事务的可串行化调度测试 1 并发控制的概念和理论
1并发控制的概念和理论 13分布式事务的可串行化调度测试 S1的优先图S2的优先图S3的优先图S4的优先图S5的优先图 Y X Y 12 T2 T2 T2 存在环路
1.3 分布式事务的可串行化调度测试 1 并发控制的概念和理论 T1 T2 T1 T2 T1 T2 T1 T2 T1 T2 S1的优先图 S2的优先图 S3的优先图 S4的优先图 S5的优先图 X Y X Y X Y X Y X Y 存在环路