Let Ri (z) and Wi (z) denote read and write operations on a data element z by…
2022
Let Ri (z) and Wi (z) denote read and write operations on a data element z by a transaction Ti , respectively. Consider the schedule S with four transactions.
S : R4(x), R2(x), R3(x), R1(y), W1(y), W2(x), W3(y), R4(y)
Which one of the following serial schedules is conflict equivalent to S?
- A.
T1 → T3 → T4 → T2
- B.
T1 → T4 → T3 → T2
- C.
T4 → T1 → T3 → T2
- D.
T3 → T1 → T4 → T2
Attempted by 194 students.
Show answer & explanation
Correct answer: A
Key conflicts and how they produce precedence edges:
On x: R4(x) occurs before W2(x) → edge T4 → T2; R3(x) occurs before W2(x) → edge T3 → T2; W2(x) occurs before the later R4(x) → edge T2 → T4 (these last two edges create a cycle between T2 and T4).
On y: R1(y) and W1(y) occur before W3(y), giving edges T1 → T3 (both R1(y) before W3(y) and W1(y) before W3(y) lead to T1 → T3).
The precedence graph therefore has edges: T4 → T2, T2 → T4 (a cycle), T3 → T2, and T1 → T3.
Conclusion: Because there is a cycle between T2 and T4, the schedule is not conflict-serializable. None of the provided serial schedules (for example "T 1 → T 3 → T 4 → T 2", "T 1 → T 4 → T 3 → T 2", "T 4 → T 1 → T 3 → T 2", or "T 3 → T 1 → T 4 → T 2") can be conflict equivalent to S.
A video solution is available for this question — log in and enroll to watch it.