Solved Example on Concurrency Control

Consider two transactions T1 and T2, and four schedules S1, S2, S3, S4 of T1 and T2 as given below:  
T1 :R(x) W(x) W (y)   T2 :R (x) R (y) W(y) 

S1 :R1(x) R2(x) R2(y) W1(x) W1(y) W2(y)

S2: R1(x) R2(x) R2(y) W1(x) W2(y) W1(y)

S3: R1(x) W1(x) R2(x) W1(y) R2(y) W2(y)

S4: R2(x) R2(y) R1(x) W1(x) W1(y) W2(y) 
 Which of the above schedules are conflict serializable?  

(A) S1 and S2 (B) S2 and S3 (C) S3 only (D) S4 only 

Answer

To check for conflict serializablility, we have to find conflicting operations pair in a schedule and draw precedence graph. If it contain cycle, the schedule is not conflict serializable. 

Schedule 1: conflicting operation pairs are: (W1(y),W2(y)) and (R2(x),W1(x)), the precedence graph has been shown as:

As the graph contain cycle, it is not conflict serializable. 

Using the same procedure for others, we will see, S2 and S3 are conflict serializable. So correct option is B.

For conflict serializability, u can refer:

http://geeksquiz.com/conflict-serializability/

0Comment