1并发控制的概念和理论 12事务可串行化理论 事务T T;={∑,≤} 其中 1.∑:操作符集合:{R(x),W(x)}U{A,C1} 2.A,C;是最后的操作符,只能是其 3.≤:(冲突)操作有序执行,R(x)<W(x)或 Wi(x)<RiX
• 事务Ti Ti= { i , <i } 其中： 1. i : 操作符集合：{Ri (x), Wi (x) } U {Ai , Ci } 2. Ai , Ci 是最后的操作符，只能是其一 3. <i : (冲突)操作有序执行，Ri (x) <i Wi (x) 或 Wi (x) <i Ri (x) 1.2 事务可串行化理论 1 并发控制的概念和理论
1并发控制的概念和理论 12事务可串行化理论 操作符集 读R(x)和写Wx)动作序列 冲突动作 R1(A)W2(A)W1(A) W2(A)R(A)W2(A) 个调度 事务的一个操作序列称为一个调度,一般用S表示 比如,S:R(x),R24y),W2(y)R2x),W1(x),W2(x)
• 操作符集 读Ri (x)和写Wi (x)动作序列 • 冲突动作 R1 (A) W2 (A) W1 (A) W2 (A) R1 (A) W2 (A) • 一个调度 事务的一个操作序列称为一个调度，一般用S表示 比如，S: R1 (x),R2 (y),W2 (y),R2 (x),W1 (x),W2 (x) 1.2 事务可串行化理论 1 并发控制的概念和理论
1并发控制的概念和理论 12事务可串行化理论 例子 已知:站点1有数据X,站点2有数据Y 约束:X=Y T (T1)a←- 5(2)c<-X 2(11)x←a+1006(12)X<2c (T1)b←-Y 7(T2)d<Y 4(T1)Y<b+1008(12)Y←2d ↓先序关系
T1 T2 1 (T1 ) a X 5 (T2 ) c X 2 (T1 ) X a+100 6 (T2 ) X 2c 3 (T1 ) b Y 7 (T2 ) d Y 4 (T1 ) Y b+100 8 (T2 ) Y 2d 先序关系 例子 已知：站点1有数据X，站点2有数据Y 约束：X=Y 1.2 事务可串行化理论 1 并发控制的概念和理论
调度S1 事务内 事务间 (X站点) (Y站点) (T a<X 2(T1)Xa+100 5(T2)c← 3(T1)b<-Y 6(12)x-2c 4(T)Y<b+100 7(T2)d←Y 8(T2)Y←-2d 初值:X=Y=0,结果:X=Y=200
(X站点) (Y站点) 1 (T1 ) a X 2 (T1 ) X a+100 5 (T2 ) c X 3 (T1 ) b Y 6 (T2 ) X 2c 4 (T1 ) Y b+100 7 (T2 ) d Y 8 (T2 ) Y 2d 初值: X=Y=0 , 结果: X=Y=200 调度S1 事务内 事务间
1并发控制的概念和理论 12事务可串行化理论 并发调度定义 令T={T1,T2,Tn}是一组事务.T上的调度S是具 有如下顺序关系<的偏序,即S={∑nT} (1)∑产T (2)<r (3)对于任意一组冲突操作pq∈S,存在p<q 或q<p关系
令T= {T1 ,T2 ,…,Tn} 是一组事务. T上的调度 S 是具 有如下顺序关系<T的偏序，即S={T ,<T} : (1) T= Ti (2) <T <i (3) 对于任意一组冲突操作 p,q S, 存在 p < q 或 q < p关系 并发调度定义 i=1 N N i=1 1.2 事务可串行化理论 1 并发控制的概念和理论