Consider the following four schedules due to three transactions (indicated by the subscript) using $read$ and $write$ on a data item $x$, denoted by $r(x)$ and $w(x)$ respectively. Which one of them is conflict serializable?

To check for conflict serializability, we construct the precedence (serialization) graph for each schedule and check for cycles:

1. Option (A): $r_1(x) ; r_2(x) ; w_1(x) ; r_3(x) ; w_2(x)$

   • Conflict between $r_2(x)$ and $w_1(x)$ gives edge $T_2 \to T_1$.

   • Conflict between $w_1(x)$ and $w_2(x)$ gives edge $T_1 \to T_2$.

   • There is a cycle between $T_1$ and $T_2$. Hence, it is not conflict serializable.

2. Option (B): $r_2(x) ; r_1(x) ; w_2(x) ; r_3(x) ; w_1(x)$

   • Conflict between $r_1(x)$ and $w_2(x)$ gives edge $T_1 \to T_2$.

   • Conflict between $w_2(x)$ and $w_1(x)$ gives edge $T_2 \to T_1$.

   • There is a cycle between $T_1$ and $T_2$. Hence, it is not conflict serializable.

3. Option (C): $r_3(x) ; r_2(x) ; r_1(x) ; w_2(x) ; w_1(x)$

   • Conflict between $r_1(x)$ and $w_2(x)$ gives edge $T_1 \to T_2$.

   • Conflict between $w_2(x)$ and $w_1(x)$ gives edge $T_2 \to T_1$.

   • There is a cycle between $T_1$ and $T_2$. Hence, it is not conflict serializable.

4. Option (D): $r_2(x) ; w_2(x) ; r_3(x) ; r_1(x) ; w_1(x)$

   • Conflict between $w_2(x)$ and $r_3(x)$ gives edge $T_2 \to T_3$.

   • Conflict between $w_2(x)$ and $r_1(x)$ gives edge $T_2 \to T_1$.

   • Conflict between $w_2(x)$ and $w_1(x)$ gives edge $T_2 \to T_1$.

   • Conflict between $r_3(x)$ and $w_1(x)$ gives edge $T_3 \to T_1$.

   • The graph has directed edges $T_2 \to T_3$, $T_2 \to T_1$, and $T_3 \to T_1$, which contains no cycles.

Thus, schedule (D) is conflict serializable with the equivalent serial order $T_2 \to T_3 \to T_1$.