Conflict Serializability

When several transactions run at once, their reads and writes interleave into a schedule. Running them one-at-a-time — a serial schedule — is always correct but allows no overlap. The goal is to overlap for speed while still getting a result *equivalent* to some serial order. A schedule that does is serializable, and the practical test for it is conflict serializability.

What counts as a conflict

Two operations conflict when they come from *different* transactions, touch the *same* item, and *at least one is a write*. Only conflicting operations have an order that matters — swapping two non-conflicting operations never changes the outcome. A schedule is conflict-serializable if reordering only its non-conflicting operations can turn it into a serial schedule.

The precedence graph test

1. 1Draw one node per transaction.
2. 2For every conflict where an operation of Ti comes *before* a conflicting operation of Tj, add an arrow Ti → Tj.
3. 3Check the graph for a cycle.
4. 4No cycle ⇒ conflict-serializable (a valid serial order is any topological sort). A cycle ⇒ *not* serializable — no equivalent serial order exists.

A worked cycle

Take the schedule R1(A), W2(A), R2(B), W1(B). There are two conflicts. R1(A) precedes W2(A) on item A (read vs write) → edge T1 → T2. R2(B) precedes W1(B) on item B → edge T2 → T1. Those two arrows form the cycle T1 → T2 → T1, so this schedule is not conflict-serializable — you cannot untangle it into either T1;T2 or T2;T1.

Conflicts:  R1(A) before W2(A)  =>  T1 -> T2
            R2(B) before W1(B)  =>  T2 -> T1

Precedence graph:   T1 --> T2
                     ^       |
                     +-------+      cycle  =>  NOT serializable