A Quick Graph Refresher

Concept. The correctness test ahead builds a directed graph from a schedule and checks it for a cycle. 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.

Side-by-side directed graphs: an acyclic graph whose arrows never loop back, and a cyclic graph with a loop.

Figure 1. On the left, an acyclic graph: follow the arrows and you never return to a node, so the nodes line up in order. On the right, a cyclic graph: the loop means no consistent order exists. On the next page, a cycle in a schedule's graph marks the schedule unsafe.

Topological Sort

A topological sort lists a DAG's nodes so that for every edge A to B, A comes before B. A DAG usually has several valid orderings; a graph with a cycle has none.

A 4-node DAG (edges A to B, A to C, B to D, C to D) beside its two valid topological orders listed as text: A to B to C to D, and A to C to B to D.

Figure 2. The DAG has two valid topological orders, A → B → C → D and A → C → B → D; B and C are independent, so either can come first. Each is a safe sequence. On the next page, each valid topological order of a schedule's graph is an equivalent serial run.

Next

Correctness → Now use these two ideas. The next page turns a transaction schedule into a directed graph and reads its cycles to decide when concurrent execution stays correct.