Conflict and view serializability

Why it matters

A database interleaves transactions for speed but promises results as if each ran alone. Serializability turns that promise into a testable definition, and the precedence graph test is one of the most frequently asked DBMS exam questions. It also explains what a "serialization failure" error from a serializable database means, and why locking and other protocols are designed the way they are.

The idea

A schedule is serializable if its effect is equivalent to some serial schedule of the same transactions. Which serial order does not matter; any one is correct, because each transaction preserves consistency on its own. The hard part is defining "equivalent" in a way that can be checked. Two definitions are used.

Conflicting operations

Two operations conflict when they belong to different transactions, access the same data item, and at least one of them is a write.

Non-conflicting adjacent operations can be swapped without changing the result. Two schedules are conflict equivalent if one can be turned into the other by such swaps, which is the same as saying every pair of conflicting operations appears in the same order in both. A schedule is conflict serializable if it is conflict equivalent to a serial schedule.

The precedence graph test

1. 1

   Draw a node per transaction

   One node for each transaction in the schedule.
2. 2

   Add an edge for every conflict

   For each pair of conflicting operations where Ti's operation comes first, draw an edge Ti → Tj.
3. 3

   Look for a cycle

   If the graph has a cycle, the schedule is not conflict serializable.
4. 4

   Read off a serial order

   If it is acyclic, any topological order of the graph is an equivalent serial schedule.

Example schedule S: R1(A), R2(A), W1(A), W2(A), R1(B), W2(B). Conflicts on A: R1(A) before W2(A) gives T1 → T2; R2(A) before W1(A) gives T2 → T1; W1(A) before W2(A) gives T1 → T2. A cycle T1 → T2 → T1 exists, so S is not conflict serializable; it is in fact a lost update on A.

View serializability

View equivalence is a weaker condition. Two schedules are view equivalent if each transaction reads the same initial values, each read sees the write of the same transaction in both, and the same transaction performs the final write of each item. A schedule is view serializable if it is view equivalent to some serial schedule.

Every conflict-serializable schedule is view serializable, but not the reverse. The extra schedules involve blind writes (writes without a prior read): R1(A), W2(A), W1(A), W3(A) is not conflict serializable (T1 and T2 conflict in both directions) but is view serializable as T1, T2, T3, because T3's final blind write overwrites everything and nobody read T2's value. Testing view serializability is NP-complete, which is why databases enforce conflict serializability instead.

From theory to engines

Databases do not build precedence graphs for every schedule after the fact; they use protocols that only ever produce serializable schedules. Two-phase locking guarantees conflict serializability by construction. Serializable snapshot isolation in PostgreSQL tracks read-write dependencies and aborts a transaction when it detects a dangerous structure that could form a cycle, which surfaces as a "could not serialize access" error that the application must retry.

Trade-offs

Conflict serializability is slightly conservative (it rejects some correct schedules with blind writes) in exchange for an efficient test and simple enforcement. Full serializability, however enforced, costs throughput through waiting or aborts, which is why many systems default to weaker isolation and add targeted locks where anomalies matter.

In an interview

Do the test aloud: "List conflicting pairs in order: R1(A) before W2(A) is T1 → T2, R2(A) before W1(A) is T2 → T1. That is a cycle, so no equivalent serial order exists; the schedule loses T1's update." If the graph is acyclic, give the topological order as the equivalent serial schedule.