Conflict Serializability

Why interleave transactions?

A busy database runs hundreds of transactions at the same time. If it ran them strictly one after another, users would wait a long time. So the database interleaves their operations: a read from one transaction, a write from another, and so on. The order of all these operations is called a schedule.

Interleaving is only allowed if the result is as if the transactions had run one at a time. Then nobody can tell the difference. Such a schedule is called serializable.

• A serial schedule runs every transaction completely before the next one starts. Always correct, but slow.
• A serializable schedule is interleaved but gives the same result as some serial schedule.

Conflicting operations

Two operations conflict if all three are true:

1. they belong to different transactions,
2. they use the same data item,
3. at least one of them is a write.

First	Then	Conflict?	Why
R1(A)	R2(A)	❌ No	Reading changes nothing
R1(A)	W2(A)	✅ Yes	T1 must read the value before T2 changes it
W1(A)	R2(A)	✅ Yes	T2 must see T1’s new value
W1(A)	W2(A)	✅ Yes	The last write wins, so the order decides the final value

Swapping two non-conflicting neighbouring operations never changes the result. A schedule is conflict serializable if such swaps can turn it into a serial schedule.

The precedence graph test

1. Draw one node per transaction.
2. For every conflicting pair where an operation of Ti comes before one of Tj, draw an edge Ti → Tj (“Ti must come first”).
3. Cycle → not conflict serializable. No cycle → serializable, and any topological order of the graph is an equivalent serial schedule.

Example: the lost update

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

• R1(A) before W2(A) → T1 → T2
• R2(A) before W1(A) → T2 → T1
• W1(A) before W2(A) → T1 → T2

T1 → T2 → T1 is a cycle: not serializable. And it really is a bug. Both transactions read A (say ₹100), T1 adds ₹50 and writes ₹150, then T2 subtracts ₹30 from the value it read and writes ₹70. T1’s update is lost. No serial order could produce ₹70.

Example: three transactions

R2(A)  W2(A)  R3(B)  W3(B)  R1(A)  R3(C)  W1(B)  W3(C)

• W2(A) before R1(A) → T2 → T1 (R2(A) and R1(A) are both reads, so that pair doesn’t count)
• R3(B) and W3(B) before W1(B) → T3 → T1
• Item C is used only by T3, so no conflict there.

No cycle, so the schedule is conflict serializable, equivalent to the serial order T2 → T3 → T1 (T3 → T2 → T1 works too).

Code

import re
from graphlib import TopologicalSorter, CycleError

def precedence_graph(schedule):
    ops = [(k, int(t), x) for k, t, x in re.findall(r"([RW])(\d)\((\w)\)", schedule)]
    edges = set()
    for i, (k1, t1, x1) in enumerate(ops):
        for k2, t2, x2 in ops[i + 1:]:
            if t1 != t2 and x1 == x2 and "W" in (k1, k2):
                edges.add((t1, t2))           # Ti must come before Tj
    return sorted({t for _, t, _ in ops}), sorted(edges)

def serial_order(schedule):
    txns, edges = precedence_graph(schedule)
    ts = TopologicalSorter()
    for t in txns:
        ts.add(t)
    for a, b in edges:
        ts.add(b, a)                          # b comes after a
    try:
        return list(ts.static_order())
    except CycleError:
        return None                           # not conflict serializable

print(precedence_graph("R1(A) R2(A) W1(A) W2(A)"))   # ([1, 2], [(1, 2), (2, 1)])
print(serial_order("R1(A) R2(A) W1(A) W2(A)"))       # None
print(serial_order("R2(A) W2(A) R3(B) W3(B) R1(A) R3(C) W1(B) W3(C)"))   # [2, 3, 1]

How real databases guarantee it

Databases don’t test schedules after the fact. They use protocols that only allow serializable schedules:

• Two-phase locking (2PL): a transaction first acquires all its locks, then releases them, and never acquires a lock after releasing one. Every 2PL schedule is conflict serializable.
• Timestamp ordering and serializable snapshot isolation (PostgreSQL’s SERIALIZABLE level) detect dangerous patterns and abort one of the transactions.

View serializability is a weaker condition that accepts a few more schedules (those with “blind writes”), but testing it is NP-complete, so practical systems stick to conflict serializability.

Common mistakes

• Counting read–read pairs as conflicts.
• Drawing the edge the wrong way. The transaction whose operation comes first points to the other one.
• Comparing operations of the same transaction. Their order is fixed anyway.
• Forgetting that one cycle anywhere is enough to make the whole schedule non-serializable.