Question 39

A schedule is conflict serializable if and only if its precedence graph is directed and acyclic.

Two operations on the same data item conflict if at least one of them is a write and they belong to different transactions:

• Schedule (A): $r_1(x); r_2(x); w_1(x); r_3(x); w_2(x)$

  • $r_2(x) < w_1(x) \implies T_2 \to T_1$
  • $w_1(x) < w_2(x) \implies T_1 \to T_2$
    Cycle: $T_1 \leftrightarrow T_2$. Not conflict serializable.

• Schedule (B): $r_2(x); r_1(x); w_2(x); r_3(x); w_1(x)$

  • $r_1(x) < w_2(x) \implies T_1 \to T_2$
  • $w_2(x) < w_1(x) \implies T_2 \to T_1$
    Cycle: $T_1 \leftrightarrow T_2$. Not conflict serializable.

• Schedule (C): $r_3(x); r_2(x); r_1(x); w_2(x); w_1(x)$

  • $r_1(x) < w_2(x) \implies T_1 \to T_2$
  • $w_2(x) < w_1(x) \implies T_2 \to T_1$
    Cycle: $T_1 \leftrightarrow T_2$. Not conflict serializable.

• Schedule (D): $r_2(x); w_2(x); r_3(x); r_1(x); w_1(x)$

  • $w_2(x) < r_3(x) \implies T_2 \to T_3$
  • $w_2(x) < r_1(x) \implies T_2 \to T_1$
  • $w_2(x) < w_1(x) \implies T_2 \to T_1$
  • $r_3(x) < w_1(x) \implies T_3 \to T_1$
    Edges in graph: $T_2 \to T_3$ and $T_3 \to T_1$ (and $T_2 \to T_1$).
    There are no cycles! A valid topological ordering is $T_2, T_3, T_1$.

Thus, schedule D is conflict serializable.