The Story That Explains Serializability
So they interleave: T1 uses the oven while T2 chops vegetables. Most interleavings are fine. Trouble starts only when they touch the same ingredient and at least one of them changes it — say T2 adds salt to a stock pot that T1 has already tasted and adjusted. Now the result depends on who touched it when.
Serializability asks one question: can this interleaved schedule produce the same result as some serial one? If yes, the schedule is safe — we get concurrency and correctness.
A schedule is a chronological order of operations from multiple transactions executing together. A schedule is serializable if its effect on the database is equivalent to that of some serial schedule of the same transactions. The most widely used and easily testable form is conflict serializability.
Academic view: serializability is the formal correctness criterion for concurrent execution — the gold standard against which isolation is defined. Industry view: it is what your database's SERIALIZABLE isolation level promises, and what lock managers and MVCC engines work hard to approximate without killing throughput.
Schedules — Serial, Non-Serial, and the Trade-off
Every serial schedule is serializable. Every conflict-serializable schedule is serializable. But not every serializable schedule is conflict-serializable (that wider class is view serializability — correct but NP-hard to test, which is why real systems and exams focus on the conflict form).
Conflicting Operations — The Heart of It All
Two operations conflict if and only if all three conditions hold at once:
| Pair (same item X, different txns) | Conflict? | Name | Why |
|---|---|---|---|
| Read(X) … Read(X) | NO | — | Order of two reads never changes any result. |
| Read(X) … Write(X) | YES | RW conflict | Swap them and the read sees a different value. |
| Write(X) … Read(X) | YES | WR conflict | The read depends on whether the write came first. |
| Write(X) … Write(X) | YES | WW conflict | The final value depends on which write is last. |
Operations on different data items never conflict, and two operations of the same transaction never conflict (their order is fixed by the program anyway). Read–Read on the same item is the only same-item, different-transaction pair that is safe.
Conflict Equivalence & Conflict Serializability
Two schedules are conflict equivalent if one can be transformed into the other by swapping only adjacent non-conflicting operations. A schedule is conflict serializable if it is conflict equivalent to some serial schedule.
Mini Numerical — Proving Equivalence by Swapping
Schedule S over items X and Y (subscripts show the transaction):
Swapping works for proofs, but it is slow for big schedules. The standard fast test is the precedence graph.
The Precedence Graph (Serialization Graph) Test
Numerical 1 — A Serializable Schedule (Full Working)
Test schedule S1 for conflict serializability:
A single edge T1 → T2 — no cycle possible with only one arrow.
The graph is acyclic, so S1 is conflict serializable. Topological order: T1 → T2. The interleaved schedule behaves exactly like running T1 completely, then T2 completely.
Numerical 2 — A Non-Serializable Schedule (The Cycle)
Now test schedule S2:
This is exactly the lost update pattern from your transactions tutorial — both transactions read X, then both write it. Let's prove formally why it is unsafe.
Two opposing arrows on the same pair of nodes — T1 → T2 and T2 → T1 — form a cycle. Instant rejection.
The cycle T1 → T2 → T1 means T1 must come both before and after T2 in any equivalent serial order — impossible. No serial schedule matches S2, so a DBMS enforcing serializability must block or abort one of these transactions (this is precisely when you see deadlock victims or serialization-failure errors in practice).
Numerical 3 — Three Transactions (Exam Level)
Test schedule S3 over three transactions and two items:
Red arrows highlight two cycles: T1 ↔ T2 (top) and T2 ↔ T3 (right side). Either alone is enough to reject.
The two-node cycle T1 → T2 → T1 already settles it (the larger cycle T2 → T3 → T2 exists too). One cycle is enough — you can stop searching the moment you find the first one.
Go item by item, list that item's operations in time order, and draw edges only between pairs where at least one is a Write. This is faster and far less error-prone than scanning the whole schedule left to right.
Solved Examples — Schedule Tables & Precedence Graph Diagrams
In exams and textbooks, schedules are usually presented as a table (one column per transaction, time flowing downward) and the answer is justified with a drawn precedence graph. Here are three fully solved examples in exactly that format.
Example 1 — Three Transactions, Three Items (Serializable)
Problem: Check whether the given schedule S is conflict serializable or not.
| Time | Transaction 1 | Transaction 2 | Transaction 3 |
|---|---|---|---|
| t1 | R(x) | ||
| t2 | R(y) | ||
| t3 | R(x) | ||
| t4 | R(y) | ||
| t5 | R(z) | ||
| t6 | W(y) | ||
| t7 | W(z) | ||
| t8 | R(z) | ||
| t9 | W(x) | ||
| t10 | W(z) |
Edges: T2 → T1 (item z), T2 → T3 (item y), T3 → T1 (item x). All arrows flow one way — no path returns to its starting node.
There is no cycle in the precedence graph, so S is conflict serializable. T2 has no incoming edges, then T3, then T1 — equivalent serial schedule: T2 → T3 → T1.
Example 2 — The Cycle Trap (NOT Serializable)
Problem: Check whether schedule S is conflict serializable:
| Time | Transaction 1 | Transaction 2 | Transaction 3 |
|---|---|---|---|
| t1 | R(x) | ||
| t2 | R(y) | ||
| t3 | W(x) | ||
| t4 | W(y) | ||
| t5 | R(z) | ||
| t6 | W(z) |
T3 only touches item z, so it has no edges — but an isolated node cannot save the schedule. One cycle anywhere is enough to reject.
The cycle T1 → T2 → T1 means T1 must come both before and after T2 in any serial order — impossible. No equivalent serial schedule exists. Note that T3 being conflict-free is irrelevant: the verdict is decided the moment a cycle appears.
Example 3 — Two Valid Serial Orders (Serializable)
Problem: Check whether schedule S is conflict serializable, and give all equivalent serial schedules:
| Time | Transaction 1 | Transaction 2 | Transaction 3 |
|---|---|---|---|
| t1 | R(a) | ||
| t2 | R(b) | ||
| t3 | W(a) | ||
| t4 | R(a) | ||
| t5 | R(b) | ||
| t6 | W(b) |
Both edges point INTO T1, and T2/T3 are unconnected to each other — so T1 must come last, but T2 and T3 can come in either order.
The graph is acyclic, so S is conflict serializable. Because T2 and T3 have no edge between them, the topological sort gives two equally correct serial schedules: T2 → T3 → T1 and T3 → T2 → T1. In an exam, naming either one (or both) earns full marks.
Example 1: a one-way triangle → exactly one serial order. Example 2: any two-way pair of arrows → instant rejection, regardless of other nodes. Example 3: unconnected nodes → multiple valid serial orders. Most exam questions are a variation of one of these three graph shapes.
Counting Schedules — A Classic Numerical
Question: Transactions T1 and T2 have m = 3 and n = 2 operations respectively. How many total schedules are possible, and how many are serial?
Academic View vs Industry View
| Concern | Treatment |
|---|---|
| Correctness | Formal: equivalence to a serial schedule |
| Test | Precedence graph + cycle detection |
| Theory classes | Conflict ⊂ View ⊂ Serializable |
| Exam focus | Draw graph, find cycle, topological order |
| Concern | Treatment |
|---|---|
| Throughput | Serializable is safest but slowest level |
| Mechanism | 2PL locking, MVCC / SSI, timestamps |
| Default levels | Often Read Committed / Repeatable Read |
| Failure mode | Retry on serialization-failure errors |
In practice, engines do not test schedules after the fact — they prevent non-serializable interleavings as they happen. Two-Phase Locking (2PL) guarantees conflict-serializable schedules by construction, while modern MVCC engines (e.g. PostgreSQL's Serializable Snapshot Isolation) monitor dangerous read-write dependency patterns and abort one transaction when a potential cycle appears. The application is expected to catch that error and retry the transaction — an industry habit every backend developer needs.
Stricter isolation → fewer anomalies but more blocking/aborts and lower throughput. Weaker isolation → faster, but the burden of reasoning about anomalies shifts to your application code. Serializability is the only level where you never have to reason about interleavings at all.
Rapid-Fire Concept Check
| Question | Answer |
|---|---|
| Two reads on the same item by different transactions — conflict? | No (only pair with no Write) |
| Test used for conflict serializability | Precedence (serialization) graph |
| Graph has a cycle — verdict? | Not conflict serializable |
| Graph is acyclic — how to get the serial order? | Topological sort |
| Edge Ti → Tj means | Ti must precede Tj serially |
| Number of serial schedules for k transactions | k! |
| Equivalence allowing swaps of non-conflicting adjacent ops | Conflict equivalence |
| Broader class, NP-hard to test | View serializability |
| Protocol that guarantees conflict-serializable schedules | Two-Phase Locking (2PL) |
| Every conflict-serializable schedule is also… | View serializable (not vice versa) |