GATE CS 2009 Q43 — Transactions and Concurrency Control

A schedule is conflict-serializable if its precedence graph contains no cycles. The vertices of the graph are the transactions, and a directed edge $T_i \to T_j$ exists if there is a conflicting pair of operations (accessing the same data item with at least one write operation) such that $T_i$'s operation occurs before $T_j$'s operation.

Let's analyze each schedule:

• Schedule $S_1$:
  • $R_2[x]$ occurs before $W_1[x] \implies T_2 \to T_1$
  • $W_1[y]$ occurs before $W_2[y] \implies T_1 \to T_2$
  Since there is a cycle ($T_1 \leftrightarrow T_2$), $S_1$ is not conflict-serializable.


• Schedule $S_2$:
  • $R_2[x]$ occurs before $W_1[x] \implies T_2 \to T_1$
  • $R_2[y]$ occurs before $W_1[y] \implies T_2 \to T_1$
  • $W_2[y]$ occurs before $W_1[y] \implies T_2 \to T_1$
  The only directed edge is $T_2 \to T_1$. Since there are no cycles, $S_2$ is conflict-serializable.


• Schedule $S_3$:
  • $W_1[x]$ occurs before $R_2[x] \implies T_1 \to T_2$
  • $W_1[y]$ occurs before $R_2[y] \implies T_1 \to T_2$
  • $W_1[y]$ occurs before $W_2[y] \implies T_1 \to T_2$
  The only directed edge is $T_1 \to T_2$. Since there are no cycles, $S_3$ is conflict-serializable.


• Schedule $S_4$:
  • $R_2[x]$ occurs before $W_1[x] \implies T_2 \to T_1$
  • $W_1[y]$ occurs before $W_2[y] \implies T_1 \to T_2$
  Since there is a cycle ($T_1 \leftrightarrow T_2$), $S_4$ is not conflict-serializable.

Thus, only $S_2$ and $S_3$ are conflict-serializable.