Precedence Graph

Definition

A precedence graph (also called a serializability graph) is the standard tool used to test conflict serializability without manually trying every possible sequence of swaps. Build it as follows:

1. Create one node per transaction in the schedule.
2. For every pair of conflicting operations (different transactions, same data item, at least one is a write) where transaction Ti's operation comes before transaction Tj's operation in the schedule, draw a directed edge Ti → Tj.

Theorem: a schedule is conflict-serializable if and only if its precedence graph has no cycles. If the graph is acyclic, any topological sort of the nodes gives a valid equivalent serial order; if it has even one cycle, no equivalent serial order can exist.

Worked Example 1 — Acyclic Graph (Conflict-Serializable)

Recall schedule S1 from 23.3/23.4:

1. R1(A)  2. W1(A)  3. R2(A)  4. R1(B)  5. W2(A)  6. W1(B)  7. R2(B)  8. W2(B)

Check every conflicting pair:

• On A: R1(A)@1 & W2(A)@5 → T1→T2. W1(A)@2 & R2(A)@3 → T1→T2. W1(A)@2 & W2(A)@5 → T1→T2.
• On B: R1(B)@4 & W2(B)@8 → T1→T2. W1(B)@6 & R2(B)@7 → T1→T2. W1(B)@6 & W2(B)@8 → T1→T2.

Every single conflict produces the same direction, T1→T2. The graph is: one node T1, one node T2, one edge T1→T2. No cycle exists (impossible with only 2 nodes and edges all one direction) → S1 is conflict-serializable, and the only topological order is <T1, T2> — matching exactly what the swap-based proof in 23.4 found.

Worked Example 2 — Cyclic Graph (NOT Conflict-Serializable)

Recall schedule S2 from 23.4 (T1: R(A), W(B); T2: R(B), W(A)):

1. R1(A)  2. R2(B)  3. W1(B)  4. W2(A)

Conflicts: R2(B)@2 & W1(B)@3 → T2→T1 (T2's read precedes T1's write on B). R1(A)@1 & W2(A)@4 → T1→T2 (T1's read precedes T2's write on A).

The graph has nodes {T1, T2} and both edges T1→T2 and T2→T1 — a 2-node cycle. Since the graph has a cycle, S2 is not conflict-serializable, confirming the earlier swap-based conclusion.

Reading a Larger Graph

With 3+ transactions the same rule applies: draw every conflict edge, then look for any cycle (not just 2-node cycles — a 3-node cycle T1→T2→T3→T1 is just as disqualifying). If the graph is a DAG (directed acyclic graph), a topological sort exists (possibly more than one, if the DAG isn't a total order) — each valid topological sort is an equivalent serial schedule.

Edge Cases

• Multiple conflicting operation pairs between the same two transactions on different items only ever add a duplicate edge in the same direction (as seen in Worked Example 1) or, if directions genuinely differ across items, immediately create a 2-node cycle (as in Worked Example 2) — there's no in-between state for two nodes.
• A precedence graph with no edges at all (transactions share no conflicting operations) is trivially acyclic — the schedule is conflict-serializable in every possible order.
• The precedence graph only encodes conflict relationships — it deliberately throws away non-conflicting operations (like blind writes' relative order), which is exactly why it tests conflict serializability and not the broader view serializability.

Key Takeaways / Interview Angle

• Q: What is the precedence graph test, in one line? Build a node per transaction, an edge Ti→Tj per conflict where Ti's operation precedes Tj's on the same item — acyclic means conflict-serializable, cyclic means it is not.
• Q: Why is this more practical than the swap-based definition? Cycle detection in a directed graph is a well-known, efficient (linear-time) algorithm, whereas exhaustively searching for a valid swap sequence would be far more expensive to implement as a live concurrency control check.