Transactions & Concurrency
Histories, Schedules, and Serializability
A history orders reads, writes, commits, and aborts from transactions. Serializability asks whether committed effects and observations are equivalent to some serial order; conflict graphs provide a practical sufficient test, while view serializability is broader.
- Notation makes interleavings reviewable.
- Conflicts require same item, different transactions, and a write.
- An acyclic precedence graph proves conflict serializability.
- View serializability is more general.
- Recoverability is a separate axis.
Start: counter X = 0. T1 and T2 each mean “increment X once.”
H = r1(X=0), r2(X=0), w1(X=1), c1, w2(X=1), c2
Edges: T1 → T2 from r1(X) before w2(X) (and w1(X) before w2(X)); T2 → T1 from r2(X) before w1(X).
The cycle T1 → T2 → T1 proves H is not conflict-serializable. Both transactions commit, but final X = 1 violates the invariant X = number of committed increments = 2. T2 reads the initial committed value, and its write follows c1, so the history contains no dirty read or dirty write.| Property | Question |
|---|---|
| Serial | Did transactions run without interleaving? |
| Conflict-serializable | Can conflicting operations be reordered to a serial history? |
| View-serializable | Are read-from relations and final writes equivalent to a serial history? |
| Strict | Are uncommitted writes neither read nor overwritten? |
| Strict serializable | Is it serializable and consistent with real-time order? |
The trace loses one committed increment without exposing uncommitted data: both transactions derive the same replacement value from X=0, and T2 overwrites X only after T1 commits. The precedence cycle rules out either serial order, each of which would finish at X=2. A graph is an analysis model, not a claim that an engine literally constructs this graph for every execution.