Serializability

A database almost never runs your request alone. At any instant thousands of transactions — transfers, orders, ticket bookings — are reading and writing the same rows. Running them strictly one at a time would be safe but unbearably slow, so the database interleaves them.

The catch: the result must look as if they had run one after another, in some order. That property is called serializability. If a schedule is serializable, every account balance, seat count and inventory total is exactly what a sane sequential run would have produced. If it is not, money appears from nowhere, two people buy the same seat, and the books no longer balance.

So the database faces a question on every commit: this messy interleaving I just allowed — is it equivalent to some clean sequential order, or not? Remarkably, that question has a crisp, fast answer, and it lives in a little graph.

Two transactions, T1 and T2, each read and write the accounts A and B. Press the buttons to interleave their operations into a single schedule. Each time one transaction's read or write conflicts with the other's on the same account (read-write, write-read or write-write), an arrow is added to the conflict graph in the order they happened.

<p class="hint">{{hint}}</p>
<div class="ops">
  <div class="col t1">
    <div class="lbl">T1</div>
    <button data-tx="1" data-op="R" data-acc="A" type="button">R1(A)</button>
    <button data-tx="1" data-op="W" data-acc="A" type="button">W1(A)</button>
    <button data-tx="1" data-op="R" data-acc="B" type="button">R1(B)</button>
    <button data-tx="1" data-op="W" data-acc="B" type="button">W1(B)</button>
  </div>
  <div class="col t2">
    <div class="lbl">T2</div>
    <button data-tx="2" data-op="R" data-acc="A" type="button">R2(A)</button>
    <button data-tx="2" data-op="W" data-acc="A" type="button">W2(A)</button>
    <button data-tx="2" data-op="R" data-acc="B" type="button">R2(B)</button>
    <button data-tx="2" data-op="W" data-acc="B" type="button">W2(B)</button>
  </div>
</div>
<div class="sched-wrap">
  <div class="sched-title">{{sched_title}}</div>
  <div id="sched" class="sched"></div>
</div>
<div class="graph">
  <div class="node n1">T1</div>
  <div id="arrows" class="arrows">{{no_conflicts}}</div>
  <div class="node n2">T2</div>
</div>
<div class="status" id="status">{{add_ops}}</div>
<div class="btns">
  <button id="lost" type="button">{{btn_lost}}</button>
  <button id="serial" type="button">{{btn_serial}}</button>
  <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.ops { display: flex; gap: 1rem; margin: .3rem 0 .6rem; }
.col { display: flex; flex-direction: column; gap: .35rem; flex: 1; }
.lbl { font-weight: 700; font-size: .85rem; color: #1d3557; }
.col.t2 .lbl { color: #b5651d; }
.ops button { font: 600 13px ui-monospace, monospace; padding: .4rem; border-radius: 7px; cursor: pointer; border: 1px solid #1d3557; background: #eef3f8; color: #1d3557; }
.col.t2 button { border-color: #b5651d; background: #fbf2e8; color: #8a4d12; }
.sched-wrap { margin: .3rem 0; }
.sched-title { font-size: .8rem; font-weight: 600; color: #555; margin-bottom: .2rem; }
.sched { display: flex; flex-wrap: wrap; gap: .3rem; min-height: 2rem; padding: .4rem; background: #f4f6f9; border-radius: 8px; }
.tok { font: 700 13px ui-monospace, monospace; padding: .2rem .45rem; border-radius: 6px; }
.tok.tx1 { background: #d7e3f0; color: #1d3557; }
.tok.tx2 { background: #f3e2cf; color: #8a4d12; }
.graph { display: flex; align-items: center; justify-content: center; gap: .8rem; margin: .7rem 0; }
.node { width: 46px; height: 46px; border-radius: 50%; display: flex; align-items: center; justify-content: center; font: 700 15px system-ui; }
.n1 { background: #1d3557; color: #fff; }
.n2 { background: #b5651d; color: #fff; }
.arrows { font: 600 13px ui-monospace, monospace; color: #444; text-align: center; min-width: 120px; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
.btns button { font: 600 14px system-ui; padding: .45rem .9rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
.btns button.ghost { background: #fff; color: #1d3557; }

// Code not found

The whole test is one rule: the schedule is serializable if and only if the conflict graph has no cycle. No cycle means the arrows can be flattened into a single order T1→T2 or T2→T1 — a serial run with the same result. A cycle (T1→T2 and T2→T1) means no such order exists: the schedule is genuinely non-serializable. Try the classic lost-update interleave to make a cycle appear instantly.

How hard is it to know whether a schedule is serializable? It depends on which notion of equivalence you accept.

• Conflict-serializability is easy (in P). Build the conflict graph — one node per transaction, one edge per pair of conflicting operations — then ask: is it acyclic? That is a textbook topological-sort / cycle-detection problem, solvable in time linear in the number of operations. This is what real database schedulers check.
• View-serializability is hard. If you relax equivalence to "every read sees the same value and the final writes match" — ignoring conflicts that don't actually change outcomes — then deciding serializability becomes NP-complete. This was proved by Christos Papadimitriou in 1979. Every conflict-serializable schedule is view-serializable, but not the reverse, and that extra freedom is exactly what makes it intractable.
• So the practical question is solved, fast. Schedulers don't gamble on the NP-complete version; they enforce conflict-serializability (often via two-phase locking), trading a little permissiveness for a guaranteed linear-time check.

That gap is the whole story: the same problem is a quick graph scan or a member of the P vs NP hard class depending on how generous you are about what "the same result" means.

Serializability is the gold-standard isolation level — the "I" in ACID — and the contract that lets you reason about a database as if you were its only user:

• Financial ledgers: transfers, settlements and double-entry bookkeeping rely on the guarantee that no interleaving can invent or lose money.
• Inventory and ticketing: "only one buyer gets the last seat" is exactly a non-serializable interleaving being rejected.
• Concurrency control: two-phase locking, timestamp ordering and serializable snapshot isolation are all machinery for producing only conflict-serializable schedules.
• Distributed databases: spanning the cycle check across machines is far harder, tangling with the CAP theorem and the cost of distributed consensus.

Even query engines feel it: the planner in SQL optimization may reorder work, but only within what serializability allows.

Serializability is a small miracle of computer science: it lets a database be wildly parallel on the inside while presenting a calm, one-thing-at-a-time face to every user. The whole guarantee rests on a single question — does the conflict graph have a cycle? — that a computer answers in the blink of an eye.

Loosen the definition just slightly, to view-serializability, and the same question jumps into the NP-complete world that haunts P vs NP. So the next time a transfer goes through cleanly while a thousand others ran beside it, you can thank a tiny graph with no cycle in it — the reason chaos and order can be, exactly, the same thing.