数据库系统的恢复和并发控制技术.ppt
16数据库保护数据库恢复数据库恢复并发控制并发控制数据库安全性数据库安全性数据库完整性数据库完整性21 1、事务的表示方法：、事务的表示方法：R Ri i(X)(X)表示事务表示事务T Ti i的读的读X X操作；操作；W Wi i(X)(X)表示事务表示事务T Ti i的写的写X X操作。操作。例：事务例：事务T1(Read(B)T1(Read(B)；A=B+1A=B+1；write(A)write(A)，事务事务T2(Read(A)T2(Read(A)；B=A+1B=A+1；write(B)write(B)可以表示成：可以表示成：T T1 1：R R1 1(B)W(B)W1 1(A)T(A)T2 2：R R2 2(A)W(A)W2 2(B)(B)3例例:事务事务 T1：R1(X)R1(Y)W1(Y)的执行顺序可表示为的执行顺序可表示为R1(X)R1(Y)W1(Y)符号符号表示先于（表示先于（)，即，即R1(X)先于先于W1(Y)执行，执行，R1(Y)先于先于W1(Y)执行，而执行，而R1(X)和和R1(Y)的先后次序无关紧要。的先后次序无关紧要。42 2、冲突操作、冲突操作定义定义：如果两个操作来自不同的事务，它：如果两个操作来自不同的事务，它们对同一数据单位进行操作，并且其中们对同一数据单位进行操作，并且其中至少有一个是写操作，则称这两个操作至少有一个是写操作，则称这两个操作是相互冲突的或冲突操作。是相互冲突的或冲突操作。例：事务例：事务T T0 0：W W0 0(X)W(X)W0 0(Y)W(Y)W0 0(Z)(Z)事务事务T T1 1：R R1 1(X)R(X)R1 1(Z)W(Z)W1 1(X)(X)则在这两个事务中有冲突操作：则在这两个事务中有冲突操作：R R1 1(X)(X)与与W W0 0(X)(X)W W1 1(X)(X)与与W W0 0(X)(X)R R1 1(Z)(Z)与与W W0 0(Z)(Z)对于冲突操作不能同时执行，哪个先执对于冲突操作不能同时执行，哪个先执行，哪个后执行由调度决定。行，哪个后执行由调度决定。53、调度、调度 设设=T1，T2，T n是一事务集，是一事务集，的一个调度的一个调度S是一拟序集（是一拟序集（,s)其中其中:1)说明说明S执行的操作正是执行的操作正是T1，T2，T n 的操作。的操作。2)s 说明调度说明调度S遵守每个事务的操作的遵守每个事务的操作的 内部执行次序内部执行次序 3)每对冲突操作的执行次序由每对冲突操作的执行次序由S决定。决定。6例如：考虑下列两个事务T0，T1T0=W0(X)W0(Y)W0(Z)T1=R1(X)R1(Z)W1(X)T0，T1的拟序集表示为：的拟序集表示为：T0=(W0(X),W0(Y),W0(Z),)T1=(R1(X),R1(Z),W1(X),R1(X)W1(X),R1(Z)W1(X)7R1(X)R1(Z)W1(X)S1=W0(X)W0(Y)W0(Z)S1=(W0(X),W0(Y),W0(Z),R1(X),R1(Z),W1(X)，W0(X)R1(X)，W0(Z)R1(Z)，R1(X)R1(Z)，R1(X)W1(X)，R1(Z)W1(X)两个事务两个事务T0，T1的调度可以表示为：的调度可以表示为：8S2=（W0(X),W0(Y),W0(Z),R1(X),R1(Z),W1(X)，W0(X)R1(X),W0(Z)R1(Z),R1(Z)R1(X),R1(X)W1(X),R1(Z)W1(X)）R1(X)R1(Z)W1(X)S2=W0(X)W0(Y)W0(Z)两个事务两个事务T0，T1的调度可以表示为：的调度可以表示为：9R1(X)R1(Z)W1(X)S3=W0(X)W0(Y)W0(Z)S3=（W0(X),W0(Y),W0(Z),R1(X),R1(Z),W1(X)，W0(X)R1(X),W0(Z)R1(Z),R1(X)W1(X),R1(Z)W1(X)）两个事务两个事务T0，T1的调度可以表示为：的调度可以表示为：10例：给出事务例：给出事务T0,T1,T2,T3,T4的一个调度的一个调度T0=W0(X)W0(Y)W0(Z)T1=R1(X)R1(Z)W1(X)T4=R4(X)R4(Y)R4(Z)T2=R2(X)W2(Y)T3=R3(Z)W3(Y)W3(Z)11一个调度S1W0(X)W0(Y)W0(Z)R1(X)R1(Z)W1(X)R3(Z)W3(Y)W3(Z)R4(X)R4(Y)R4(Z)R2(X)W2(Y)请写出S1的拟序集124 4、串行调度、串行调度 如果在一个调度中，各个事务不交叉执如果在一个调度中，各个事务不交叉执行，而顺序地串行执行，这个调度被称行，而顺序地串行执行，这个调度被称为串行调度。为串行调度。定义：定义：如果调度如果调度S S中的任意两个事务中的任意两个事务TiTi和和TjTj，如，如果果TiTi的所有操作都先于的所有操作都先于TjTj的所有操作，或者相反，的所有操作，或者相反，则称则称S S为为串行调度串行调度。注意：注意：在串行调度中每一个事务都是在下一个事务开在串行调度中每一个事务都是在下一个事务开始执行之前提交。因此，始执行之前提交。因此，串行调度没有并发性串行调度没有并发性，故每一个串行调度都是一个正确的执行。故每一个串行调度都是一个正确的执行。135 5、并发调度、并发调度 如果在一个调度中，各个事务交叉地执如果在一个调度中，各个事务交叉地执行，这个调度称为并发调度。行，这个调度称为并发调度。14定义：定义：多个事务的并发执行是正确的，当且多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行地执行它们仅当其结果与按某一次序串行地执行它们时的结果相同，称这种调度策略为时的结果相同，称这种调度策略为可串行可串行化的调度化的调度。6 6、可串行化的调度、可串行化的调度如果一个事务集的并发调度与某一串行如果一个事务集的并发调度与某一串行调度是等价的，则称该并发调度是可串调度是等价的，则称该并发调度是可串行化的行化的。157、串行化定理定理：定理：一个调度S是可串行化的，当且仅当它的串行图是无环的。无环的。串行图：串行图：设S是若干事务T1,T2,Tn的一个调度，S的串行图SG(S)是一个有向图，其构成规则如下：1）图中的结点表示事务2）如果Oi和Oj是冲突操作，且Oi先于Oj执行，则在图中有一条边TiTj。16R1(X)W1(X)R3(X)W3(Z)R2(X)W2(Y)W1(Y)T2T1T3R1(X)W1(X)R3(X)W3(X)R2(X)W2(Y)W1(Y)T2T1T3178、等价的串行调度：、等价的串行调度：如果如果SG(S)是无环是无环的，则的，则S等价于等价于SG(S)的任一拓扑排序。的任一拓扑排序。T2T1T3拓扑排序为：T2，T1，T3T1T2T3拓扑排序为：T1,T3,T2或为：T1,T2,T318W0(X)W0(Y)W0(Z)R1(X)R1(Z)W1(X)R3(Z)W3(Y)W3(Z)R4(X)R4(Y)R4(Z)R2(X)W2(Y)调度调度S的串行图的串行图拓扑排序为：拓扑排序为：T0，T2，T1，T3，T4或为：或为：T0，T2，T3，T1，T4T0T1T2T3T419Read(A)Read(B)Read(C)Write(C)Read(D)Write(C)Read(C)Write(D)Write(B)TT2T3可串行化调度20 1）某一事务在对数据进行读、写之前，先）某一事务在对数据进行读、写之前，先要申请并获得对该数据的封锁。要申请并获得对该数据的封锁。2）在释放一个封锁之后，事务不再申请）在释放一个封锁之后，事务不再申请和获得任何其它封锁。和获得任何其它封锁。说明：说明：规则规则1避免了两个冲突操作同时存避免了两个冲突操作同时存取同一数据。取同一数据。规则规则2把每个事务分为两个把每个事务分为两个阶段：上升段和下降段。阶段：上升段和下降段。上升下降每一事务只有得到全每一事务只有得到全部锁以后才放锁。部锁以后才放锁。四、两段锁协议(2PL协议)21例：对事务T1和T2用两段锁协议加锁的过程T1：R1(X)W1(Y)T2：W2(X)W2(Y)SlockXXlockYUnlockXUnlockYXlockXXlockYUnlockXUnlockY22 2PL调度优点：简单调度优点：简单 缺点：易死锁缺点：易死锁 例如：对于如下两个事务采用两段锁协议例如：对于如下两个事务采用两段锁协议 T1：R1(X)W1(Y)T2：W2(Y)W2(X)T1与与T2的一个调度过程：的一个调度过程：1 初始时，没有事务占有锁初始时，没有事务占有锁 2 调度器接到调度器接到R1(X)，对对X加读锁，执行加读锁，执行R1(X)。3 调度器接到调度器接到W2(Y)，对，对Y加写锁，执行加写锁，执行W2(Y)4 调度器接到调度器接到W2(X)，T2等待等待 5调度器接到调度器接到W1(Y)，T1等待等待 这样就造成了死锁。这样就造成了死锁。23定理：任何一个遵从2PL协议的调度都是可串行化的。说明：事务遵守2PL协议是可串行化调度的充分条件，而不是必要条件。即若并发事务都遵守2PL协议，则对这些事务的任何并发调度策略都是可串行化的；若对并发事务的一个调度是可串行化的，不一定所有事务都符合2PL协议。注：三级封锁协议是符合注：三级封锁协议是符合2PL协议的协议的24两段锁协议（续）T1SlockB读B=2Y=BXlockAA=Y+1写回A=3UnlockBUnlockAT2SlockA等待等待等待等待等待等待等待等待等待等待SlockA读读A=3Y=AXlockBB=Y+1写回写回B=4UnlockBUnlockAT1SlockB读读B=2Y=BUnlockBXlockAA=Y+1写回写回A=3UnlockAT2SlockA等待等待等待等待等待等待等待等待SlockA读读A=3X=AUnlockAXlockBB=X+1写回写回B=4UnlockB(a)遵守两段锁协议遵守两段锁协议(b)不遵守两段锁协议不遵守两段锁协议T1SlockB读读B=2Y=BUnlockBXlockAA=Y+1写回写回A=3UnlockAT2SlockA读读A=2X=AUnlockAXlockB等待等待XlockBB=X+1写回写回B=3UnlockB(c)不遵守两段锁协议不遵守两段锁协议25例题1设设T1，T2，T3是如下的三个事务是如下的三个事务T1：A：=A+2T2：A：=A*2T3：A：=A2设设A的初值为的初值为0：若这三个事务允许并发执行，讨论他们若这三个事务允许并发执行，讨论他们可能实施的调度，请一一列举并求每种可能实施的调度，请一一列举并求每种调度的结果调度的结果26解：六种可能的调度解：六种可能的调度 T1T2T3 结果：结果：16 T1T3T2 结果：结果：8 T2T1T3 结果：结果：4 T2T3T1 结果：结果：2 T3T1T2 结果：结果：4 T3T2T1 结果：结果：2例题分析27例题2T1T2T3T4Write(y)Read(x)Read(y)Write(x)Write(x)Write(z)Read(z)Write(x)根据如图调度，判断其是冲突可串行化的吗？为什么？如果调度是冲突可串行化的，请给出与之等价的一个串行调度序列。28根据调度S得到串行图：T3T1T2T4T1T2T3T4由于图中不存在环，故调度由于图中不存在环，故调度S是可串行化的，与之等是可串行化的，与之等价的一个串行调度序列为：价的一个串行调度序列为：29例题3设有两个事务T1、T2，其并发操作如图所示，下面说法正确的是（）A.该操作不存在问题B.该操作丢失修改C.该操作不能重复读D.该操作读“脏”数据T1T2读A=10A=A-5写回读A=10A=A-8写回
