A Quick Graph Refresher
Concept. A directed graph captures which operations must come before others. It needs two graph ideas: cyclic vs acyclic, and topological sort, a linear order that respects every edge.
Intuition. Getting dressed is a topological sort: socks before shoes, pants before belt. If the rules also demanded shoes before socks, that loop is a cycle, and no valid order exists. The next page builds a graph from a transaction schedule and reads it the same way: acyclic means a safe order exists, a cycle means none does.
Cyclic vs Acyclic Graphs
A directed graph is acyclic (a Directed Acyclic Graph, or DAG) when no path loops back to a node it already visited, and cyclic when at least one path does.
Figure: Acyclic graphs have no directed cycleTwo neutral diagrams compare an acyclic chain T1 to T2 to T3 with a cycle T1 to T2 to T3 to T1. Arrowheads show direction; color is not needed to distinguish them.
Figure 1. Left: no directed cycle, so an order respecting every edge exists. Right: the cycle prevents such an order. A transaction schedule is conflict-serializable exactly when its conflict graph has no cycle.
Topological Sort
A topological sort lists a DAG's nodes so that for every edge A to B, A comes before B. A DAG can have more than one valid ordering; a graph with a cycle has none.
Figure: A topological order respects every edgeThe DAG has edges A to B, A to C, B to D, and C to D. Its two topological orders are A B C D and A C B D. B and C have no ordering constraint between them.
Figure 2. Both A → B → C → D and A → C → B → D respect every edge. B and C have no ordering constraint between them. In a conflict graph, a topological order gives an equivalent serial transaction order.