数据库考试题如何找冲突可串行化等价的串行化方案

这个是个可串行化调度，可以根据对数据库元素XYZ的 冲突访问画优先图来进行判断，如果没有环，那么就是可串行化的

第二个问 就是把串行化的调度顺序写出来,串行化调度为：

T3(R(Y))T3(W(Y))T3(R(Z))T4(R(Z))T4(W(Z))T1(R(X))T1(W(X))T1(W(Y))T2(R(X))T2(W(X))T2(R(Y))

根据这个可以基于冲突规则进行置换的，因此有

T3(R(Y))T3(W(Y))T3(R(Z))T1(R(X))T1(W(X))T1(W(Y))T2(R(X))T2(W(X))T2(R(Y))T4(R(Z))T4(W(Z))

T3(R(Y))T3(W(Y))T3(R(Z))T1(R(X))T1(W(X))T1(W(Y))T4(R(Z))T4(W(Z))T2(R(X))T2(W(X))T2(R(Y))

首先确定冲突 *** 作:

同一事务的两个动作冲突:ri(X)wi(X),

不同事务对同一数据库元素的写冲突:wj(X)wi(X),

不同事务对同一数据库元素的读和写冲突:ri(X)wj(X),

这些都是冲突 *** 作：r1(A) w1(A) , r1(A) w2(A) , w2(A)r1(A) ,w1(A) w2(A),

优先图的画法如下：

节点: S中的事务

弧: Ti ->Tj whenever

- pi(A), qj(A) 涉及同一数据库元素

- pi(A) <S qj(A)

- pi, qj 至少一个是写动作

如果存在环, S 不是冲突可串行的, 否则, S 是冲突可串行的

例如S=r1(A)w1(A)r2(A)w2(A)r1(B)w1(B)r2(B)w2(B)

其中w1(A)r2(A)得出T1 ->T2 ，w1(B)r2(B)得出T1 ->T2

无环，所以是可串行调度

再如：S1=r2(A)r1(B)w2(A)r2(B)r3(A)w1(B)w3(A)W2(B)

r2(A)w3(A)得出T2->T3

r1(B)W2(B)得出T1 ->T2

r2(B)w1(B)得出T2 ->T1

有环，S1 不是冲突可串行化的

---