Conflict Serializability

Consider the following schedules involving two transactions. Which one of the following statements is TRUE?

S1: r1( X) r1( Y) r2( X) r2( Y) w2( Y) w1( X)

S2: r1( X) r2( X) r2( Y) w2( Y) r1( Y) w1( X)

(A) Both S1 and S2 are conflict serializable.

(B) S1 is conflict serializable and S2 is not conflict serializable.

(C) S1 is not conflict serializable and S2 is conflict serializable.

(D) Both S1 and S2 are not conflict serializable. 

Answer

To check for conflict serializabilty, we will draw precedence graph for a schedule. If precedence graph contains cycle, the schedule is not conflict serializable else schedule is conflict serializable.

For schedule 1, r1(Y) and w2(Y) are conflicting operations ( operations by different transaction on same data item and atleast one operation is write operation). So, an edge is drawn from T1 to T2 (as r1(Y) is executed before w2(Y)). Similarly, r2(X) and w1(X) are conflicting operations. So, an edge is drawn from T2 to T1 (as r2(X) is executed before w1(X)). As we can see from figure 1, precedence graph contains cycle, so S1 is not conflict serializable.

For schedule 2, r1(Y)  and w2(Y) are conflicting operations. So, an edge is drawn from T2 to T1 (as w2(Y) is executed before r1(Y)). Similarly, r2(X) and w1(X) are conflicting operations. So, an edge is drawn from T2 to T1 (as r2(X) is executed before w1(X)). As we can see from figure 2, precedence graph does not contain cycle, so S2 is conflict serializable.

1Comment
Mohit Lalwani @monty12
28 Jun 2016 01:37 pm

check for conflict serializabilty, draw precedence graph for a schedule. If precedence graph contains cycle, the schedule is not conflict serializable else schedule is conflict serializable.

operation said to be conflict only if
(I) atleast one write operation.
(II) on same data item.
(III) both operation should from different transations.

 

for S1:
find conflict pair;

r1(X)---->w1(x)  -------(1)  not consider because of same transaction;
r1(Y)---->w2(Y)  -------(2) ;
r2(X)---->w1(X)  -------(3)  ;
r2(Y)---->w2(Y)  -------(4) not consider because of same transaction;
now T1---->T2 ,T2---->T1  there is cycle ;
not conflict serializable;

____________________________________________________________
for S2:
find conflict pair;
r1(X)---->w1(X) ----------(1) not consider because of same transaction;
r2(X)---->w1(X) ----------(2);
r2(Y)---->w2(Y) ----------(3) not consider because of same transaction;
w2(Y)---->r1(Y);
now there is serial schedule which T2--->T1;

ans C