Conflict Serializability and the Precedence Graph Test

Two transactions can each be correct on its own and still produce a state that no serial execution of the same two would produce. The clearest example is a transfer pair: one transaction debits account A and credits B, another reads both balances to compute a total. If the reader observes A after the debit but B before the credit, it sees money that does not exist in any serial order. The scheduler allowed an interleaving whose result is not equivalent to running the transactions one after the other, and the definition of correctness in this area is exactly that equivalence.

Serial equivalence as the correctness criterion

A schedule is a total order over the operations of several transactions, interleaving them. A serial schedule runs one transaction to completion before starting the next. Serializability says a schedule is correct if it is equivalent to some serial schedule of the same transactions.

Equivalence is not judged on the final state alone, because many schedules produce the same final state by coincidence while exposing intermediate values that never existed. The standard definition uses conflict equivalence: two schedules are equivalent if they order every pair of conflicting operations the same way. Two operations conflict when they belong to different transactions, access the same data item, and at least one of them is a write. A read-read pair never conflicts, two writes to different items never conflict, but a read and a write of the same item always do, in either order, because the read observes either the pre-write or post-write value depending on the order.

Under this definition the test becomes mechanical. Build a graph whose vertices are the transactions. For every pair of conflicting operations where transaction T1’s operation precedes T2’s, add an edge T1 → T2. The schedule is conflict serializable if and only if this precedence graph is acyclic.

Building the graph from a trace

The graph is easy to construct from an operation log. Each read or write records the transaction, the item, and the value or version observed.

def precedence_graph(ops):
    """ops: list of (txn, kind, item) in schedule order, kind in {'r','w'}."""
    edges = set()
    history = []                      # (txn, kind, item) seen so far
    for txn, kind, item in ops:
        for other, okind, oitem in history:
            if other != txn and oitem == item and (kind == 'w' or okind == 'w'):
                edges.add((other, txn))
        history.append((txn, kind, item))
    return edges

def is_serializable(edges, txns):
    # Kahn's algorithm: a schedule is serializable iff every vertex drains.
    indeg = {t: 0 for t in txns}
    for a, b in edges:
        indeg[b] += 1
    ready = [t for t in txns if indeg[t] == 0]
    seen = 0
    while ready:
        t = ready.pop()
        seen += 1
        for a, b in edges:
            if a == t:
                indeg[b] -= 1
                if indeg[b] == 0:
                    ready.append(b)
    return seen == len(txns)

The history scan makes construction quadratic in the number of operations, which is acceptable for the offline analysis it is meant for. A real scheduler does not build the graph after the fact; it maintains the constraints incrementally and refuses operations that would close a cycle, which is what strict two-phase locking does implicitly by holding locks until commit.

A serial order, when one exists, is any topological order of the graph. The graph does not identify a unique serial schedule, and it does not need to: any topological order produces conflict-equivalent results.

Why the graph test is not a scheduler

The graph tells whether a completed schedule was correct. It does not tell a scheduler what to do next, because the future operations are unknown at decision time. A scheduler that admitted an operation because no cycle existed yet can still be forced into a cycle by a later operation, and the only remedies at that point are aborting a transaction or blocking until the cycle resolves itself.

This is the reason practical concurrency control is built from protocols rather than from graph search. Two-phase locking guarantees acyclicity structurally: every transaction acquires all locks before releasing any, so the lock order induces a total order on conflicting accesses, and a cycle would require a transaction to hold a lock while waiting for one it already released, which the protocol forbids. Optimistic validation guarantees it by checking at commit time whether any item read by the committing transaction was written by a transaction that committed during its lifetime.

Both protocols are conservative in the same sense: they reject some serializable schedules. Two-phase locking blocks transactions that could have proceeded safely; optimistic validation aborts transactions whose reads happened to be invalidated. The graph test is the exact boundary, and every practical protocol draws a boundary strictly inside it.

The anomalies the test names

The classical anomalies are recognizable patterns of conflicting access, and naming them by the shape of those accesses is more useful than naming them by folklore.

A dirty read is a write by T1 followed by a read by T2 followed by T1’s abort. The graph records the edge T1 → T2 from the write-read conflict, and the abort makes the value T2 read nonexistent. No cycle is required for this to be a violation; the property that fails is recoverability, which says a transaction may only commit after every transaction whose uncommitted writes it read has committed.

A lost update is two read-modify-write sequences whose writes overwrite each other. T1 reads x, T2 reads x, T1 writes x, T2 writes x. T2’s read precedes T1’s write, which gives T2 → T1; T1’s write precedes T2’s write, which gives T1 → T2. The graph has a two-cycle, so the schedule is not conflict serializable and the test rejects it. What the graph does not tell you is where the fix belongs: the lost update is a failure of read-modify-write atomicity, so the remedy is a lock held across the read and the write, an atomic increment, or a scheduler that refuses the interleaving — not a stronger predicate check.

Write skew, the anomaly that motivates serializable snapshot isolation, is a cycle between two transactions each of which reads what the other writes, with neither writing what the other reads. T1 reads x and writes y; T2 reads y and writes x. T1’s read of x conflicts with T2’s write of x, giving T1 → T2; T2’s read of y conflicts with T1’s write of y, giving T2 → T1. The graph has a two-cycle, and no serial order exists. Every snapshot-based scheme that validates only write-write conflicts misses this shape, which is the subject of serializable snapshot isolation.

Where conflict serializability is too coarse

Conflict serializability treats every pair of accesses to the same item as a conflict, even when the values involved make the conflict harmless. A transaction that writes the value 7 over an existing 7 has not changed anything observable, yet the graph records an edge. A transaction that reads an item and writes it back unchanged similarly creates edges that a value-aware analysis would not.

View serializability is the weaker alternative: it asks only whether the final writes and every read’s observed value match some serial schedule. It is a strictly larger class, and deciding membership is NP-complete, which is why no practical system implements it. Conflict serializability is a conservative approximation chosen because acyclic-graph testing is linear in the number of edges.

There is also a granularity problem. The graph is defined over data items, and the choice of item is the choice of what counts as the same thing. At row granularity, two transactions updating different columns of the same row conflict; at page granularity, two transactions updating different rows of the same page conflict; at table granularity almost everything conflicts. Finer granularity means more bookkeeping and less false conflict, which is the same trade-off that appears in index locking and key ranges. Predicate-level reasoning — treating “the set of rows matching this WHERE clause” as the item — is the finest granularity and the only one that makes phantoms visible to the graph, since a new row inserted into a range read conflicts with the read even though no existing item was touched.

What survives into practice

The precedence graph is the reference definition against which every isolation level is measured. When a system claims repeatable read, the claim is a statement about which cycles its scheduler can produce. When a benchmark or a conformance test asserts that a history is serializable, the assertion is usually this test, applied offline to a recorded trace.

The practical residue is three habits. First, think in terms of conflicting pairs rather than in terms of operations, because that is what determines whether order matters. Second, remember that acyclic graphs admit many serial orders and the choice among them is not constrained by correctness, only by performance and by what the application assumes. Third, recognize that acyclicity is a property of the whole schedule, so a scheduler that decides locally can only guarantee it by being conservative globally. The protocols that follow in this cluster are all attempts to buy that global guarantee at a bounded local cost.