Conflict Serializability

What Counts as a "Conflict"

Two operations from different transactions conflict if they satisfy all three conditions: (1) they belong to different transactions, (2) they act on the same data item, and (3) at least one of them is a write. So: R-R is never a conflict (two reads never interfere); R-W, W-R, and W-W on the same item are all conflicts. Two operations that don't conflict can be swapped (their relative order exchanged) without changing the effect of the schedule — either they touch different data items, or they're both reads.

Definition

A schedule is conflict-serializable if you can transform it into some serial schedule purely by repeatedly swapping adjacent, non-conflicting operations (never touching conflicting pairs). If such a sequence of swaps exists, the schedule is guaranteed to produce the same result as that serial schedule.

Worked Example — Conflict-Serializable

Recall schedule S1 from 23.3:

1. R1(A)  2. W1(A)  3. R2(A)  4. R1(B)  5. W2(A)  6. W1(B)  7. R2(B)  8. W2(B)

Swap step 3 R2(A) and step 4 R1(B) — different data items (A vs. B), non-conflicting:

R1(A) W1(A) R1(B) R2(A) W2(A) W1(B) R2(B) W2(B)

Swap W2(A) (now after R1(B)) and W1(B) — different items, non-conflicting:

R1(A) W1(A) R1(B) R2(A) W1(B) W2(A) R2(B) W2(B)

Swap R2(A) and W1(B) — different items, non-conflicting:

R1(A) W1(A) R1(B) W1(B) R2(A) W2(A) R2(B) W2(B)

This is exactly the serial schedule <T1, T2>! Three legal swaps (each between non-conflicting operations on different items) transformed S1 into a serial order, proving S1 is conflict-serializable.

Worked Example — NOT Conflict-Serializable

Consider a smaller schedule S2 where T1 does R(A), W(B) and T2 does R(B), W(A):

1. R1(A)  2. R2(B)  3. W1(B)  4. W2(A)

Check conflicts: R2(B) (step 2) and W1(B) (step 3) conflict on B, and R2 comes before W1 — so T2 must logically precede T1 for B. But R1(A) (step 1) and W2(A) (step 4) conflict on A, and R1 comes before W2 — so T1 must logically precede T2 for A. These two requirements contradict each other (T2 before T1, and T1 before T2), so no sequence of valid swaps can ever turn S2 into a serial schedule — S2 is not conflict-serializable.

Edge Cases

• Swapping is only ever valid between adjacent operations at each step — you cannot jump an operation past a conflicting one, even indirectly; every intermediate swap must itself be non-conflicting.
• A schedule with zero conflicting pairs at all (transactions touch fully disjoint data) is trivially conflict-serializable — every interleaving is equivalent to every serial order.
• Conflict serializability only cares about the existence of a legal reordering; it says nothing about which serial order the DBMS should prefer or how many swaps are needed.

Key Takeaways / Interview Angle

• Q: Why is R-R never a conflict? Because two reads never change any data, so their relative order can never affect the final result — swapping them is always safe.
• Q: How does a real DBMS use this concept? It doesn't run the swap algorithm live — instead, locking protocols (e.g., two-phase locking) are designed so that any schedule they permit is automatically guaranteed to be conflict-serializable, without ever having to construct or check swaps at runtime.
• Q: Is conflict serializability the only kind of serializability? No — it is the practical, easy-to-test standard used by real systems, but 23.5 introduces the broader (and less commonly implemented) view serializability.