Conflict Serializability

Two operations from different transactions conflict if they access the same data item and at least one of them is a write. Formally, for operations $O_i$ (from $T_i$) and $O_j$ (from $T_j$, $i \neq j$) on the same item $Q$: read/read never conflicts, read/write and write/read conflict, and write/write conflicts. Read-read pairs are the only non-conflicting case because swapping two reads never changes what either transaction observes. Conflicting operations are the ones whose relative order matters. If two operations do not conflict, swapping their order in a schedule cannot change the final database state or what any transaction reads, because either they touch disjoint data or they are both reads of the same data. This gives a notion of equivalence: two schedules $S$ and $S'$ over the same set of transactions are conflict equivalent if $S$ can be transformed into $S'$ by a sequence of swaps of consecutive, non-conflicting operations belonging to different transactions. Conflict equivalence is coarser than requiring identical operation order — it says the schedules agree on the order of every conflicting pair. A schedule is conflict serializable if it is conflict equivalent to some serial schedule (one in which transactions run entirely one after another, with no interleaving). This is a precise, checkable strengthening of general serializability (which only requires equivalence in final effect, allowing view equivalence and phenomena like blind writes). Every conflict serializable schedule is (view) serializable, but the converse can fail — there exist view serializable schedules containing blind writes that are not conflict serializable. In practice, conflict serializability is the workhorse notion because, unlike general serializability, it is checkable in polynomial time and it is exactly the guarantee that mainstream concurrency-control protocols provide.

The mechanical test for conflict serializability builds a precedence graph (also called a serialization graph) $G = (V, E)$:

• $V$ contains one node per transaction in the schedule.
• For every pair of conflicting operations $O_i \in T_i$ and $O_j \in T_j$ where $O_i$ appears before $O_j$ in the schedule, add a directed edge $T_i \to T_j$.

Multiple conflicts between the same pair of transactions collapse to a single edge (we only care about existence of at least one precedence, and — critically — the direction must be consistent; if $T_i$'s operations always precede $T_j$'s conflicting operations, or vice versa, in a serializable schedule the direction between any given ordered pair is fixed by the earliest conflict, but it is worth checking that all conflicts between the same pair agree in direction, since a schedule with conflicting operations pointing both ways between the same two transactions is trivially non-serializable — that shows up as a 2-cycle, which the general cycle test already catches). Once the graph is built, the test is: the schedule is conflict serializable if and only if the precedence graph is acyclic. If acyclic, any topological sort of the graph gives a serial schedule that is conflict equivalent to the original — this is not just a heuristic, it is the constructive half of the proof below. ``` ALGORITHM BuildPrecedenceGraph(schedule S, transactions T_1..T_n) // S is a list of operations: each op has (transaction_id, type in {R,W}, data_item) create graph G with nodes T_1 .. T_n, no edges for each unordered pair (T_i, T_j), i != j: conflict_found_direction = NONE // tracks first-seen direction, for sanity check for position p = 1 .. length(S): O_p = S[p] if O_p.transaction == T_i: for position q = p+1 .. length(S): O_q = S[q] if O_q.transaction == T_j and O_q.item == O_p.item and (O_p.type == W or O_q.type == W): add edge T_i -> T_j to G // T_i's op precedes T_j's conflicting op // (symmetric scan also covers T_j before T_i, yielding T_j -> T_i if it occurs) return G ALGORITHM IsConflictSerializable(G): return NOT HasCycle(G) ALGORITHM HasCycle(G): // standard DFS-based cycle detection mark all nodes WHITE // unvisited for each node v in G: if color[v] == WHITE: if DFS_Visit(v) == CYCLE_FOUND: return true return false ALGORITHM DFS_Visit(u): color[u] = GRAY // on current recursion stack for each edge (u -> v) in G: if color[v] == GRAY: return CYCLE_FOUND // back edge -> cycle if color[v] == WHITE: if DFS_Visit(v) == CYCLE_FOUND: return CYCLE_FOUND color[u] = BLACK // fully explored, safe return NO_CYCLE ALGORITHM SerialOrderFromGraph(G): // constructive: acyclic => produces a valid serial order return TopologicalSort(G) // Kahn's algorithm or DFS-finish-order reversal ``` A practical implementation builds the graph in a single left-to-right scan of the schedule, maintaining for each data item the set of transactions that have touched it so far and whether the touch was a read or write, adding an edge each time a new operation conflicts with a previously recorded one. That single-pass construction is what makes real systems (and dependency-graph-based scheduler audits) run this in linear time rather than the naive quadratic pairwise scan shown above for clarity.

Building the graph. With $n$ transactions and a schedule of $m$ operations, the naive pairwise scan shown for clarity is $O(m^2)$ in the worst case (comparing every operation against every later operation). The single-pass streaming version — for each data item, remember the last reader(s) and last writer, and emit an edge on every new access that conflicts with a remembered one — processes each operation in $O(1)$ amortized work against a hash map keyed by data item, giving $O(m)$ time and $O(m + n)$ space overall (the graph has at most $O(n^2)$ edges, but redundant edges between the same ordered pair are typically collapsed, capping the graph itself at $O(n^2)$ edges and $O(n)$ nodes).

Testing acyclicity. Standard DFS-based cycle detection visits every node and edge once: $O(V + E) = O(n + n^2) = O(n^2)$ in the worst case, but in practice with sparse conflict structure this is close to $O(n)$. This is exponentially cheaper than the alternative of enumerating all $n!$ possible serial orders and checking each for equivalence.

Correctness — the theorem and why it holds. > Theorem. A schedule $S$ is conflict serializable if and only if its precedence graph $G(S)$ is acyclic. ($\Leftarrow$) Acyclic implies conflict serializable — constructive direction. If $G(S)$ has no cycle, it admits at least one topological order $T_{\pi(1)}, T_{\pi(2)}, \dots, T_{\pi(n)}$. Claim: the serial schedule $S'$ that runs transactions in exactly this order is conflict equivalent to $S$. Every edge $T_i \to T_j$ in $G(S)$ means some operation of $T_i$ conflicts with, and precedes, some operation of $T_j$ in $S$; because the order is topological, $T_i$ comes before $T_j$ in $S'$ too, so every conflicting pair keeps the same relative order in both schedules. Two schedules over the same operations that agree on the order of every conflicting pair are, by definition, conflict equivalent (one can be reached from the other by swapping only non-conflicting adjacent pairs, since disagreement about order only ever arises from conflicting pairs by definition of the graph). Hence $S$ is conflict equivalent to a serial schedule, i.e., conflict serializable. ($\Rightarrow$) Conflict serializable implies acyclic — contrapositive argument. Suppose $G(S)$ has a cycle $T_1 \to T_2 \to \cdots \to T_k \to T_1$. Each edge $T_i \to T_{i+1}$ certifies a conflicting operation pair ordered with $T_i$ first. If $S$ were conflict equivalent to some serial schedule $S'$, then $S'$ must place transactions in an order consistent with every edge, since conflict-equivalent schedules preserve the relative order of every conflicting pair. But the cycle demands $T_1$ before $T_2$ before … before $T_k$ before $T_1$ again — a strict total order cannot satisfy a cyclic set of precedence constraints. Contradiction; so no such serial $S'$ exists, and $S$ is not conflict serializable. $\blacksquare$

Honesty about scope and tradeoffs. Conflict serializability is a sufficient condition for the isolation guarantee databases actually want (equivalence to some serial execution), and it is strictly stronger than necessary: there exist correct, view-serializable schedules (typically ones with "blind writes" — a write with no matching read in between two other writes to the same item) that are not conflict serializable, yet still produce a state indistinguishable from a serial execution. Conflict serializability trades a small amount of completeness for a test that is efficiently checkable and, more importantly, efficiently enforceable on the fly: locking protocols and timestamp protocols can guarantee acyclicity of the precedence graph as they go, without ever materializing or inspecting the graph after the fact. That is the real payoff — the theorem is the justification for why those protocols are correct, not a runtime check bolted onto production schedulers.

Consider three transactions accessing accounts $A$ and $B$:

Scanning left to right and recording, per data item, the transactions that have accessed it so far:

Item A — accesses in order: T1(R), T2(R), T1(W), T3(R).

• T1(R) vs T2(R): both reads, no conflict.
• T1(W) [step 3] vs earlier T2(R) [step 2]: conflict (write follows read on same item) — since T2's read precedes T1's write, this records $T2 \to T1$.
• T1(W) [step 3] vs T3(R) [step 6]: T1's write precedes T3's read — conflict, edge $T1 \to T3$.

Item B — accesses in order: T2(R) [step 4], T3(W) [step 5], T1(W) [step 7].

• T2(R) before T3(W): conflict, edge $T2 \to T3$.
• T2(R) before T1(W) [step 7 is later]: conflict, edge $T2 \to T1$ (already have this edge from item A, no new edge needed).
• T3(W) before T1(W): conflict, edge $T3 \to T1$.

Collected edges: $T2 \to T1$, $T1 \to T3$, $T2 \to T3$, $T3 \to T1$. Run `HasCycle`: start DFS at $T2$ (color GRAY). Follow $T2 \to T1$: $T1$ GRAY. Follow $T1 \to T3$: $T3$ GRAY. Follow $T3 \to T1$: $T1$ is GRAY (on the current stack) — back edge found, cycle detected: $T1 \to T3 \to T1$.

Verdict: not conflict serializable. Indeed, the cycle says $T1$'s write to $A$ must precede $T3$'s read of $A$ (so $T1$ before $T3$), but $T3$'s write to $B$ must precede $T1$'s write to $B$ (so $T3$ before $T1$) — no serial order can satisfy both simultaneously, exactly matching the proof's contrapositive argument. Now modify step 7 to `R(B)` by T1 instead of `W(B)`, removing the write/write conflict on $B$ between T3 and T1. Recomputing: the edge $T3 \to T1$ disappears (read/write with T3's write first and T1's read after is still a conflict — read after write on the same item still conflicts! — so actually this edge would remain). To genuinely break the cycle, suppose instead T1 never touches $B$ at all. Then the edges are just $T2 \to T1$, $T1 \to T3$, $T2 \to T3$ — a DAG. Topological order: $T2, T1, T3$. The equivalent serial schedule runs all of $T2$'s operations, then all of $T1$'s, then all of $T3$'s, and this serial execution is guaranteed to produce results consistent with the original interleaved schedule on every conflicting access.

Every mainstream relational database — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server — implements a concurrency-control subsystem whose correctness proof rests on conflict serializability. Lock managers enforcing Two-Phase Locking are designed, and proven correct, by showing that the locking discipline can never produce a cycle in the precedence graph: once a transaction releases a lock, it acquires no new ones, which structurally forecloses the possibility of a cyclic wait-and-conflict pattern. Systems using the Timestamp-Ordering Protocol instead assign transactions a total order up front and abort any operation that would violate it, which is equivalent to guaranteeing the precedence graph's edges always point in the timestamp order — an acyclic graph by construction. Beyond textbook engines, distributed databases and NewSQL systems (Spanner, CockroachDB, YugabyteDB) still reason about conflict graphs when justifying their serializable isolation levels, even though they layer in techniques like multi-version concurrency control (MVCC) and global timestamp oracles. Query optimizers and replication systems that reorder operations for performance must respect conflict relationships to avoid silently breaking application correctness. Database testing tools (Jepsen-style linearizability/serializability checkers) construct precedence-like graphs from observed traces to certify or falsify that a production system actually delivered the isolation level it advertised.

Ask the tutor: Can you show why a schedule with a blind write can be view serializable but fail the conflict-serializability cycle test?