Consider the following four schedules due to three transactions (indicated by…
20172014
Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item X, denoted by r(X) and w(X) respectively. Which one of them is conflict serializable ?
S1 : r1 (X); r2 (X); w1 (X); r3 (X); w2 (X)
S2 : r2 (X); r1 (X); w2 (X); r3 (X); w1 (X)
S3 : r3 (X); r2 (X); r1 (X); w2 (X); w1 (X)
S4 : r2 (X); w2 (X); r3 (X); r1 (X); w1 (X)
- A.
S1
- B.
S2
- C.
S3
- D.
S4
Attempted by 131 students.
Show answer & explanation
Correct answer: D
Answer: Schedule S4 is conflict serializable. It is equivalent to the serial order T2, T3, T1.
Reason (precedence graph):
w2(X) occurs before r3(X), so there is an edge from T2 to T3.
w2(X) occurs before r1(X) and before w1(X), so there is an edge from T2 to T1.
r3(X) occurs before w1(X), so there is an edge from T3 to T1.
The resulting precedence graph has edges T2 -> T3, T2 -> T1, and T3 -> T1. There are no edges pointing back to T2 or T3, so the graph is acyclic. A topological ordering is T2, T3, T1, which gives the equivalent serial schedule.
Why the other schedules fail:
S1 and S2 produce mutual conflicts between T1 and T2 (edges in both directions), creating a cycle.
S3 also produces a cycle between T1 and T2 via their read/write ordering, so it is not conflict serializable.
Conclusion: Only S4 is conflict serializable, equivalent to the serial execution T2; T3; T1.
A video solution is available for this question — log in and enroll to watch it.