Consider the database transactions T1 and T2, and data items X and Y. Which of…

Answer: Only the schedule "W2(X), R1(X), W2(Y), W1(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1)" is conflict serializable (equivalent to executing the second transaction before the first).

Method (precedence graph):

• Create a node for each transaction and add a directed edge from transaction A to transaction B whenever an operation of A on a data item precedes a conflicting operation of B on the same data item (read–write, write–read, or write–write). If the graph has a cycle, the schedule is not conflict serializable; if it is acyclic, the topological order gives an equivalent serial schedule.

Apply this to each schedule:

• Schedule: R1(X), W2(X), W1(Y), W2(Y), R1(X), W1(X), COMMIT(T2), COMMIT(T1) — Conflicts produce edges both from the first transaction to the second (R1(X) before W2(X), W1(Y) before W2(Y)) and from the second to the first (W2(X) before the later R1(X)). The edges form a cycle, so not conflict serializable.

• Schedule: W2(X), R1(X), W2(Y), W1(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1) — All conflicts go from the second transaction to the first (writes by the second precede reads/writes by the first). The precedence graph is acyclic, so this schedule is conflict serializable and equivalent to running the second transaction before the first.

• Schedule: R1(X), W1(Y), W2(X), W2(Y), R1(X), W1(X), COMMIT(T1), COMMIT(T2) — There is a read–write conflict R1(X) before W2(X) (edge from the first to the second) and later a write–read conflict W2(X) before a later R1(X) (edge from the second to the first). Those opposing edges create a cycle, so not conflict serializable.

• Schedule: W2(X), R1(X), W1(Y), W2(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1) — The write of X by the second before the read by the first gives an edge from the second to the first, while the write of Y by the first before the write by the second gives an edge from the first to the second. Those two edges form a cycle, so not conflict serializable.

Conclusion: Only the schedule where the second transaction's writes on X and Y occur before the first transaction's reads and writes (the schedule beginning with W2(X), R1(X), W2(Y), W1(Y), ...) is conflict serializable; all other given interleavings produce cycles in the precedence graph.