GATE 2024 CS (CS1) – Question 46
Consider the read-write schedule $S$ over three transactions $T_1,T_2,T_3$: $S: 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$?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) $T_1T_3T_2$; (C) $T_3T_2T_1$; (D) $T_3T_1T_2$
Explanation
Conflicting operations are those of different transactions on the same item with at least one write.
- Item $z$: only $T_1$ touches it ($r_1,w_1$), so no conflicts.
- Item $x$: only $T_2$ touches it.
- Item $y$: $r_3(y),w_3(y)$ come before $r_2(y),w_2(y)$, so $T_3$ must precede $T_2$ (edge $T_3\to T_2$).
The precedence graph has the single edge $T_3\to T_2$, with $T_1$ unconstrained. A serial schedule is conflict-equivalent to $S$ iff $T_3$ comes before $T_2$:
- $T_1T_2T_3$: $T_2$ before $T_3$. **No.**
- $T_1T_3T_2$: **Yes.**
- $T_3T_2T_1$: **Yes.**
- $T_3T_1T_2$: **Yes.**
Answer: B, C, D.