Consider the database transactions T1 and T2, and data items X and Y. Which of the schedule(s) is/are conflict serializable?
| Transaction T1 |
|---|
| R1(X) |
| W1(Y) |
| R1(X) |
| W1(X) |
| COMMIT(T1) |
| Transaction T2 |
|---|
| W2(X) |
| W2(Y) |
| COMMIT(T2) |
Answer
(B)
Explanation
Build the precedence graph. Two operations conflict when they come from different transactions, touch the same item and at least one is a write; the earlier one's transaction gets an edge to the later one's. Commits add no edges.
- (A) R1(X) before W2(X) gives T1 → T2, but W2(X) before the second R1(X) gives T2 → T1. Cycle.
- (B) W2(X) comes before both R1(X) operations and W1(X), and W2(Y) comes before W1(Y). Every edge is T2 → T1, so the graph is acyclic and the schedule is equivalent to the serial order T2, T1.
- (C) W1(Y) before W2(Y) gives T1 → T2, while W2(X) before the second R1(X) gives T2 → T1. Cycle.
- (D) W2(X) before R1(X) gives T2 → T1, while W1(Y) before W2(Y) gives T1 → T2. Cycle.
Answer: B