An interleaved schedule is correct when it behaves as if the transactions ran one at a time. Build the precedence graph — an edge Ti→Tj whenever an operation of Ti conflicts with and precedes one of Tj on the same item — and the schedule is serializable exactly when that graph is acyclic. Down the center a schedule of reads and writes goes in, the engine builds the graph, the verdict comes out. The blue team builds and defends it; the red team tries to break it.
source Eswaran, Gray, Lorie & Traiger, The Notions of Consistency and Predicate Locks in a Database System (1976), CACM 19(11):624–633 — dl.acm.org/doi/10.1145/360363.360369. Rendered, not quoted.
Serializability is not guessed; it falls out of a directed graph:
nodes are the transactions. edge Ti→Tj is drawn whenever an operation of Ti conflicts with and precedes an operation of Tj on the same item. verdict: the schedule is conflict-serializable if and only if this graph has no cycle — a topological sort of an acyclic graph is a serial order the schedule is conflict-equivalent to.
Edges of the current schedule:
| from | → | to | via item |
|---|
Acyclicity is the gold standard: a schedule as correct as running each transaction alone. But a graph test only judges a finished schedule. To guarantee acyclicity while transactions still run, you need a protocol.
That protocol is two-phase locking — grow all locks, then release, never re-acquire. Its theorem: every 2PL schedule is conflict-serializable, i.e. its precedence graph is provably acyclic. This sphere proves the property; the neighbour enforces it. Each sphere is the next one's premise.
The blue team's live check: for every schedule below, compare the graph verdict (acyclic?) against the ground truth (exhaustive search over all t! serial orders). If red tampers, this badge is where it shows.
A schedule is an interleaving of the operations of several transactions on shared data items. Each operation is a read or a write of one item, tagged by its transaction. Two operations conflict only if they touch the same item, belong to different transactions, and at least one is a write:
| pair | same item | conflict? |
|---|---|---|
| read / read | yes | no |
| read / write | yes | RW — yes |
| write / read | yes | WR — yes |
| write / write | yes | WW — yes |
Order matters: the earlier operation of a conflicting pair points to the later one. That single arrow is what you feed the panel below.
Pick any schedule — the graph is built and the cycle test is run on the spot, never looked up. The serial order (when it exists) is a live topological sort.
What the machine produces, proven: for every constructed schedule the graph verdict equals the ground truth conflict-serializable ⟺ acyclic, checked exhaustively against all t! serial orders. A purely serial schedule is a chain; the classic lost-update interleaving is a cycle and is rejected; a write-write-only cycle is caught by the WW edge.
The blue team's witness (left) confirms these live; the red team (right) tries to make the graph lie.
The trade is deliberate: deciding view-serializability is NP-complete, while the cycle test is linear. The database picks the cheap, conservative test and refuses some legal schedules on purpose. "Serializable" here means conflict-serializable — one honest choice among several.
"Serializable means the operations do not interleave." Cut. Heavy interleaving is fine — serializable means conflict-equivalent to some serial order, not run without overlap.
"A cycle-free graph means no deadlock." Cut. Wrong graph. Precedence-graph acyclicity is about serializing a completed schedule; deadlock is a cycle in the wait-for graph.
"Two writes to the same item do not conflict if they store the same value." Cut. WW conflict is defined by operation and order, not value — dropping it is exactly the red team's tamper (window 6).
The red team's move: stop tracking write-write edges — keep only read-write ones. A schedule whose only cycle rides a WW edge now looks acyclic, and the engine wrongly calls it serializable. The witness (window 7) is watching.
Drop the write-write edge and the write-write cycle vanishes — the graph goes acyclic, the verdict flips to serializable, but the exhaustive ground truth still says non-serializable. The witness recomputes, disagrees, and turns red. Nothing is faked; the attack is real and it is caught.