1并发控制的概念和理论 12事务可串行化理论 调度 组事务的调度必须包含这些事务的所有操作 调度中某个事务的操作顺序必须保持与该事务原有 的顺序相同 串行调度 个事务的第一个动作是在另一个事务的最后一个 动作完成后开始.即调度中事务的各个操作不会交 叉,每个事务相继执行 致性调度 调度可以使得数据库从一个一致性状态转变为另 个一致性状态,则称调度为一致性调度
• 调度 – 一组事务的调度必须包含这些事务的所有操作 – 调度中某个事务的操作顺序必须保持与该事务原有 的顺序相同 • 串行调度 – 一个事务的第一个动作是在另一个事务的最后一个 动作完成后开始. 即调度中事务的各个操作不会交 叉, 每个事务相继执行. • 一致性调度 – 调度可以使得数据库从一个一致性状态转变为另一 个一致性状态，则称调度为一致性调度 1.2 事务可串行化理论 1 并发控制的概念和理论
1并发控制的概念和理论 12事务可串行化理论 调度等价 S1与S2等价,也就是说,对于冲突操作, <O101>,O1<O在S中成立,同时O1<O1 在S2中也成立 可串行化调度 如果一个调度等价于某个串行调度,则该 调度称为可串行化调度。 也就是说,该调度可以通过一系列非冲突 动作的交换操作使其成为串行调度
• 调度等价 – S1与S2等价, 也就是说, 对于冲突操作, <Oi , Oj>, Oi < Oj在S1中成立, 同时 Oi < Oj 在S2中也成立 • 可串行化调度 – 如果一个调度等价于某个串行调度，则该 调度称为可串行化调度。 – 也就是说，该调度可以通过一系列非冲突 动作的交换操作使其成为串行调度 1.2 事务可串行化理论 1 并发控制的概念和理论
1并发控制的概念和理论 12事务可串行化理论 例子 两个事务,定义如下 T 1. Read(x) 1. Read(x) 2.X=X+10 2.X=x-20 3. Write(x) 3. Write(x) 4. Read(y) 4. Read(y) 5.y=y-15 6. Write(y) 6. Write(y) 7. commit 7. commit
例子 • 两个事务，定义如下： T1 : 1. Read(x） 2. x=x+10 3. Write(x) 4. Read(y) 5. y=y-15 6. Write(y) 7. commit 1.2 事务可串行化理论 1 并发控制的概念和理论 T2 : 1. Read(x） 2. x=x-20 3. Write(x) 4. Read(y) 5. y=y*2 6. Write(y) 7. commit
1并发控制的概念和理论 12事务可串行化理论 五种调度: R1(x)2xX+10,W1(x)R1(y)2y=y-15,W1(y)C1,R2(x),x= 20,W2(x)R2(y)2y=y*2,W2(y),C2} S2={R1(x),x=x+10,W1(x)2R2(x)2X=X-20,W2(x)2R1(y)2y=y 15,W1(y).C1,R2(y)2y=y*2,W2(y)2C2} S3={R1(x)2X=X+10,W1(x),R2(x)XX 20,W2(x),R2(y)y=y*2,W2(y),C2,R1(y)y=y-15,W1(y)2C1} S4=R(X),XX 20.W2(x),R2(y)y=y*2,W2(y).C2,R1(x)2x=x+10.W1(x),R1(y)y 15,W1(y)C1 S5={R2(x)2x=X-20.W2(x),R1(X)X=x+10.W1(x) R2(y)y=y*2,W2(y)C2,R1(y)y=y-15.W1(y)C1
五种调度： S1={R1 (x),x=x+10,W1 (x),R1 (y),y=y-15,W1 (y),C1 , R2 (x),x=x- 20,W2 (x),R2 (y),y=y*2,W2 (y),C2} S2={R1 (x),x=x+10,W1 (x), R2 (x),x=x-20,W2 (x), R1 (y),y=y- 15,W1 (y),C1 , R2 (y),y=y*2,W2 (y),C2} S3={R1 (x),x=x+10,W1 (x), R2 (x), x=x- 20,W2 (x),R2 (y),y=y*2,W2 (y),C2 ,R1 (y),y=y-15,W1 (y),C1} S4={R2 (x),x=x- 20,W2 (x),R2 (y),y=y*2,W2 (y),C2 ,R1 (x),x=x+10,W1 (x),R1 (y),y =y-15,W1 (y),C1} S5={R2 (x),x=x-20,W2 (x), R1 (x),x=x+10,W1 (x), R2 (y),y=y*2,W2 (y),C2 ,R1 (y),y=y-15,W1 (y),C1} 1.2 事务可串行化理论 1 并发控制的概念和理论
1并发控制的概念和理论 12事务可串行化理论 如果将事务提交延迟到两个事务操作完成 之后执行,有: 调度S1和S4是串行调度 调度S2和S1的冲突操作具有相同的顺序,因此 是等价调度;S2是可串行化调度,也是一致性 调度 调度S3虽是一致调度,但是它不与S1或S4等价, 所以S3不是可串行化调度 调度S5和S4等价,所以S5是一致调度,也是可 串行化调度
• 如果将事务提交延迟到两个事务操作完成 之后执行，有： – 调度S1和S4是串行调度 – 调度S2和S1的冲突操作具有相同的顺序，因此 是等价调度；S2是可串行化调度，也是一致性 调度 – 调度S3虽是一致调度，但是它不与S1或S4等价， 所以S3不是可串行化调度 – 调度S5和S4等价，所以S5是一致调度，也是可 串行化调度 1.2 事务可串行化理论 1 并发控制的概念和理论