One graph, kept free of cycles
Every concurrency control scheme is an algorithm that keeps one graph without cycles. The schemes differ only in how they learn the edges of the graph and what they do when an edge would close a cycle. If we put the graph on the table first, eight apparently unrelated mechanisms become one family with four variants.
Conflicts and the serialization graph
Recall that two operations conflict if they come from different transactions, touch the same item, and at least one is a write. That gives three kinds of edge:
| Edge | Meaning | Example |
|---|---|---|
| ww (write-write) | T₁ writes X, then T₂ overwrites X | Both update the same wallet |
| wr (write-read) | T₁ writes X, then T₂ reads that value | T₂ reads the new balance |
| rw (read-write, also called an antidependency) | T₁ reads X, then T₂ overwrites X, so T₁ must be ordered before T₂ | T₁ reads the old balance; T₂ then changes it |
Draw an arrow Tᵢ → Tⱼ whenever an operation of Tᵢ comes first and conflicts with an operation of Tⱼ. This is the serialization graph (also called the precedence graph).
The proof takes one line: a graph without cycles can be topologically sorted (put in a line so that every arrow points forward), and that line is a serial schedule that produces the same result.
Small example. T₁ reads X, then T₂ writes X (arrow T₁ → T₂). Later T₂ reads Y, and T₁ writes Y (arrow T₂ → T₁). Now there is a cycle T₁ → T₂ → T₁. No serial order matches: T₁ would need to be both before and after T₂. This schedule is not serializable and the database must not allow it.
The first honest note. Conflict serializability is sufficient but not necessary for correctness. A weaker criterion, view serializability, accepts strictly more schedules, and it is the more faithful definition of "equivalent to a serial run". But testing view serializability is NP-complete (no efficient algorithm is known). Therefore every production system enforces a criterion stricter than correctness requires, because the exact criterion is intractable. Keep this in mind. It comes back several times, and by the end of Multiversion and optimistic schemes it will have a name.
How each scheme relates to the graph
| Scheme | How it learns about edges | What it does about them |
|---|---|---|
| 2PL (two-phase locking) | Never builds the graph; it blocks so that edges can only form in lock-point order | Waits |
| Timestamp ordering | Fixes the topological order up front; rejects any operation that would create a backward edge | Aborts immediately |
| OCC (optimistic) | Reconstructs the relevant edges at commit time | Aborts at commit |
| SSI (serializable snapshot isolation) | Tracks only rw edges, and only two bits of information about them | Aborts a suspected pivot |
| Deterministic | Agrees on the order before execution, so no edge can be out of order | Nothing to do |
Notice what this table says: when a conflict is detected and what is done about it are two independent choices. Timestamp ordering detects at the operation, like 2PL, but it aborts instead of waiting. Our earlier "timing" table (Why concurrency is different) mixed up these two ideas; the table above is the more accurate one.