Core CS · DBMS
Swap two operations, lose twenty-two rupees
Two transactions, eight operations, and one interleaving that is safe sitting next to one that is not. You will build the precedence graph edge by edge and watch a single swapped operation put an arrow in the wrong direction.
Run both schedules, one operation at a time →01 The idea
Serial is correct, and serial is far too slow
A transaction is one unit of work: a group of reads and writes that must all take effect or none of them. A schedule is the order in which the database actually executes the operations of several transactions, with each transaction’s own operations kept in its own order. If the schedule finishes one transaction completely before starting the next, it is a serial schedule, and a serial schedule is correct by definition, because no transaction ever sees another one’s half-finished work.
So why not run everything serially. Because a transaction spends most of its life waiting: for a page to come off disk, for a network round trip, for a lock somebody else is holding. Serial execution leaves the processor idle through every one of those waits, and it makes a one-row balance check queue behind a report that scans a million rows. Interleaving fixes both at once. Throughput goes up because the machine has something to do during the waits, and average response time comes down because a short transaction no longer sits behind a long one.
What interleaving costs you is the guarantee. Once operations from two transactions land between each other, some orders produce a database state that no serial run could have produced. Two transactions of four operations each can be interleaved 8! / (4! × 4!) = 70 ways while keeping each transaction’s own order intact, and exactly two of those seventy are serial. So “just run them serially” is not a usable rule, and “it looked fine afterwards” is not a test. What you need is a procedure that takes any one of the seventy and answers a single question: is its effect the same as some serial order?
02 Worked example
One transfer, one interest run, eight operations
Asha has 100 rupees in her savings row A and 50 in her current row B. Two transactions want both rows tonight. T1 is a transfer: it moves 20 from A to B. T2 is the interest run: it adds ten per cent to A, then ten per cent to B. Each is four operations, a read and a write per row. Here is one interleaving of them, with the value on disk after every single operation.
-- T1 move 20 from A to B r1(A) w1(A) r1(B) w1(B)-- T2 add 10% to A, then to B r2(A) w2(A) r2(B) w2(B) -- schedule S1 A B-- before anything runs 100 50 1 r1(A) T1 reads A = 100 100 50 2 w1(A) T1 writes A = 100 - 20 80 50 3 r2(A) T2 reads A = 80 80 50 4 w2(A) T2 writes A = 80 + 8 88 50 5 r1(B) T1 reads B = 50 88 50 6 w1(B) T1 writes B = 50 + 20 88 70 7 r2(B) T2 reads B = 70 88 70 8 w2(B) T2 writes B = 70 + 7 88 77-- final state 88 77Nothing in those numbers tells you whether the schedule was safe. 88 and 77 look reasonable, and so will the numbers the broken version of this schedule produces in section 04. The test does not look at values at all. It looks only at which pairs of operations were forced into an order, and it runs like this.
Apply that to S1. Row A gives three conflicting pairs: r1(A) with w2(A), w1(A) with r2(A), and w1(A) with w2(A). Row B gives three more of exactly the same shape. In all six of them the T1 operation is the one that came first, so all six arrows read T1 to T2, and six copies of the same arrow are still one edge. The graph is two nodes with a single arrow between them. There is no cycle, so S1 is conflict serialisable, and the only topological order of that graph is T1 then T2.
Check it by hand. Run T1 on its own and A becomes 80 and B becomes 70. Now run T2 on those values: 80 + 8 = 88 and 70 + 7 = 77. The same pair of numbers S1 produced. The graph told you that before you did any arithmetic, and it would still tell you on a schedule of forty operations where doing the arithmetic is not an option.
Now move one operation, and only one. Swap operations 6 and 7, which are w1(B) and r2(B), so that T2 reads B before T1 writes it, and change nothing else. That single adjacent swap turns one of the six pairs around, and with T1 to T2 already on the graph, one arrow pointing the other way closes a cycle. Section 04 runs both schedules a step at a time so you can watch the graph change under the swap.
03 Mechanics
Three ways it goes wrong, and three grades of schedule
The whole test rests on the conflict rule, so start there. Two operations conflict when they are from different transactions, on the same data item, and at least one is a write. Three conditions, all of which have to hold. For one row and two transactions the entire rule fits in four cells.
| T1 on row A, down · T2 on row A, across | T2 reads A | T2 writes A |
|---|---|---|
| T1 reads A | no conflict · swap the two and nothing changes | conflict · whoever went first fixes the direction of the edge |
| T1 writes A | conflict · the reader sees a different value depending on the order | conflict · the write that happens second is the one that survives |
Only read against read is free, and that single exception is what makes read-heavy workloads cheap to run concurrently. Operations on different rows never conflict whatever they are, which is why a schedule spread over ten rows usually draws far fewer edges than it has operations. Now the three failures those edges exist to catch. All three use the same two rows and the same starting values, 100 and 50.
| Problem | The interleaving | What the database is left holding | What the graph says |
|---|---|---|---|
| Lost update | r1(B) r2(B) w1(B) w2(B) |
Both read 50. T1 writes 70. T2 writes 50 + 5 = 55, computed from the value T1 had already replaced. B ends at 55 and the 20 rupees T1 moved are gone. No operation failed and no error was raised. |
r2(B) before w1(B) draws T2 to T1; r1(B) before w2(B) draws T1 to T2. Cycle. Rejected |
| Dirty read (uncommitted dependency) |
r1(A) w1(A) r2(A) abort1 w2(A) |
T1 writes 80, T2 reads that uncommitted 80, T1 aborts and A goes back to 100, then T2 writes 80 + 8 = 88. T1 never happened, so A should read 110. T2 charged interest on a number that was never in any committed state. |
every edge runs T1 to T2. Acyclic. Conflict serialisable, and still wrong |
| Unrepeatable read | r3(B) w2(B) commit2 r3(B) |
T3 is an audit, a third transaction that reads each row twice to check its own total. It reads B = 50, T2 writes 55 and commits, T3 reads B = 55. One transaction, two answers, and neither is wrong at the moment it was taken. | r3(B) before w2(B) draws T3 to T2; w2(B) before the second r3(B) draws T2 to T3. Cycle. Rejected |
The middle row is the one that decides interviews. Its precedence graph is acyclic, so the schedule passes the serialisability test, and it still leaves the database holding interest charged on a value that was rolled back. Serialisability is a statement about the order of reads and writes. It says nothing at all about commits and aborts, and “T2 read something from a transaction that later died” is not a fact any cycle can express. That gap is covered by three separate properties, in increasing strength.
| Grade | The rule | Does the dirty-read schedule pass? | What it buys you |
|---|---|---|---|
| Recoverable | If Tj reads a value Ti wrote, Ti must commit before Tj commits. | no · T1 aborted, so it never commits, and T2 must not be allowed to commit either |
You never have to undo a transaction that already told the user it succeeded. This is the floor. Below it the word “committed” means nothing. |
| Cascadeless (avoids cascading aborts) |
Tj may read a value Ti wrote only after Ti has committed. | no · r2(A) read the 80 that T1 had not committed |
One abort never drags other transactions down with it. Without this, aborting T1 forces T2 to abort, which may force T3, and so on down the chain. |
| Strict | No transaction may read or write an item until the transaction that last wrote it has committed or aborted. | no · the same read at r2(A) |
Undo becomes a plain restore of the before image: put back the value that was there. Nothing else can have overwritten it in the meantime. |
Strict implies cascadeless implies recoverable, and the implication never runs the other way. None of the three implies serialisability, and serialisability implies none of them. The unrepeatable-read schedule r3(B) w2(B) commit2 r3(B) is strict, because nobody read or wrote B while another writer was still open, and its graph still has a cycle. You are being asked two independent questions about every schedule and you need both answers ready.
There is a weaker condition than conflict serialisability, called view serialisability: a schedule is view serialisable if there is some serial schedule in which every read reads from the same write and the final write of each item is the same one. It accepts everything conflict serialisability accepts plus a few extra schedules, and every one of those extras contains a blind write, meaning a transaction writing an item it never read. Nobody tests for it, because deciding view serialisability is NP-complete while the precedence graph is a cycle check on a graph with one node per transaction.
And a running database does neither test, because both of them need the finished schedule and a live system has to decide before each operation runs. What it follows instead is a protocol: two-phase locking. Every transaction takes every lock it will ever need before it releases any of them, so its life splits into a growing phase where it only acquires and a shrinking phase where it only releases. The instant it takes its last lock is called its lock point. Any schedule that a set of two-phase transactions can produce is conflict serialisable, and that is the whole trade: you stop asking whether a schedule was safe and follow a rule that cannot draw a cycle. Strict two-phase locking additionally holds every exclusive lock until commit or abort, which hands you strict schedules on top. What 2PL does not hand you is freedom from deadlock, and that is its price.
05 Cheat sheet
The whole test on one card
Two independent questions get asked about every schedule, in this order: is it serialisable, and what happens if somebody aborts. The first five rows answer the first question, the next three answer the second, and the last row is what a real system does instead of asking either.
| Term | The test | The verdict it gives |
|---|---|---|
| Conflict | different transactions, same item, at least one write | read against read is the only free pair |
| Serial schedule | no interleaving at all | n! of them, every one correct |
| Precedence graph | one node per transaction, one edge per conflicting pair, pointing away from the operation that came first | a cycle means reject, and there is nothing else left to check |
| Conflict serialisable | the precedence graph is acyclic | equivalent serial order = any topological sort of the graph |
| View serialisable | same reads-from pairs and same final write per item as some serial schedule | a strictly larger set, and NP-complete to decide |
| Recoverable | Ti commits before Tj commits, whenever Tj read what Ti wrote | no committed transaction ever has to be undone |
| Cascadeless | Tj reads what Ti wrote only after Ti has committed | no dirty reads, so one abort stays one abort |
| Strict | no read or write of an item until its last writer has committed or aborted | undo is a restore of the before image |
| Two-phase locking | every lock acquired before any lock is released | guarantees conflict serialisability, guarantees nothing about deadlock |
06 Where & why
Which database actually tests this
No mainstream engine builds a precedence graph while you type. Each one picks a protocol that makes cycles impossible, or a cheaper protocol that lets some through and documents which. Knowing which is which is what turns this from a chapter into something you can say about a system you have run. Every engine below that lets two transactions interleave ships with a default level that is not serialisable, and the one that is serialisable by default gets there by refusing to interleave at all.
SERIALIZABLE here is serialisable snapshot isolation. Transactions run against a snapshot and the engine watches for the read-write dependency pattern that every cycle has to contain, then aborts one transaction with a serialization_failure rather than making anybody wait. Readers never block writers, so the cost lands in your retry loop instead of your throughput. The default is READ COMMITTED, which stops dirty reads and nothing else, so the unrepeatable read from section 03 is allowed there by design.
InnoDB takes row locks and holds every exclusive lock until commit or rollback, which is strict 2PL, and is why its rollback is a plain undo. Its default is REPEATABLE READ, where a plain SELECT reads a consistent snapshot, so the unrepeatable read does not happen there but write skew still does. Ask for SERIALIZABLE and InnoDB quietly turns every plain SELECT into a locking read, which is the textbook protocol at textbook cost.
Oracle’s SERIALIZABLE is snapshot isolation: readers are never blocked, a write collision raises ORA-08177, and write skew is permitted, which the standard’s definition does not allow. SQL Server’s SERIALIZABLE takes key-range locks and holds them to the end of the transaction, which is rigorous two-phase locking, while its default READ COMMITTED releases each shared lock as soon as the statement ends. One word, two protocols, and the gap between them is a standard interview question.
In rollback-journal mode SQLite allows one writer and no concurrent reader while that write is in progress, so its schedules are serial and the question never arises. In WAL mode readers run against a snapshot while one writer works, and a second writer gets SQLITE_BUSY instead of an interleaving. It is the honest reminder that the cheapest way to guarantee serialisability is to refuse concurrency, and that refusing concurrency is exactly the throughput you are buying back on a bigger engine.
07 Interview questions
What they actually ask
This topic arrives straight after ACID, and it is usually answered with three memorised nouns and no test at all. Whoever can draw the graph, get the arrows the right way round, and then say what serialisability does not cover is answering a different question from everybody else in the queue.
What is a schedule, and what makes one serial?
If serial execution is correct, why interleave at all?
When exactly do two operations conflict?
What does it mean for a schedule to be conflict serialisable?
How do you test a schedule for conflict serialisability?
Name the three problems concurrency causes.
A schedule with a dirty read in it turns out to have an acyclic precedence graph. Is it safe?
Recoverable, cascadeless, strict. What is the difference?
What is view serialisability, and why does no system use it?
A running database cannot draw a precedence graph. So how does it guarantee serialisability?
What does two-phase locking cost you?
Writing ordinary application code, how much of this do you actually touch?
08 Practice problems
Six schedules to take apart
Work each one on paper with the graph drawn out. The most common mistake by far is drawing an edge from the wrong end of the pair, and it stays invisible until the verdict comes out backwards.