Serializability

Acyclic Means Serializable

An acyclic precedence graph provides an equivalent serial order.

highlighted = computed this step

Acyclic graph gives a serial order

If the precedence graph has no cycle, a topological order gives an equivalent serial order. The engine picks the deterministic smallest-id order when choices tie. Note: the topo order is displayed in the render.

acyclic graph\text{acyclic graph}

Topo order

The recomputed cycle length is 0 and the topo order length is 2. Note: the verdict and topo order fall out of the same graph.

cycle length=0,topo length=2\text{cycle length}=0,\quad \text{topo length}=2

conflict-serializability is an exact SUFFICIENT criterion; a cyclic precedence graph is provably not conflict-serializable; view-serializability, lock scheduling, and recovery are beyond these tiny traces - no product claims.

Acyclic schedulestepT1T20R(A)1R(B)2W(A)3W(A) conflict-serializable: yes; topo: T1,T2T1T2

Summary

Acyclic means the graph admits an equivalent serial order. Note: conflict-serializability is exact here; view-serializability, locks, and recovery are deferred.

topo order\text{topo order}