Consider the following read-write schedule \(S\) over three transactions \(T_{1}\), \(T_{2}\), and \(T_{3}\), where the subscripts in the schedule indicate transaction IDs:
\(S\colon r_{1}(z);\) \(w_{1}(z);\) \(r_{2}(x);\) \(r_{3}(y);\) \(w_{3}(y);\) \(r_{2}(y);\) \(w_{2}(x);\) \(w_{2}(y);\)
Which of the following transaction schedules is/are conflict equivalent to \(S\) ?
Answer
(B), (C), (D)
Explanation
Two operations conflict when they come from different transactions, use the same item and at least one of them is a write.
- \(z\) is used only by \(T_{1}\) and \(x\) only by \(T_{2}\), so they cause no conflicts.
- On \(y\), both \(r_{3}(y)\) and \(w_{3}(y)\) come before \(r_{2}(y)\) and \(w_{2}(y)\). The conflicting pairs \(r_{3}(y)\)–\(w_{2}(y)\), \(w_{3}(y)\)–\(r_{2}(y)\) and \(w_{3}(y)\)–\(w_{2}(y)\) all order \(T_{3}\) before \(T_{2}\).
The precedence graph has the single edge \(T_{3} \to T_{2}\), and \(T_{1}\) is free. A serial schedule is conflict equivalent to \(S\) exactly when \(T_{3}\) comes before \(T_{2}\): \(T_{1}T_{3}T_{2}\), \(T_{3}T_{2}T_{1}\) and \(T_{3}T_{1}T_{2}\). Option A puts \(T_{2}\) first.
Answer: B, C, D