Precedence Graph

All our theoretical groundwork—schedules, serial schedules, equivalence, conflicts—culminates in this page. The precedence graph (also called serializability graph or serialization graph) transforms the abstract question "Is this schedule conflict-serializable?" into a concrete, efficient algorithm.

The precedence graph method is:

• Complete: It correctly identifies ALL conflict-serializable schedules
• Sound: Every schedule it accepts IS conflict-serializable
• Efficient: Runs in polynomial time O(n² × m²) where n = transactions, m = operations
• Constructive: When serializable, it provides an equivalent serial order

This is the standard algorithm taught in every database course and serves as the foundation for understanding how real concurrency control protocols work. Whether you're analyzing schedules manually, implementing a database scheduler, or understanding isolation levels, the precedence graph is your essential tool.

Formal Definition

Given a schedule S over transactions T = {T₁, T₂, ..., Tₙ}, the precedence graph G(S) = (V, E) is a directed graph where:

Vertices (V): One vertex for each transaction Tᵢ in S

Edges (E): A directed edge Tᵢ → Tⱼ exists if and only if there is a conflict between Tᵢ and Tⱼ where Tᵢ's operation appears before Tⱼ's operation in S

(Tᵢ → Tⱼ) ∈ E  ⟺  ∃ conflicting operations oᵢ ∈ Tᵢ, oⱼ ∈ Tⱼ
                   such that oᵢ <S oⱼ (oᵢ precedes oⱼ in S)

Intuition: Ordering Constraints as Edges

Each edge represents an ordering constraint:

• Tᵢ → Tⱼ means "Tᵢ must come before Tⱼ in any equivalent serial schedule"

Why? Because there's a conflict where Tᵢ's operation happens first. In any equivalent serial schedule, this ordering must be preserved, which means Tᵢ must complete entirely before Tⱼ starts.

Edge Types by Conflict

Edges arise from three types of conflicts:

All three create the same type of edge: Tᵢ → Tⱼ

Multiple conflicts between the same pair: If there are multiple conflicts between Tᵢ and Tⱼ (e.g., on different data items), they might create edges in the same direction (Tᵢ → Tⱼ) or opposite directions (Tᵢ → Tⱼ and Tⱼ → Tᵢ). Opposite-direction edges between the same pair form a cycle of length 2.

Step-by-Step Algorithm

Algorithm: ConstructPrecedenceGraph(S)

Input: Schedule S over transactions T = {T₁, T₂, ..., Tₙ}
Output: Precedence graph G = (V, E)

1. Initialize G:
   - V = {T₁, T₂, ..., Tₙ}  // One vertex per transaction
   - E = ∅                   // Empty edge set initially

2. For each data item X accessed in S:
   a. Collect all operations on X in schedule order
   
   b. For each pair of operations (oᵢ, oⱼ) on X where:
      - oᵢ ∈ Tᵢ and oⱼ ∈ Tⱼ with i ≠ j
      - oᵢ appears before oⱼ in S
      - At least one of oᵢ, oⱼ is a write
      
      Add edge Tᵢ → Tⱼ to E (if not already present)

3. Return G = (V, E)

Complexity Analysis

• Step 2a: For each data item, O(m) operations to collect
• Step 2b: For each pair C(m,2) = O(m²) pairs to check
• With d data items: O(d × m²) conflict checks
• Each check is O(1), edge insertion is O(1) with hash set
• Total: O(d × m²) or equivalently O(n² × m²) where n = transactions

The Fundamental Theorem

Theorem (Conflict Serializability Test):

A schedule S is conflict-serializable if and only if its precedence graph G(S) is acyclic.

S is conflict-serializable  ⟺  G(S) is acyclic

Proof Sketch

If direction (Acyclic → Serializable):

If G(S) is acyclic, it has a topological ordering T_{π(1)}, T_{π(2)}, ..., T_{π(n)}. This ordering respects all edges: if Tᵢ → Tⱼ, then Tᵢ appears before Tⱼ.

Construct serial schedule Ss = T_{π(1)} · T_{π(2)} · ... · T_{π(n)}.

For every conflict oᵢ <S oⱼ in S, we have edge Tᵢ → Tⱼ in G(S), which means Tᵢ comes before Tⱼ in the topological order, so oᵢ <Ss oⱼ in Ss.

Thus S ≡c Ss (all conflicts have same ordering). Therefore S is conflict-serializable.

Only if direction (Serializable → Acyclic):

Suppose G(S) has a cycle: Tᵢ₁ → Tᵢ₂ → ... → Tᵢₖ → Tᵢ₁

This means:

• Tᵢ₁ must precede Tᵢ₂ in any equivalent serial schedule
• Tᵢ₂ must precede Tᵢ₃
• ...
• Tᵢₖ must precede Tᵢ₁

By transitivity: Tᵢ₁ must precede itself. Contradiction!

No serial schedule can satisfy all constraints, so S is not conflict-serializable.

Method 1: Depth-First Search (DFS)

The standard algorithm for cycle detection in directed graphs:

Algorithm: HasCycle(G)

Input: Directed graph G = (V, E)
Output: True if G has a cycle, False otherwise

1. color[v] = WHITE for all v ∈ V
   // WHITE = unvisited, GRAY = in progress, BLACK = finished

2. For each vertex v ∈ V:
   If color[v] = WHITE:
      If DFS-Visit(v) returns True:
         Return True  // Cycle found

3. Return False  // No cycle

DFS-Visit(u):
1. color[u] = GRAY
2. For each neighbor v of u:
   If color[v] = GRAY:
      Return True  // Back edge = cycle!
   If color[v] = WHITE:
      If DFS-Visit(v) returns True:
         Return True
3. color[u] = BLACK
4. Return False

Complexity: O(V + E) = O(n + edges) where edges ≤ n² for n transactions

Method 2: Topological Sort Attempt

Trying to compute a topological sort also detects cycles:

Algorithm: TopologicalSort(G)

Input: Directed graph G = (V, E)
Output: Topological ordering if acyclic, CYCLE if cyclic

1. Compute in-degree for each vertex
2. Queue = all vertices with in-degree 0
3. result = empty list
4. While Queue is not empty:
   a. u = dequeue
   b. Append u to result
   c. For each edge (u, v):
      - Decrement in-degree[v]
      - If in-degree[v] = 0:
        Enqueue v
5. If |result| = |V|:
   Return result  // Valid topological order
   Else:
   Return CYCLE  // Some vertices unreachable = cycle exists

Complexity: O(V + E)

Method 3: Quick Check for 2-Cycles

For small precedence graphs, check for bidirectional edges:

For each pair (Tᵢ, Tⱼ):
   If edge Tᵢ → Tⱼ exists AND edge Tⱼ → Tᵢ exists:
      Return CYCLE

This catches the most common case: two transactions with conflicts in both directions.

When the precedence graph is acyclic, we can find an equivalent serial schedule using topological sort.

Understanding Topological Sort

A topological sort of a directed acyclic graph (DAG) is a linear ordering of vertices such that for every edge (u, v), u appears before v in the ordering.

Key Insight: For an acyclic precedence graph, any topological sort gives a valid equivalent serial schedule.

Multiple Valid Orders

If the graph has multiple valid topological sorts, all of them are equivalent serial schedules!

Graph: T₁ → T₃, T₂ → T₃

Valid topological sorts:
- T₁, T₂, T₃ ✓
- T₂, T₁, T₃ ✓

Both are valid serial schedules equivalent to the original.

Let's work through several complete examples to solidify your understanding.

Example 1: Three-Transaction Serializable Schedule

Example 2: Non-Serializable Schedule

Example 3: Complex Four-Transaction Schedule

Experienced analysts recognize patterns that immediately indicate serializability or non-serializability.

Quick Non-Serializability Indicators

Pattern 1: The Read-Write Swap

... rᵢ(X) ... wⱼ(X) ... rⱼ(Y) ... wᵢ(Y) ...

Creates: Tᵢ → Tⱼ (from X) and Tⱼ → Tᵢ (from Y)
2-cycle guaranteed!

Pattern 2: The Write-Write Swap

... wᵢ(X) ... wⱼ(X) ... wⱼ(Y) ... wᵢ(Y) ...

Creates: Tᵢ → Tⱼ (from X) and Tⱼ → Tᵢ (from Y)
2-cycle guaranteed!

Pattern 3: Bidirectional Access

Tᵢ reads X before Tⱼ writes X
Tⱼ reads Y before Tᵢ writes Y

Almost always creates a cycle. Check carefully!

Quick Serializability Indicators

Pattern 1: Monotonic Access

If all conflicts for all data items favor the same direction:

All edges: T₁ → T₂, T₁ → T₃, T₂ → T₃ (all point 'forward')
No back edges → acyclic → serializable

Pattern 2: Serial-Like Structure

If the schedule looks like T₁ operations, then T₂ operations, etc. (with minor interleaving of non-conflicting operations), likely serializable.

Pattern 3: Disjoint Access

Transactions accessing completely different data create no conflicts and add no edges:

T₁: operates on A, B
T₂: operates on C, D
No shared data → no edges → any serial order works