Correctness: Ensuring Safe Concurrent Execution

Concept. A correct concurrent schedule produces the result of a valid serial order. That property is conflict-serializability, and the test for it is a conflict graph with no cycle.

Intuition. When Mickey's and Minnie's playlist updates interleave at the action level, the schedule is correct as long as the resulting Listens table looks identical to "all of Mickey, then all of Minnie" or the reverse. The per-step order can change; the end state must match some serial run. This page goes from "the database reorders for speed" to the exact test for when that reordering is safe.

The naive ways both failed: serial is too slow, free-for-all corrupts. The fix interleaves for speed while keeping the result correct, which demands a precise test for when an interleaving is safe. The rest of this page makes it mechanical: name the schedule types, define what a conflict is, and turn any schedule into a graph whose cycles flag the unsafe ones.

Key Definitions

An action is a single read or write of one row. A transaction is a sequence of them:

A transaction T1 as a sequence of action boxes T1.R(A), T1.W(A), T1.R(B); blue labels are reads, orange labels are writes.

Figure 1. A transaction is a sequence of actions, each one a read or write of a single row, written T1.R(A) for transaction T1 reading row A. Blue labels are reads, orange labels are writes. Correctness tracks only their order, not the values they compute.

Three kinds of schedule for two transactions T1 and T2, each box one action like T1.R(A): serial runs T1 fully then T2; interleaved mixes their reads and writes; serializable is an interleaving whose result matches some serial order. Blue labels are reads, orange labels are writes.

Figure 2. Serial runs one transaction's actions to completion, then the next. Interleaved mixes them in time. Serializable is an interleaving whose result matches some serial order. Blue boxes are reads, orange writes; the T1 or T2 prefix names the transaction, and the page tracks only the R/W order, the macro view.

Serializable is not serial. A serial schedule never overlaps; a serializable one interleaves freely, but its result still matches some serial order.

When do actions conflict?

A conflict is two actions on the same row where at least one is a write: their order changes the result, so the database must never swap that pair. Every other pair is free. The three failures from Naive Concurrency were exactly these conflicts, and they come in three kinds, set by which action reads and which writes.

A 2 by 2 matrix comparing one action of transaction T1 against one action of T2, both on the same row: read-read commutes (no conflict); read-write, write-read, and write-write are conflicts. A conflict needs two different transactions on the same row.

Figure 3. A conflict needs two transactions, the same row, and at least one write. Only read-read commutes; the other three each leave an order-dependent result, each a named anomaly: read-write a stale read, write-read a dirty read, write-write a lost update. Every conflict becomes a directed edge in the conflict graph, next.

Only conflicts are pinned; every other pair of actions can move. The next section turns that into a test for a whole schedule, then shows why that freedom is exactly enough.

How to Test for Conflict-Serializability

Build a conflict graph, then check for a cycle

The conflict graph has one node per transaction and a directed edge from Ti to Tj whenever an action of Ti conflicts with and precedes an action of Tj. The schedule is conflict-serializable exactly when that graph is acyclic.

Acyclic: a topological sort gives a serial order that respects every conflict edge, so the schedule is CS.
Cycle: two conflicts demand opposite orders, no serial order satisfies them all, so the schedule is not CS.

The test in three steps: one node per transaction, one directed edge per conflict forming the acyclic chain T3 to T1 to T2, then check for a cycle; a green box says no cycle means conflict-serializable, a red box says a cycle means not.

Figure 4. The whole test in three steps. Build one node per transaction, add a directed edge for every conflict, then look for a cycle. No cycle (green) means a serial order respects every edge, so the schedule is conflict-serializable; a cycle (red) means two edges demand opposite orders, so none does.

Example 1: Concert Ticket Booking

A concrete scenario: 3 transactions and 2 shared variables.

Setup: The Scenario

Scenario

Concert venue with 2 sections. Three customers simultaneously try to book tickets during a high-demand sale.

Shared Variables:
• A: VIP section tickets (initially: 10)
• B: General section tickets (initially: 22)

Transaction Actions

Each customer performs specific booking actions on the shared ticket counters.

T1: R(A), W(A) - books a VIP seat
T2: R(A), R(B), W(B) - checks VIP, then books General
T3: R(B), W(B) - books a General seat

Expected Results

Once all three transactions commit, the counts must land here under any correct schedule.

Final Values:
• A: 9 tickets
• B: 20 tickets

Serial Schedule S1: T1 → T2 → T3

Serial schedule of the concert booking running T1, then T2, then T3 with no overlap: a table of Transaction, Action, Variable, Step, and Value, reads in blue and writes in orange, ending at A=9, B=20.

Figure 5. A serial schedule runs T1, then T2, then T3 with no overlap. The brackets on the left make the shape plain: each transaction's actions form one contiguous block, the visual signature of serial. It ends at A=9, B=20 with ACID intact, but with no parallelism it is the slowest of the three.

Conflict Identification

Conflict analysis of the serial schedule: a Conflicting-Actions table (T1 and T2 conflict on A; T2 and T3 conflict on B), a conflict graph forming the acyclic chain T1 to T2 to T3, and the verdict that it is conflict-serializable with equivalent serial order T1, T2, T3.

Figure 6. Even a serial schedule has conflicts wherever transactions touch a shared variable: a W-R on A (T1 → T2), a W-W on B (T2 → T3), four in all. They chain T1 → T2 → T3, which is exactly the serial order that produced them.

Example 2: Interleaved Schedule Analysis

Now interleave the transactions. Two interleaved schedules below show the difference between conflict-serializable and non-conflict-serializable.

Schedule S1': Our First Interleaved Schedule

This first interleaving mixes the actions but preserves correctness.

Interleaved schedule S1' of T1, T2, T3: a table of Transaction, Action, Variable, Step, and Value in step order, reads in blue and writes in orange, ending at A=9, B=20.

Figure 7. S1' interleaves T1, T2, and T3 instead of running them serially. Whether the interleaving stays correct depends entirely on its conflict graph, built next.

Conflict analysis for interleaved schedule S1': a Conflicting-Actions table, a conflict graph with edges T2 to T1 and T2 to T3 and no cycle, and the verdict that it is conflict-serializable, equivalent to the serial order T2, T1, T3 (with that serial schedule shown).

Figure 8. The conflict graph of S1' has four conflicts and no cycle, so S1' is conflict-serializable: it matches the serial order T2 → T1 → T3 (or T2 → T3 → T1). The faster interleaving is still correct.

Schedule S2': Our Second Interleaved Schedule

This second interleaving creates conflicts that break serializability.

Interleaved schedule S2' of T1, T2, T3 with an extra T2 write on B: a table of Transaction, Action, Variable, Step, and Value in step order, reads in blue and writes in orange.

Figure 9. S2' is a different interleaving of the same three transactions. The extra T2 write on B breaks it; the conflict graph next shows how. Its final values happen to match the serial run, so the totals are not the tell: the cycle is.

Conflict analysis for interleaved schedule S2': a Conflicting-Actions table, a conflict graph with edges T2 to T1, T2 to T3, and T3 to T2 forming a red cycle between T2 and T3, and the verdict that the cycle makes it NOT conflict-serializable.

Figure 10. The conflict graph of S2' contains a cycle, so S2' is not conflict-serializable, and the interleaving is unsafe.

Conflicts Identified

We compute the conflicting actions and the Conflict Graph:

The cycle lives on variable B. T2 writes B at step 5, then T3 reads B at step 6, so T2's value reaches T3 and the order must be T2 before T3 (edge T2 → T3). But T3 writes B at step 7, then T2 writes B again at step 9, overwriting T3, so the order must also be T3 before T2 (edge T3 → T2). Those two B-conflicts point opposite ways, giving the cycle T2 → T3 → T2.

Why the cycle test works

You have now watched the cycle test decide two schedules: S1' was acyclic and safe, S2' held a cycle and was not. But why does an acyclic graph mean safe? Because you can slide the schedule into a serial order. Two actions that do not conflict swap with no effect, so slide the non-conflicting neighbours until each transaction's actions sit together in one block. What is left is a serial schedule. The only adjacencies you cannot slide past are the conflicts, the graph's own edges, and they fix which block comes first. When the edges form a cycle, two of them demand opposite orders, the schedule will not untangle, and no serial order exists, which is exactly what trapped S2'.

An interleaved schedule of four action tiles. T1's two tiles (read A, write B) are highlighted in violet and start apart, with a T2 action between them. Violet swap markers sit on the two non-conflicting neighbour pairs and a red cross on the write-write pair on B. One free swap gathers T1 into a block and T2 into the next, the serial order below.

Figure 11. Can we swap an interleaved schedule into a serial one? The goal is to gather each transaction's actions into one contiguous block. T1's two tiles (violet) start apart, with a T2 action between them. A neighbour pair may swap only when it does not conflict; here the middle pair touches different rows, so one swap drops T1 into a block and T2 into the next, leaving the serial order T1 then T2. The write-write conflict on B (red) is the one pair that cannot move. A schedule untangles like this exactly when its conflict graph is acyclic.

Two things follow, and they are the whole reordering story:

  • Non-conflicting actions reorder freely. That overlap is where the throughput comes from.

  • Whole transactions have no fixed order. The database runs them in any sequence the conflicts allow, and never promises T1 before T2.

Need a guaranteed order? Put both in one transaction, so their actions form a single block nothing can slide into.

The Landscape of Schedule Classes

A schedule is serializable when its result matches some serial run, which is the correctness goal. But serializability is expensive to check directly: proving it means comparing the outcome against every serial order, for every possible data value. Conflict-serializable is the practical stand-in, a stricter class decided by one mechanical test, the acyclic conflict graph. The classes nest.

Nested hierarchy: S2PL inside 2PL inside Conflict-Serializable inside Serializable

Figure 12. Each ring is a set of schedules, strictly contained in the next: every conflict-serializable schedule is serializable, every two-phase-locking (2PL) schedule is conflict-serializable, and Strict-2PL sits inside 2PL. The gap between serializable and CS is a few rare blind-write schedules (a write that never reads its row), serializable yet not CS. The containment is also a difficulty gradient: the outer ring is checkable only by brute force, CS by the mechanical cycle test, and the 2PL rings, which the Two-Phase Locking page builds a few pages on, need no test at all, since the protocol enforces membership.

Because CS is sufficient for serializability and mechanical to check, it is the working standard: when this course says "serializable," it means conflict-serializable. The cycle test tells you whether a finished schedule is safe; it does not produce safe ones. Two-Phase Locking does: it yields only schedules already inside the CS ring, so the database never runs the test at runtime. The rest of this section builds that machinery, starting with the lock itself, top to bottom.