What does it mean for a schedule of concurrent database transactions to be conflict-serializable, and why does obeying the two-phase locking rule (acquire all locks before releasing any) guarantee that property?

## Serial, serializable, conflict-serializable The gold standard for correctness under concurrency is a **serial schedule**: transactions run one after another with no interleaving, so if each transaction preserves the database's invariants on its own, the result does too. Serial execution is correct but slow, so engines interleave and then require the result to be **serializable** — equivalent to *some* serial order (not necessarily the arrival order). "Equivalent" needs a definition, and the practical one is **conflict equivalence**. Two operations **conflict** when all three hold: they belong to different transactions, they access the same data item, and at least one of them is a write. So read/read never conflicts; read/write, write/read and write/write do. Two schedules are conflict-equivalent if one can be transformed into the other by repeatedly swapping *adjacent non-conflicting* operations — swapping conflicting ones could change what a transaction sees or what value survives, so those swaps are forbidden. A schedule is **conflict-serializable** if it is conflict-equivalent to some serial schedule. ## The precedence graph test The mechanical test builds a **precedence graph** (also called a serialization or conflict graph): - one node per committed transaction; - an edge T_i → T_j whenever an operation of T_i conflicts with a later operation of T_j in the schedule (T_i must come first in any equivalent serial order). **Theorem:** the schedule is conflict-serializable if and only if this graph is acyclic. If it is acyclic, any topological sort of it is an equivalent serial order. A cycle means the constraints are contradictory — T1 must precede T2 and T2 must precede T1 — so no serial order matches. Example of a cycle: T1 reads A, T2 writes A, T2 writes B, T1 writes B. The read/write on A gives T1→T2; the write/write on B gives T2→T1. Cycle, so not conflict-serializable. ## Why two-phase locking forces acyclicity Recall the 2PL rule: a transaction has a **growing phase** where it only acquires locks and a **shrinking phase** where it only releases them, with the **lock point** being the boundary — the moment it holds its maximal lock set. Assume the locking is sound in the ordinary way: to read an item you hold at least a shared lock; to write it you hold an exclusive lock; shared conflicts with exclusive and exclusive with exclusive. Now take any precedence edge T_i → T_j. That edge exists because two conflicting operations touched the same item, T_i's first. Conflicting operations require conflicting lock modes on that item, and conflicting locks cannot be held simultaneously. Therefore T_i must have **released** its lock on that item before T_j **acquired** its own. Releasing puts T_i at or past its lock point; acquiring puts T_j at or before its lock point. Chaining the inequalities: `lockpoint(T_i) ≤ release_i(x) < acquire_j(x) ≤ lockpoint(T_j)` so `lockpoint(T_i) < lockpoint(T_j)` for **every** edge. Edges only ever run from an earlier lock point to a later one. If the graph contained a cycle T_1 → T_2 → … → T_1, we could chain those strict inequalities into `lockpoint(T_1) < lockpoint(T_1)` — a contradiction. So the graph is acyclic, so the schedule is conflict-serializable, and sorting transactions by lock point gives the equivalent serial order. That last sentence is the sentence to say out loud in an interview: **under 2PL, the serialization order is the order of lock points.** Under rigorous (strong strict) 2PL, where every lock is held to commit, the lock point effectively coincides with commit, so the serialization order is simply the **commit order** — a property replication and recovery lean on heavily. ## Sufficient, not necessary 2PL is a *local* rule: each transaction obeys it independently, with no global view of the schedule, and serializability emerges anyway. The price of that locality is conservatism. Consider a schedule where T1 reads A, is completely finished with A, and T2 then writes A and later writes B that T1 must read — the schedule may be perfectly conflict-serializable, yet 2PL forbids T1 from acquiring B's lock after it dropped A's. So 2PL accepts a strict subset of the conflict-serializable schedules, and conflict-serializability is itself a strict subset of the broader **view-serializable** schedules (which allow blind writes to be reordered in ways conflict equivalence rejects). View serializability is NP-hard to test, which is why nobody enforces it in a real engine. ## Where this shows up in practice Two things follow. First, the reason a database's SERIALIZABLE level is expensive under locking is that maintaining these guarantees means holding read locks long enough to keep the edge argument valid — drop them early and the transaction stops being two-phase, which is exactly what REPEATABLE READ and READ COMMITTED do. Second, MVCC-based engines that offer serializability cannot use this argument at all, since readers never take locks; they instead detect dangerous structures in the dependency graph at runtime and abort a participant. Both approaches are ultimately protecting the same invariant: keep the precedence graph acyclic.