Serializability and Schedules

A transaction is a sequence of read and write operations on data items, bracketed by begin and commit/abort, as established when studying Transaction States and Atomic Execution. When multiple transactions run concurrently, the database system interleaves their operations to improve throughput and resource utilization. The resulting interleaved sequence of operations — reads, writes, commits, and aborts from all participating transactions, in the order the system actually executes them — is called a schedule. Formally, a schedule $S$ over a set of transactions $T_1, T_2, \dots, T_n$ is a sequence of operations that 1. contains all operations of every $T_i$, in the same relative order that $T_i$ itself specifies, and 2. interleaves operations from different transactions in some order chosen by the scheduler (the concurrency control component). A schedule is serial if the operations of each transaction occur consecutively, with no interleaving from other transactions — that is, the schedule is equivalent to running $T_1$ completely, then $T_2$ completely, and so on. A serial schedule is automatically correct in the sense that matters to a database: since transactions are assumed individually correct (each one, run alone starting from a consistent state, leaves the database in a consistent state — the "C" of ACID), running them one at a time preserves consistency by simple induction. The catch is that serial execution forfeits all benefits of concurrency.

Serializability is the criterion that reconciles these two goals: a schedule is serializable if it is equivalent to some serial schedule over the same set of transactions. "Equivalent" needs a precise meaning, and the field distinguishes two standard notions:

• Conflict equivalence. Two operations from different transactions conflict if they access the same data item and at least one of them is a write. Two schedules are conflict-equivalent if one can be transformed into the other by repeatedly swapping adjacent, non-conflicting operations of different transactions. A schedule is conflict serializable if it is conflict-equivalent to some serial schedule.
• View equivalence. Two schedules are view-equivalent if (a) for every data item, each transaction reads the same value in both schedules (the same "who wrote what I read" relationships hold), and (b) the final writer of each data item is the same transaction in both schedules. A schedule is view serializable if it is view-equivalent to some serial schedule.

Every conflict-serializable schedule is view-serializable, but not vice versa: view serializability is a strictly weaker (more permissive) condition, at the cost of being computationally harder to check (view serializability testing is NP-complete in general, whereas conflict serializability is checkable in polynomial time — details of the exact algorithm belong to Conflict Serializability). Because of this tractability gap, virtually all production concurrency control protocols target conflict serializability, and it is the working definition assumed whenever a system says it "guarantees serializable execution." A separate but equally important axis classifies schedules by recoverability: can the system correctly recover from an abort? A schedule is recoverable if, whenever transaction $T_j$ reads a data item written by $T_i$, $T_i$'s commit occurs before $T_j$'s commit. Non-recoverable schedules can force a "domino effect" of cascading aborts or, worse, make correct recovery impossible after a crash. Recoverability and serializability are independent properties — a schedule can be serializable yet non-recoverable, and real systems must guarantee both.

Reasoning about serializability proceeds in three conceptual steps, each of which becomes an algorithm in practice: (1) represent the schedule, (2) identify conflicts, (3) check for an equivalent serial order.

Step 1 — Represent the schedule. A schedule is written as a sequence of operations tagged by transaction, e.g. $r_1(A)$ means "$T_1$ reads $A$", $w_2(B)$ means "$T_2$ writes $B$", and $c_i$/$a_i$ denote commit/abort of $T_i$.

Step 2 — Identify conflicting pairs. Two operations $op_i(X)$ from $T_i$ and $op_j(X)$ from $T_j$ ($i \ne j$) conflict if they touch the same item $X$ and at least one is a write. There are three conflict types: write-read (WR, a "dirty read" hazard if uncommitted), read-write (RW, an "unrepeatable read" hazard), and write-write (WW, a "lost update" hazard). Order between conflicting operations is fixed by the schedule and cannot be swapped without changing behavior; order between non-conflicting operations can be swapped freely without changing the final database state or what any transaction reads.

Step 3 — Test for serializability. For conflict serializability, the standard mechanism is the precedence graph (also called a serialization graph), built as follows: create one node per transaction, and draw an edge $T_i \to T_j$ whenever some operation of $T_i$ precedes and conflicts with some operation of $T_j$. The fundamental theorem is: > A schedule is conflict serializable if and only if its precedence graph is acyclic. If acyclic, any topological sort of the graph gives an equivalent serial order. This test, and its full justification, is developed in depth under Conflict Serializability; here we give the mechanism because it is the operational meaning of "how do you check whether a schedule works." ```pseudocode // Determine whether schedule S is conflict serializable. // S is given as an ordered list of operations, each tagged with its transaction id. function IS_CONFLICT_SERIALIZABLE(S): transactions := distinct transaction ids appearing in S graph := new DirectedGraph(nodes = transactions) for each pair of operations (op_a, op_b) in S with op_a occurring before op_b: if op_a.transaction != op_b.transaction and op_a.item == op_b.item and (op_a.type == WRITE or op_b.type == WRITE): graph.addEdge(op_a.transaction -> op_b.transaction) // conflict edge if graph.hasCycle(): return (false, null) else: order := graph.topologicalSort() return (true, order) // 'order' is an equivalent serial schedule ``` This runs by scanning all pairs of operations sharing an item; in a real implementation you would group operations by data item first to avoid the naive $O(m^2)$ pair scan (see complexity section). Cycle detection and topological sort on the resulting graph are standard linear-time graph algorithms. A companion, purely conceptual, pseudocode captures what it means for a schedule to be serial in the first place — the anchor definition everything else refers back to: ```pseudocode // A serial schedule for transactions T_1 ... T_n in some order pi is simply // running each one to completion, uninterrupted, before starting the next. function EXECUTE_SERIAL(T_list, order): for i in order: T := T_list[i] for each operation op in T.operations: perform(op) // no other transaction's operation is interleaved commit(T) ``` Serializability theory then says: schedule S is correct if there exists some `order` such that `EXECUTE_SERIAL` on that order produces the same read-values and final database state as S.

Building the precedence graph. With $n$ transactions and $m$ total operations in the schedule, a naive all-pairs conflict scan costs $O(m^2)$. A practical implementation instead groups operations by data item: for each of the $d$ distinct data items, list the operations touching it in schedule order (length $m_x$ for item $x$, with $\sum_x m_x = m$), and scan each such list once to emit conflict edges between adjacent-in-time differing transactions on that item, costing $O(m_x)$ per item and $O(m)$ total. Building the graph is therefore $O(m + n^2)$ in the worst case (the $n^2$ bounds the number of distinct edges between transaction pairs), which in practice is close to linear in the size of the schedule.

Cycle detection and serial order. Once the graph has $n$ nodes and $E \le n^2$ edges, depth-first-search-based cycle detection and topological sorting both run in $O(n + E)$, i.e., $O(n^2)$ worst case but typically far less since conflict graphs are sparse. So the entire serializability test for conflict serializability runs in roughly $O(m + n^2)$ time and $O(m + n^2)$ space (to store the schedule and the graph) — polynomial, hence tractable for real deployment as an offline auditing tool, even though no production system literally builds this graph online for every schedule (protocols instead guarantee acyclicity by construction, e.g., two-phase locking, as covered under Conflict Serializability).

Why acyclicity characterizes conflict serializability (proof sketch). If the precedence graph is acyclic, the schedule is conflict serializable. Take any topological order of the transactions consistent with the graph's edges — one exists because the graph is a DAG. Claim: the schedule can be transformed into the serial schedule following this order purely by swapping adjacent non-conflicting operations, hence it is conflict-equivalent to that serial schedule. Proof by a swapping/exchange argument: consider any operation pair out of topological order, i.e., an operation of a "later" transaction $T_j$ appearing before an operation of an "earlier" transaction $T_i$ (earlier meaning $T_i$ precedes $T_j$ in the topological order). If these two adjacent operations conflicted, they would induce an edge $T_j \to T_i$ in the precedence graph, contradicting that $T_i$ precedes $T_j$ in a topological order of an acyclic graph. So any such adjacent out-of-order pair must be non-conflicting, and can be swapped without changing the schedule's effect. Repeating this bubble-sort-style swapping process — a standard argument bounded by $O(m^2)$ swaps — terminates with the fully serial order, and since every swap preserves conflict-equivalence (by definition), the original schedule is conflict-equivalent to that serial schedule. If the schedule is conflict serializable, its precedence graph is acyclic. Suppose for contradiction the graph has a cycle $T_1 \to T_2 \to \cdots \to T_k \to T_1$. Each edge $T_i \to T_{i+1}$ means some conflicting operation of $T_i$ precedes one of $T_{i+1}$ in $S$. Conflict-equivalence to a serial schedule $S'$ requires that every conflicting pair of operations occurs in the same relative order in $S$ and $S'$ (swapping non-conflicting operations never changes the order of conflicting ones, by definition of the swap). So $S'$ must place $T_1$ before $T_2$ before $\dots$ before $T_k$ before $T_1$ — an impossible cyclic ordering of what is supposed to be a linear (serial) sequence. Contradiction; hence no such $S'$ exists, and $S$ is not conflict serializable. Together these two directions establish the acyclicity theorem exactly, and give an efficient, mechanically checkable characterization of correctness — a rare case in concurrency theory where "correct" reduces cleanly to a textbook graph property.

Honest tradeoffs. Conflict serializability is sufficient but not necessary for "true" correctness in the broader sense of view serializability — some view-serializable schedules (typically ones involving "blind writes," writes not preceded by a read of the same item) are not conflict serializable, yet still produce a valid serial-equivalent outcome. Testing view serializability directly is NP-complete, so systems accept the stricter, cheaper-to-verify conflict serializability as their practical target, sacrificing a small amount of theoretical permissiveness for tractable enforcement. Likewise, no commercial system runs this graph algorithm live per-transaction; instead it is used as an analytical tool to prove that a given concurrency control protocol (locking, timestamps, multiversion) always yields acyclic precedence graphs by construction.

Consider two transactions on a bank database with accounts $A$ and $B$, initially $A = 100$, $B = 50$.

• $T_1$ (transfer 20 from A to B): `read(A); A := A - 20; write(A); read(B); B := B + 20; write(B); commit`
• $T_2$ (audit, sum A + B): `read(A); read(B); commit`

Schedule $S_1$ (serial, $T_1$ then $T_2$):

Serial, trivially correct: audit sees $80 + 70 = 150$, consistent with the pre-transfer total $100+50=150$.

Schedule $S_2$ (interleaved, unsafe):

The audit total is $80 + 50 = 130 \ne 150$: $20$ has "disappeared" mid-transfer from the auditor's point of view. Building the precedence graph for $S_2$: operation $w_1(A)$ (step 2) precedes and conflicts with $r_2(A)$ (step 3) on item A ⇒ edge $T_1 \to T_2$. Operation $r_2(B)$ (step 4) precedes and conflicts with $w_1(B)$ (step 7) on item B ⇒ edge $T_2 \to T_1$. The graph has both $T_1 \to T_2$ and $T_2 \to T_1$: a 2-cycle. By the theorem, $S_2$ is not conflict serializable — and indeed we just exhibited a wrong numeric outcome that matches neither $(T_1, T_2)$ nor $(T_2, T_1)$ order, confirming the theorem's prediction operationally, not just structurally.

Schedule $S_3$ (interleaved, but safe):

Here the only conflict edges run $T_1 \to T_2$ (both $w_1(A)$ before $r_2(A)$ and $w_1(B)$ before $r_2(B)$), no edge the other way, so the graph is acyclic — conflict serializable, equivalent to serial order $T_1, T_2$. The audit correctly reports 150 even though the two transactions' operations were interleaved in real time. This is the whole point: interleaving is fine, as long as it does not create a conflict cycle.

Serializability theory did not emerge from a single breakthrough moment but from the practical crisis of early multi-user database and operating systems in the 1970s, where concurrent access to shared data was causing silent corruption bugs that no one had a rigorous vocabulary to describe or prevent.

Every production relational database — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server, SQLite — implements a concurrency control subsystem whose entire design goal is to guarantee some form of serializability (or an explicitly weaker, documented isolation level) without ever literally computing a precedence graph online. Two-phase locking protocols enforce serializability by construction, guaranteeing acyclic precedence graphs as a side effect of lock ordering rules. Optimistic concurrency control and multiversion concurrency control (MVCC), used in PostgreSQL's snapshot isolation and in systems like Google Spanner and CockroachDB, validate transactions against exactly this kind of conflict analysis at commit time, often using a more refined graph that also tracks read-write anti-dependencies (relevant to detecting so-called write skew anomalies). Distributed databases and cloud transaction services (Spanner, CockroachDB, FoundationDB) advertise "serializable" as their strongest isolation guarantee precisely in the sense defined here, and their published architecture papers explicitly cite precedence-graph-style arguments to justify correctness. Compilers and static analyzers for database application code, and formal verification tools for smart contracts and financial ledgers, use serializability checking as an offline auditing technique — exactly the graph algorithm given above — to certify that a set of observed transaction logs could have arisen from some safe serial order. Understanding schedules and serializability is also the prerequisite for reading and evaluating any concurrency control protocol paper, since every such protocol's correctness proof ultimately reduces to "this protocol never produces a cyclic precedence graph."

Ask the tutor: Can you walk me through why two-phase locking always produces an acyclic precedence graph?