Introduction

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.

Build a Schedule

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">Two transactions read/write accounts <b>A</b> and <b>B</b>. Click an
operation to append it to the schedule. Conflicting operations on the same account
(read-write, write-read, write-write) add an arrow to the conflict graph. The
schedule is <b>serializable iff the graph has no cycle</b>.</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">Schedule</div>
  <div id="sched" class="sched"></div>
</div>
<div class="graph">
  <div class="node n1">T1</div>
  <div id="arrows" class="arrows">no conflicts yet</div>
  <div class="node n2">T2</div>
</div>
<div class="status" id="status">Add operations to build a schedule.</div>
<div class="btns">
  <button id="lost" type="button">Lost-update interleave</button>
  <button id="serial" type="button">Serial T1 then T2</button>
  <button id="reset" type="button" class="ghost">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; }

// Conflict-serializability test. A schedule is a list of operations, each
    // {tx, op:'R'|'W', acc:'A'|'B'}. Two operations CONFLICT when they belong to
    // different transactions, touch the same account, and at least one is a write.
    // For each conflicting pair we add a directed edge earlier.tx -> later.tx in the
    // conflict (precedence) graph. The schedule is conflict-serializable IFF this
    // graph is ACYCLIC. With two transactions, a cycle = both edges 1->2 and 2->1.
const schedule = [];

function conflict(a, b){
  return a.tx !== b.tx && a.acc === b.acc && (a.op === 'W' || b.op === 'W');
}
// Returns {edges:Set('1->2'...), cycle:bool}
function analyze(sched){
  const edges = new Set();
  for (let i = 0; i < sched.length; i++)
    for (let j = i + 1; j < sched.length; j++)
      if (conflict(sched[i], sched[j])) edges.add(sched[i].tx + '->' + sched[j].tx);
  // Generic cycle detection (DFS) over txs present.
  const adj = {};
  edges.forEach(e => { const [u, v] = e.split('->'); (adj[u] = adj[u] || []).push(v); });
  const WHITE = 0, GRAY = 1, BLACK = 2, color = {};
  Object.keys(adj).forEach(n => color[n] = WHITE);
  (sched.length ? [...new Set(sched.map(s => '' + s.tx))] : []).forEach(n => { if (!(n in color)) color[n] = WHITE; });
  let cyc = false;
  function dfs(u){
    color[u] = GRAY;
    (adj[u] || []).forEach(v => {
      if (color[v] === GRAY) cyc = true;
      else if (color[v] === WHITE) dfs(v);
    });
    color[u] = BLACK;
  }
  Object.keys(color).forEach(n => { if (color[n] === WHITE) dfs(n); });
  return { edges, cycle: cyc };
}

function add(tx, op, acc){ schedule.push({ tx, op, acc }); render(); }

function render(){
  const s = document.getElementById('sched'); s.innerHTML = '';
  schedule.forEach(o => {
    const d = document.createElement('span');
    d.className = 'tok tx' + o.tx;
    d.textContent = o.op + o.tx + '(' + o.acc + ')';
    s.appendChild(d);
  });
  const { edges, cycle } = analyze(schedule);
  const a = document.getElementById('arrows');
  a.textContent = edges.size ? [...edges].join('   ') : 'no conflicts yet';
  const st = document.getElementById('status');
  if (!schedule.length){ st.textContent = 'Add operations to build a schedule.'; st.className = 'status'; }
  else if (cycle){ st.textContent = '✗ Cycle in conflict graph — NOT serializable.'; st.className = 'status bad'; }
  else { st.textContent = '✓ Acyclic conflict graph — serializable.'; st.className = 'status ok'; }
}

document.querySelectorAll('.ops button').forEach(b =>
  b.addEventListener('click', () => add(+b.dataset.tx, b.dataset.op, b.dataset.acc)));

document.getElementById('lost').addEventListener('click', () => {
  schedule.length = 0;
  // Classic lost update: R1(A) R2(A) W1(A) W2(A) -> edges 1->2 and 2->1 => cycle.
  [['R',1,'A'],['R',2,'A'],['W',1,'A'],['W',2,'A']].forEach(([op,tx,acc]) => schedule.push({tx,op,acc}));
  render(); console.log('lost-update edges:', [...analyze(schedule).edges]);
});
document.getElementById('serial').addEventListener('click', () => {
  schedule.length = 0;
  // T1 fully, then T2 fully: only 1->2 edges, no cycle.
  [['R',1,'A'],['W',1,'A'],['R',1,'B'],['W',1,'B'],['R',2,'A'],['W',2,'A']].forEach(([op,tx,acc]) => schedule.push({tx,op,acc}));
  render();
});
document.getElementById('reset').addEventListener('click', () => { schedule.length = 0; render(); });
render();
Result
Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/serializability/Content licensed under CC BY-NC 4.0.