在数据库中,事务在并发调度过程中,会产生多种结果,什么样的调度是正确的?只有串行调度才是正确的结果。并发过程的结果只有与串行调度结果一样的才是正确的。这种并发调度被称为可串行化调度。
可串行化是并发事务正确调度的基本准则。对于一个并发调度,当且仅当它是可串行化的时候,才被认为是正确调度。
本文主要讲解判断可串行化调度的充要条件。
1.冲突操作指的是不同事务对于同一数据的读写操作与写写操作。
2.有些冲突操作是可以交换次序的,有些冲突操作不能交换次序。
3.不能交换位置的次序为: (1).不同事务的冲突操作。
(2).同一事务的两个操作。
4.一个调度Sc在保证冲突操作(即3中的两种情况)次序不变的情况下,通过交换两个事务不冲突操作的次序得到另一个调度Sc',如果Sc'是串行的,则称调度Sc为冲突可串行化的调度。(如果觉得第四句话拗口不熟悉继续往下看就明白了)
例1:有两个事物T1与T2,初值A=10,B=20。
T1:读B;A=B+1 ;
T2:读A;B=A+1;
先执行T1,后执行T2,结果为A=21,B=22。
先执行T2,后执行T1,结果为A=12,B=11。
以上两种结果均是正确。除这两种结果外的结果,都是错误的调度结果。
冲突可串行化例:
例2.先导解释:r1(A),其中r代read表读操作,1代表事务1,A代表A类数据。w2(B),w代表write写操作,2代表事务2,B代表数据B。
例2:有一调度,Sc1=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B),
选出其可以交换的次序,即不是第二种情况就可以交换次序:
r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B) 这四个颜色块分别标记为A,B,C,D。(注意各块内部也是可以分开的)
经过上文的分析,从块与块之间的角度来看,我们可以得出A与B是冲突操作,C与D是冲突操作,符合第三条的第一种情况,所以这两个不能交换次序。
再从块内角度分析,A内部r1(A)w1(A)是冲突操作,符合第三条的第二种情况,所以这两个不能交换次序。同理可得BCD块内情况均是如此。
下面我们打破块的束缚,从整体来看,绿色块跟青色块可以交换次序,因为这两个操作不冲突,不符合第三条的任意一种情况。
r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)
交换这两个块,可以得到如下结果:
r1(A)w1(A)r2(A)r1(B)w1(B)w2(A)r2(B)w2(B)
再看新的绿色快=块与青色块,如果交换它俩也不会发生冲突:
r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)
交换之:
r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)
最后这个结果就变为:
r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)
把原来的次序:r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)
换成了
r1(A)w1(A)r1(B)w1(B)r2(A)w2(A)r2(B)w2(B)
这就相当于执行了串行操作T1,T2。于是,这就是冲突可串行化。
串行化就是把同一个事务要做的读写操作按先后顺序排到一块。并发事务可以调整成串行化的话,就称为可串行化调度。
冲突不可串行化例:
有三个事务T1 = W1(Y)W1( X ) , T2 = W2(Y)W2( X ) , T3 = W3( X )。
调度L1=W1(Y)W1( X )W2(Y)W2( X )W3( X )是一个串行调度。
调度L2=W1(Y)W2(Y) W2( X )W1( X )W3( X )不满足冲突可串行化,但是调度L2是可串行化的。因为L2的调度结果与L1结果相同。为啥相同?自己随便代入值算算就知道了。
为什么说调度L2不可冲突串行化?如果把W1(X) 放到W2(Y) W2( X )前,变为W1(Y)W1( X )W2(Y)W2( X )W3( X ),就违反了第三条第一种情况,所以不能改变次序。但是可串行化的条件是只要满足其中一种串行调度次序就可以。
在本题中串行顺序有6种,分别是123,132,213,231,312,321.
上文的判断方法很稳妥,求出来的肯定是对的,但如果用优先图来做的话,时间效率会很高,而且容易识别出错误来。
大杀器:优先图
用圆圈跟逻辑线来表示,圆圈表示事务,逻辑箭头线表示从事务1转向事务2.
例:有三个事务T1 = W1(Y)W1( X ) , T2 = W2(Y)W2( X ) , T3 = W3( X )。调度L2=W1(Y)W2(Y) W2( X )W1( X )W3( X )的优先图画法如下图所示:
有环就不能冲突可串行化,没有环的就可以。
画优先图注意事项:
1.所有资源都要画上,在逻辑线上标注资源名称,在圆圈内标注事务标号。、
2.如果要画从Ti到Tj的线,需要满足以下三种情况的其中一种:
(1)Tj在read(W)前,Ti要write(W)
(2)Tj在write(W)前,Ti要read(W)
(3)Tj在write(W)前,Ti要write(W)