GATE CS 2024 Set 1 Q36 — Transactions and Concurrency Control

To find which serial schedules are conflict equivalent to $S$, we construct the precedence graph (conflict graph) by identifying conflicting operations between different transactions.

Two operations conflict if they belong to different transactions, access the same data item, and at least one of them is a write operation:

• On $z$: Only $T_1$ accesses $z$ ($r_1(z), w_1(z)$). Thus, there are no conflicts involving $z$ between different transactions.
• On $x$: Only $T_2$ accesses $x$ ($r_2(x), w_2(x)$). Thus, there are no conflicts involving $x$ between different transactions.
• On $y$: Both $T_2$ and $T_3$ access $y$. The conflicting operations are:
  • $w_3(y)$ and $r_2(y)$ $\implies T_3 \to T_2$
  • $w_3(y)$ and $w_2(y)$ $\implies T_3 \to T_2$

Since $T_1$ has no conflicting operations with any other transaction, there are no precedence edges involving $T_1$. The only dependency in the precedence graph is:

Any conflict-equivalent serial schedule must preserve this dependency, meaning $T_3$ must execute before $T_2$. The position of $T_1$ can be anywhere. This gives the following valid serial schedules:

1. $T_1 T_3 T_2$ (Option B)
2. $T_3 T_2 T_1$ (Option C)
3. $T_3 T_1 T_2$ (Option D)