GATE CS 2025 Set 2 Q43 — Transactions and Concurrency Control

To determine which schedule is conflict serializable, we construct the precedence graph for each option. An edge $T_i \to T_j$ exists if there is a pair of conflicting operations (on the same data item, with at least one write) such that $T_i$ executes before $T_j$.

Let's analyze the schedules:

• Option A:
  • $R_1(X)$ occurs before $W_2(X) \implies T_1 \to T_2$
  • $W_2(X)$ occurs before $R_1(X) \implies T_2 \to T_1$
  • This creates a cycle $T_1 \rightleftharpoons T_2$. Thus, it is not conflict serializable.
• Option B:
  • $W_2(X)$ occurs before $R_1(X)$ and $W_1(X) \implies T_2 \to T_1$
  • $W_2(Y)$ occurs before $W_1(Y) \implies T_2 \to T_1$
  • There are no conflicting operations where $T_1$ executes before $T_2$. The precedence graph contains only the edge $T_2 \to T_1$, which is acyclic. Thus, it is conflict serializable.
• Option C:
  • $R_1(X)$ occurs before $W_2(X) \implies T_1 \to T_2$
  • $W_2(X)$ occurs before $R_1(X) \implies T_2 \to T_1$
  • This creates a cycle $T_1 \rightleftharpoons T_2$. Thus, it is not conflict serializable.
• Option D:
  • $W_1(Y)$ occurs before $W_2(Y) \implies T_1 \to T_2$
  • $W_2(X)$ occurs before $R_1(X) \implies T_2 \to T_1$
  • This creates a cycle $T_1 \rightleftharpoons T_2$. Thus, it is not conflict serializable.