The Gold Standard for Isolation
Serializability is the strongest isolation guarantee for database transactions. A schedule (interleaved execution of multiple transactions) is serializable if its outcome — the final database state and the values returned to each transaction — is equivalent to some serial execution of those same transactions. A serial execution runs transactions one after another, with no overlap. Serializability does not require a specific serial order; it just requires that some valid serial ordering exists that produces the same result.
Why Serializability Matters
Without serializability, concurrent transactions can produce anomalies that are impossible in any serial execution. Consider two transactions, T1 and T2, both transferring $100 between accounts. If both read the same initial balance before either writes, one transfer can be lost. Under a serializable schedule, the result must equal either "T1 then T2" or "T2 then T1" — both transfers are correctly applied.
Conflict Serializability
The most widely used test for serializability is conflict serializability. Two operations from different transactions conflict if they access the same data item and at least one is a write:
- Read-Write (R-W) conflict: T1 reads X, T2 writes X (or vice versa).
- Write-Write (W-W) conflict: T1 writes X, T2 writes X.
A schedule is conflict serializable if you can swap the order of non-conflicting operations to transform it into a serial schedule. This is equivalent to checking the precedence graph (also called the serialization graph).
Precedence Graph (Serialization Graph)
Build a directed graph where:
- Each transaction is a node.
- Draw an edge from Ti to Tj if Ti performs an operation that conflicts with a later operation by Tj. This edge means "Ti must come before Tj in any equivalent serial order."
If the precedence graph has no cycles, the schedule is conflict serializable — a topological sort of the graph gives a valid serial order. If the graph has a cycle, no serial ordering can produce the same result, and the schedule is not conflict serializable.
View Serializability
View serializability is a more permissive definition: a schedule is view serializable if, for every data item, (1) the same transaction performs the initial read, (2) the same read-write dependencies exist, and (3) the same transaction performs the final write. View serializability allows some schedules that conflict serializability rejects (called blind writes). However, testing for view serializability is NP-complete, making it impractical. In practice, databases use conflict serializability.
Serializable Snapshot Isolation (SSI)
Modern PostgreSQL implements serializability using SSI (Serializable Snapshot Isolation). SSI starts with MVCC snapshot isolation (which already prevents most anomalies) and adds lightweight tracking of read-write dependencies. When SSI detects a pattern that could form a cycle in the precedence graph, it aborts one of the transactions. This is an optimistic approach — transactions run concurrently and are only aborted if a potential violation is detected, rather than blocking them preemptively with locks.
Building a Precedence Graph
Consider three transactions executing concurrently on data items X and Y:
T1: Read(X) Write(X)
T2: Read(X) Write(Y)
T3: Read(Y) Write(X)
Identifying conflicts:
- T1 writes X, then T2 reads X → edge T1 → T2 (W-R conflict on X)
- T2 writes Y, then T3 reads Y → edge T2 → T3 (W-R conflict on Y)
- T1 writes X, then T3 writes X → edge T1 → T3 (W-W conflict on X)
Precedence graph:
T1 → T2 → T3
T1 ------→ T3
No cycle exists! A topological sort gives the serial order: T1, T2, T3. The concurrent schedule produces the same result as running T1, T2, T3 in sequence.
A non-serializable example:
T1: Read(X) Write(Y)
T2: Read(Y) Write(X)
Conflicts:
- T1 reads X, T2 writes X → edge T1 → T2 (T2's write comes after T1's read)
- T2 reads Y, T1 writes Y → edge T2 → T1 (T1's write comes after T2's read)
Precedence graph:
T1 → T2 → T1 (CYCLE!)
A cycle exists! This schedule is not conflict serializable. Neither "T1 then T2" nor "T2 then T1" produces the same result as this interleaved execution. Under SSI, PostgreSQL would detect this dangerous pattern and abort one of the transactions, asking the application to retry it.