Part 3 of 5 · 1 min read
Conflict serializability and the precedence graph
An interleaved schedule is safe if it produces the same effect as some serial schedule, checkable via a precedence graph.
Think of two people rearranging furniture in a shared room at the same time. Their interleaved actions are fine as long as the room ends up looking exactly like it would have if one person had finished first, then the other.
In plain words: an interleaved schedule is conflict serializable if it is equivalent to some serial schedule, meaning it produces the same final effect, based only on which pairs of operations conflict: two operations conflict if they come from different transactions, access the same data item, and at least one of them is a write. A precedence graph tests this directly: draw one node per transaction, and an edge from transaction A to transaction B whenever an operation of A conflicts with, and comes before, an operation of B. The schedule is conflict serializable exactly when this graph has no cycle.
A worked example. If transaction A writes a row before transaction B reads that same row, an edge A to B is added to the precedence graph; if no such edges ever form a cycle back to A, the schedule is conflict serializable.
The key lines. No new SQL; building a precedence graph is an analysis technique applied to a schedule, not a database operation.
Conflict serializability, precedence graph
A schedule is conflict serializable if it is equivalent to some serial schedule based on conflicting operation order; a precedence graph, with an edge per conflict, tests this by checking for cycles, concluding serializability exactly when none exist.
Example: two people's interleaved furniture rearranging being equivalent to one finishing before the other starts is the conflict-serializability idea applied to furniture.