Graphing Database Conflicts: How Precedence Graphs Prove Serializability

In high-throughput relational databases, executing transactions serially (one after another) wastes massive CPU and I/O parallelism. Instead, storage engines execute multiple transactions concurrently with interleaved operations.

However, arbitrary interleaving can trigger lost updates, dirty reads, and inconsistency.

To prove that an interleaved schedule S is mathematically safe, database theory relies on Conflict Serializability.

---

1. What Makes Two Operations Conflict?

Two operations I_i and I_j in a schedule conflict if and only if they satisfy three conditions:

1. They belong to different transactions (T_i ≠ T_j).
2. They access the same data item (Q).
3. At least one of them is a write operation (W(Q)).

The Conflict Matrix:

• Read-Read (R_i(Q), R_j(Q)): No conflict. Order does not alter data.
• Read-Write (R_i(Q), W_j(Q)): Conflict. Swapping changes whether T_i reads the old or new value.
• Write-Read (W_i(Q), R_j(Q)): Conflict. Swapping alters T_j's observation.
• Write-Write (W_i(Q), W_j(Q)): Conflict. Swapping alters the final value surviving in storage.

---

2. Constructing the Precedence Graph

A Precedence Graph (or Serialization Graph) is a directed graph G = (V, E) constructed as follows:

• Vertices (V): Every transaction participating in the schedule.
• Edges (E): A directed edge T_i → T_j is drawn if T_i executes a conflicting operation before T_j.

---

3. The Serializability Theorem

A concurrent schedule S is conflict serializable if and only if its precedence graph contains no directed cycles.

• If Acyclic: The schedule can be serialized. The equivalent serial execution order is obtained via Topological Sorting of the DAG.
• If a Cycle Exists: (e.g., T₁ → T₂ → T₁), it implies T₁ must precede T₂, but T₂ must also precede T₁—a physical impossibility. The schedule is rejected or aborted.

Explore interactive conflict precedence graph analyzers at Binary Dose.