GATE CS 2014 Set 3 Q29 — Transactions and Concurrency Control

To determine if the schedules are conflict-serializable, we construct their precedence graphs. An edge $T_i \to T_j$ exists if there are conflicting operations $op_i(A)$ and $op_j(A)$ (where at least one is a write) such that $op_i(A)$ occurs before $op_j(A)$.

Analysis of Schedule $S1$:

• On $X$: $r_3(X)$ is before $w_1(X) \implies T3 \to T1$
• On $Y$: $r_2(Y)$ is before $w_3(Y) \implies T2 \to T3$
• On $Z$: $w_2(Z)$ is before $r_1(Z)$ and $w_1(Z) \implies T2 \to T1$

The precedence graph for $S1$ contains the edges: $\{T2 \to T3, \; T3 \to T1, \; T2 \to T1\}$. Since there are no cycles, $S1$ is conflict-serializable (with equivalent serial order $T2 \to T3 \to T1$).

Analysis of Schedule $S2$:

• On $Y$: $r_2(Y)$ is before $w_3(Y) \implies T2 \to T3$
• On $Z$: $r_1(Z)$ is before $w_2(Z) \implies T1 \to T2$
• On $Z$: $w_2(Z)$ is before $w_1(Z) \implies T2 \to T1$

The precedence graph for $S2$ contains the cycle $T1 \to T2 \to T1$. Since it contains a cycle, $S2$ is not conflict-serializable.

Thus, only $S1$ is conflict-serializable.