GATE CS 2012 Q27 — Transactions and Concurrency Control

To determine the conflict serializability of any non-serial interleaving of transactions $T_1$ and $T_2$, we identify their conflicting operations on shared data items $P$ and $Q$:

• $T_1$: $r_1(P) \to r_1(Q) \to w_1(Q)$
• $T_2$: $r_2(Q) \to r_2(P) \to w_2(P)$

The conflicting pairs of operations are:

1. $r_1(P)$ and $w_2(P)$ on data item $P$
2. $r_2(Q)$ and $w_1(Q)$ on data item $Q$

For any schedule to be non-serial:

• $T_1$ cannot completely finish before $T_2$ starts. Thus, the first operation of $T_2$, which is $r_2(Q)$, must execute before the last operation of $T_1$, which is $w_1(Q)$. This write-after-read conflict ($r_2(Q) \to w_1(Q)$) creates a precedence edge: $T_2 \to T_1$.
• Similarly, $T_2$ cannot completely finish before $T_1$ starts. Thus, the first operation of $T_1$, which is $r_1(P)$, must execute before the last operation of $T_2$, which is $w_2(P)$. This write-after-read conflict ($r_1(P) \to w_2(P)$) creates a precedence edge: $T_1 \to T_2$.

Since any non-serial interleaving forces both edges $T_1 \to T_2$ and $T_2 \to T_1$, the precedence graph will always contain a cycle. Therefore, any non-serial interleaving is not conflict serializable.