GATE CS 2014 Set 1 Q29 — Transactions and Concurrency Control

A schedule is conflict serializable if its precedence (conflict) graph is acyclic. An edge $T_i \to T_j$ exists in the precedence graph if there are operations $O_i(x)$ in $T_i$ and $O_j(x)$ in $T_j$ such that:

1. $O_i(x)$ appears before $O_j(x)$ in the schedule.
2. At least one of them is a write operation ($w(x)$).

Let's analyze the precedence graph for each option:

• Option A: $r_1(x); r_2(x); w_1(x); r_3(x); w_2(x);$
  • $r_2(x)$ is followed by $w_1(x) \implies T_2 \to T_1$
  • $w_1(x)$ is followed by $w_2(x) \implies T_1 \to T_2$
  • This creates a cycle: $T_2 \leftrightarrows T_1$. Thus, it is not conflict serializable.
• Option B: $r_2(x); r_1(x); w_2(x); r_3(x); w_1(x);$
  • $r_1(x)$ is followed by $w_2(x) \implies T_1 \to T_2$
  • $w_2(x)$ is followed by $w_1(x) \implies T_2 \to T_1$
  • This creates a cycle: $T_1 \leftrightarrows T_2$. Thus, it is not conflict serializable.
• Option C: $r_3(x); r_2(x); r_1(x); w_2(x); w_1(x);$
  • $r_1(x)$ is followed by $w_2(x) \implies T_1 \to T_2$
  • $w_2(x)$ is followed by $w_1(x) \implies T_2 \to T_1$
  • This creates a cycle: $T_1 \leftrightarrows T_2$. Thus, it is not conflict serializable.
• Option D: $r_2(x); w_2(x); r_3(x); r_1(x); w_1(x);$
  • $w_2(x)$ is followed by $r_3(x) \implies T_2 \to T_3$
  • $w_2(x)$ is followed by $r_1(x)$ and $w_1(x) \implies T_2 \to T_1$
  • $r_3(x)$ is followed by $w_1(x) \implies T_3 \to T_1$
  • The resulting precedence graph has edges: $T_2 \to T_3$, $T_2 \to T_1$, and $T_3 \to T_1$.
  • This graph is acyclic, with the equivalent serial order being $T_2 \to T_3 \to T_1$.

Therefore, only the schedule in Option D is conflict serializable.