PPT《*》

和S等价,即产生相同的执行结果. 上例上的第三种情况S3(简化只留下r、w语句) 并发事务的可串行化 7.1.5 * T1 T2 R(A) W(A) R(A) W(A) R(B) W(B) R(B) W(B) T1 T2 R(A) W(A) R(A) R(B) W(A) W(B) R(B) W(B) S3 S3-1 并发事务的可串行化 7.1.5 * T1 T2 R(A) W(A) R(B) R(A) W(A) W(B) R(B) W(B) T1 T2 R(A) W(A) R(B) R(A) W(B) W(A) R(B) W(B) S3-2 S3-3 并发事务的可串行化 7.1.5 * T1 T2 R(A) W(A) R(B) W(B) R(A) W(A) R(B) W(B) 同第一种,所以第三种S3和第一种S1是等价的. S3-4 并发事务的可串行化 7.1.5 * 定义: 如果调度S'

从调度S通过交换一系列的非冲突语句得到,那么称S、S'

是一对 冲突等价 的调度. 如果调度S和某个串行调度是 冲突等价 ,那么称调度S是 冲突可串行化 的调度. 例7-2:第一种S1和第二种S2是 冲突等价等价 吗? 并发事务的可串行化 7.1.5 * 例7-2:第一种S1和第二种S2是 冲突等价等价 吗? T1 T2 R(A) W(A) R(B) W(B) R(A) W(A) R(B) W(B) 即:T2的r(A)不可能换到T1的w(A)之前 ,所以两种情不一样. 并发事务的可串行化 7.1.5 * 例7-3:有一并发调度T

3、T4是 冲突可串行化 吗? T3 T4 R(Q) W(Q) W(Q) 两邻语句不能互换即不能变为 T3 T4 T4 T3 所以不是 冲突可串行化 并发事务的可串行化 7.1.5 例7-4:有一并发调度 T1: 从帐号A转100到帐号B T5: 从帐号B转10 到帐号A 设: A=2000 B=1000 T1 T5 R(A) A:=A-100 W(A) R(B) B:=B+100 W(B) R(B) B:=B-10 W(B) R(A) A:=A+10 W(A) T1 T5 R(A) A:=A-100 W(A) R(B) B:=B-10 W(B) R(B) B:=B+100 W(B) R(A) A:=A+10 W(A) A=1910 B=1090 A=1910 B=1090 并发事务的可串行化 7.1.5 * 这两种 调度 等价,但不是 冲突可串行化 而 调度等价 不一定是 冲突等价 . 可见: 冲突等价 的定义比 调度等价 的定义严格. 即: 冲突等价 一定是 调度等价 . 并发事务的可串行化 7.1.5 * 2. 观察可串行化 比 冲突等价 的定义放宽一些. 定义: 定义:在同样事务集上的两个调度设S、S'

,如果满足下列三个条件,那么称S、S'

是 观察等价 的调度. 并发事务的可串行化 7.1.5 * 对每个数据项Q,如果事务Ti在调度S中读了Q的初值,那么事务Ti在调度S'

也读Q的初值. T1 T2 R(A) W(A) R(B) W(B) R(A) W(A) R(B) W(B) 例7-5: S1 并发事务的可串行化 7.1.5 * 对每个数据Q,如果在调度S中,事务Tj执行read(Q)操作,读了由事务Ti 产生的Q值,那么在调度S'

中,事务Tj也必须执行read(Q)操作,读由事务Ti产生的Q值. T1 T2 R(A) W(A) R(B) W(B) R(A) W(A) R(B) W(B) S2 并发事务的可串行化 7.1.5 * 对每个数据项Q,如果在调度S中, 最后执行 W(Q)的事务是Ti,那么在S'

中最后执行W(Q)也是Ti. T1 T2 R(A) W(A) R(A) W(A) R(B) W(B) R(B) W(B) S3 并发事务的可串行化 7.1.5 * (1)(2)可以保证在调度中每个事务读到同样的数据值,(1)(2)(3)可以导致DB的状态是一样的. T1 T2 R(A) W(A) R(B) W(B) R(A) W(A) R(B) W(B) T1 T2 R(A) W(A) R(B) W(B) R(A) W(A) R(B) W(B) T1 T2 R(A) W(A) R(A) W(A) R(B) W(B) R(B) W(B) S1 S2 S3 并发事务的可串行化 7.1.5 * S1 S2 S3 在S1中:T1读A的初始,S2中T1不读A的初始.所以S1,S2不是观察等价. S1和S3比较. (1) T1读 A的初始值(S1,S3中)B的初始值(S1,S3中) (2) S1中,T2读由T1产生的A,B值. (3) S1中,最后执行W(A)、W(B)是T2. S3中,最后执行W(A)、W(B)是T2.所以S1和S3是 观察等价 . 并发事务的可串行化 7.1.5 * 定义: 如果调度S与某个串引调度是 观察等价 ,那么称调度S是 观察可串行化 的调度. S3为:观察可串行化,也是 冲突可串行化 T3 T4 T6 R(Q) W(Q) W(Q) W(Q) 例7-6: S1 并发事务的可串行化 7.1.5 * T3 T4 T6 R(Q) W(Q) W(Q) W(Q) S1是 观察可串行化 但S1不是 冲突可串行化 . 结论: 每个 冲突可串行化 的调度都是 观察可串行化 ,但 观察可串行化 的调度不一都是 冲突可串行化 . 并发事务的可串行化 7.1.5 * 小结