Serializability

Cycle Means Not Serializable

A cyclic precedence graph blocks conflict-serializability.

highlighted = computed this step

A cycle blocks conflict serializability

Conflict-serializability is decided by the precedence graph. When the graph cycles, no serial order can preserve all conflicting operation orders. Note: the verdict caption is generated by the cycle check.

cycle check\text{cycle check}

Highlighted cycle

The recomputed graph has 2 edges and a cycle of length 2. Note: the cycle edges are highlighted in the render.

edges=2,cycle length=2\text{edges}=2,\quad \text{cycle 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.

Cycle checkstepT1T20R(A)1W(A)2W(B)3W(B) conflict-serializable: no; cycle: T1,T2T1T2

Summary

A cyclic precedence graph is the exact obstruction for conflict-serializability. Note: conflict-serializability is exact here; view-serializability, locks, and recovery are deferred.

cycle obstruction\text{cycle obstruction}