1 What a transaction is & ACID
Imagine you give your friend $10 by taking a $10 note out of your piggy bank and putting it into theirs. There's a scary half-second where the note is in neither bank — it's in your hand. If a magpie swooped down and stole it right then, $10 would just vanish. A transaction is a magic rule that says: either the whole move happens, or none of it does — there is no in-between where the money disappears. The database makes that promise for you.
A transaction is a group of database operations (reads and writes) that the database treats as one single, indivisible unit of work. In SQL you mark its boundaries explicitly:
BEGIN; -- start the transaction UPDATE accounts SET balance = balance - 10 WHERE id = 'alice'; UPDATE accounts SET balance = balance + 10 WHERE id = 'bob'; COMMIT; -- make it permanent (or ROLLBACK to undo everything)
Everything between BEGIN and COMMIT succeeds
together or is thrown away together. To make this precise, databases promise four properties whose
initials spell ACID.
| Letter | Property | Promise in plain English |
|---|---|---|
| A | Atomicity | All-or-nothing. Every statement in the transaction happens, or none does. ("Atom" = indivisible.) |
| C | Consistency | The transaction moves the database from one valid state to another — all rules (constraints, types, foreign keys) still hold afterwards. |
| I | Isolation | Concurrent transactions don't step on each other. Each one behaves as if it ran alone. |
| D | Durability | Once committed, the change survives — even a power cut a millisecond later won't lose it. |
Walking through ACID with the bank transfer
Let's use Alice sending Bob $10 (the two UPDATEs above) to feel each letter:
- Atomicity — if the database crashes after debiting Alice but before crediting Bob, atomicity guarantees the debit is undone on restart. Money never evaporates. The mechanism that allows undo/redo is the write-ahead log (WAL), which we touch on again in the recovery session.
- Consistency — suppose there's a rule "total money in the system never changes." The transfer removes $10 and adds $10, so the total is preserved. If a constraint would be violated (e.g. Alice's balance can't go negative), the transaction is rejected and rolled back.
- Isolation — if Carol is reading the total balances at the same instant, she must not see the moment where $10 has left Alice but not yet reached Bob. To her it should look like the transfer either fully happened or hasn't started.
- Durability — once the bank's app says "Transfer complete," that money has moved for good. Pulling the plug won't bring it back to Alice.
Without atomicity, picture the crash happening between the two UPDATEs:
-- Step 1 runs and is saved: UPDATE accounts SET balance = balance - 10 WHERE id = 'alice'; -- Alice: 100 -> 90 *** POWER FAILURE *** (Bob's credit never runs) -- Bob still has his old balance: Bob: 50 (unchanged)
Now $10 has simply disappeared from the system. Total money dropped from 150 to 140. A transaction prevents exactly this: on restart the database reads its log, sees the transfer never committed, and rolls back Alice's debit so she's back to 100. All-or-nothing saves the day.
A transaction bundles several operations into one unit so that partially-completed work can never be observed or left behind. ACID is the four-part contract the database signs: Atomic (all-or-nothing), Consistent (rules always hold), Isolated (as if alone), Durable (survives crashes).
BEGIN …
COMMIT/ROLLBACK. ACID = Atomicity, Consistency,
Isolation, Durability. Atomicity is what stops the bank transfer from "losing" money when a crash
happens mid-way — the danger of partial execution.
2 Concurrency anomalies
Two kids share one colouring book. If they both colour the same page at the same time without taking turns, you get a mess: one paints over the other, or someone copies a half-finished drawing and gets confused. Concurrency anomalies are exactly these "we didn't take turns properly" messes — but in a database, where two users touch the same data at the same moment.
The I in ACID (isolation) is the hard one. When many transactions run at once, the database interleaves their reads and writes to stay fast. A particular interleaving is called a schedule. Some schedules produce wrong results that could never happen if the transactions ran one-at-a-time. Those wrong results are anomalies. Below, T1 and T2 are two transactions and time runs downward.
Anomaly 1 — Dirty read
A dirty read happens when T2 reads a value that T1 wrote but has not committed yet — and T1 later rolls back. T2 acted on data that never officially existed.
| Time | T1 | T2 |
|---|---|---|
| 1 | UPDATE balance = 200 (was 100) | |
| 2 | READ balance → sees 200 (uncommitted!) | |
| 3 | ROLLBACK (balance back to 100) | |
| 4 | Acts on the bogus 200 — wrong! |
Anomaly 2 — Non-repeatable read
A non-repeatable read happens when T1 reads the same row twice and gets two different values, because T2 changed and committed it in between. The same query, the same row, two answers within one transaction.
| Time | T1 | T2 |
|---|---|---|
| 1 | READ balance → 100 | |
| 2 | UPDATE balance = 100 → 150; COMMIT | |
| 3 | READ balance → 150 (changed under me!) |
Anomaly 3 — Phantom read
A phantom read is the non-repeatable read's cousin, but for sets of rows. T1 runs a query with a condition (e.g. "all accounts with balance > 100"); T2 inserts a new row matching that condition and commits; T1 re-runs the query and a "phantom" row has appeared that wasn't there before.
| Time | T1 | T2 |
|---|---|---|
| 1 | SELECT COUNT(*) WHERE balance > 100 → 3 | |
| 2 | INSERT account (balance = 500); COMMIT | |
| 3 | SELECT COUNT(*) WHERE balance > 100 → 4 (phantom!) |
A non-repeatable read is about an existing row's value changing (an UPDATE). A phantom is about the set of rows changing — new rows appearing or disappearing (an INSERT/DELETE) for a range query. They're prevented by different mechanisms, which is why the SQL standard lists them separately.
Anomaly 4 — Lost update
A lost update happens when two transactions read the same value, both compute a new value from it, and both write back — so one write silently clobbers the other.
| Time | T1 (add $10) | T2 (add $20) |
|---|---|---|
| 1 | READ balance → 100 | |
| 2 | READ balance → 100 | |
| 3 | WRITE balance = 110; COMMIT | |
| 4 | WRITE balance = 120; COMMIT |
Both deposits should leave 130, but the final balance is 120 — T1's +$10 was lost because T2 overwrote it with a value computed from the stale 100.
Anomaly 5 — Write skew
A write skew is subtler. Two transactions read an overlapping set of data, each checks a rule that's currently satisfied, and each writes to a different row. Individually each looks fine; together they break an invariant that spans both rows.
Rule: at least one doctor must stay on call. Alice and Bob are both on call and both want to go off call. Each transaction checks "is anyone else still on call?" — and at this instant the answer is yes, so each thinks it's safe.
-- Invariant: COUNT(on_call) >= 1 must always hold (currently Alice & Bob both on call) T1 (Alice): SELECT count(*) FROM shifts WHERE on_call = true; -- = 2, ok T2 (Bob): SELECT count(*) FROM shifts WHERE on_call = true; -- = 2, ok T1 (Alice): UPDATE shifts SET on_call = false WHERE who = 'alice'; T2 (Bob): UPDATE shifts SET on_call = false WHERE who = 'bob'; both COMMIT -> now ZERO doctors on call. Invariant broken!
Neither transaction wrote the row the other read, so no single value was overwritten (it's not a lost update). Yet the combined effect violates a rule. Write skew is famous because it sneaks past the popular "Snapshot Isolation" level — only Serializable reliably prevents it.
These anomalies aren't theoretical — they cause real double-spends, overdrafts and broken invariants in production. The whole point of the next topic (isolation levels) is to choose which of these you're willing to risk in exchange for speed.
3 Isolation levels
Imagine a sliding door between two rooms. You can leave it wide open (everyone sees and bumps into everyone — fast but chaotic), slightly ajar, or locked shut (total privacy, but you have to wait your turn — slow but tidy). Isolation levels are exactly these settings: how much one transaction is allowed to notice what others are doing. More privacy = fewer messes, but more waiting.
The SQL standard defines four isolation levels. Each is a deal: a higher level forbids more anomalies but costs more performance (more locking or version-keeping, more waiting, more aborts). You pick the lowest level that's still safe for your task.
-- you set the level per-transaction (PostgreSQL / standard SQL): SET TRANSACTION ISOLATION LEVEL READ COMMITTED; -- or: READ UNCOMMITTED | REPEATABLE READ | SERIALIZABLE
| Level | Idea |
|---|---|
| Read Uncommitted | The loosest. A transaction may read other transactions' uncommitted writes. Almost no protection. |
| Read Committed | You only ever read data that has been committed. The common default (e.g. PostgreSQL, Oracle). |
| Repeatable Read | Once you read a row, re-reading it gives the same value for the whole transaction. |
| Serializable | The strictest. The result is guaranteed identical to some order of running the transactions one at a time. |
The standard "which anomaly does each prevent?" table
This is the table to memorise. "Possible" means the level allows that anomaly; "Prevented" means it forbids it. (Definitions from the ANSI/ISO SQL standard.)
| Isolation level | Dirty read | Non-repeatable read | Phantom read |
|---|---|---|---|
| Read Uncommitted | Possible | Possible | Possible |
| Read Committed | Prevented | Possible | Possible |
| Repeatable Read | Prevented | Prevented | Possible |
| Serializable | Prevented | Prevented | Prevented |
Take the non-repeatable read from Topic 2 (T1 reads 100, T2 commits 150, T1 re-reads):
- Under Read Committed, T1's second read sees the freshly committed 150 → the anomaly still happens (it's "Possible").
- Under Repeatable Read, T1 is pinned to the value it first saw (100) for its whole life → the anomaly is prevented.
So if your report must see a stable snapshot, Read Committed isn't enough — step up to Repeatable Read.
The standard says only what each level must at least forbid; engines may forbid more. For example, PostgreSQL's "Repeatable Read" actually uses Snapshot Isolation and also blocks phantom reads — but, as we saw, snapshot isolation can still allow write skew, which is why a truly Serializable level exists. Also, many engines implement "Read Uncommitted" as just "Read Committed" because their design (MVCC) never exposes uncommitted data anyway.
The performance trade-off
As you climb the levels the database holds locks longer (or tracks more versions and conflicts), so transactions wait on each other more, throughput drops, and at Serializable you may even get transactions aborted with a "serialization failure" that your app must retry. The art is choosing the cheapest level that's still correct for the job.
Going up the ladder — Read Uncommitted → Read Committed → Repeatable Read → Serializable — each step forbids one more class of anomaly (dirty → non-repeatable → phantom) and Serializable forbids them all, including write skew. The cost is reduced concurrency: more waiting and more retries. Pick the lowest level that is still safe for your workload.
4 Serializability & 2PL theory
Two people want to use one bathroom. The obviously safe plan is "take turns" — one fully finishes, then the other goes. That's a serial plan: slow but never a clash. But what if they could each do little bits at the same time and the end result is exactly as if they'd taken turns? That'd be just as safe but faster. Serializability theory is the rulebook for spotting when an interleaved plan is "as good as taking turns," and 2PL is a simple discipline — grab all your keys first, only give them back later — that guarantees it.
Serial vs serializable schedules
Recall a schedule is one specific interleaving of several transactions' operations. Two kinds matter:
- A serial schedule runs transactions one completely after another — T1 finishes, then T2 starts. It's always correct (no interleaving = no anomalies), but it wastes the machine's ability to do work in parallel.
- A serializable schedule is an interleaved schedule whose final result is equivalent to some serial schedule. It may run operations in a mixed-up order, but the outcome is identical to some "take turns" order. This is the gold standard of correctness — it's exactly what the Serializable isolation level promises.
Serializable does not mean the result equals running them in the order they arrived. It means the result matches at least one valid serial order (either "T1 then T2" or "T2 then T1"). The database is free to pick whichever it can achieve — it just has to match one of them.
Conflict serializability — how we check it
Checking "is this equivalent to a serial order?" in general is hard, so we use a practical, slightly stricter test called conflict serializability. Two operations conflict if they are from different transactions, touch the same data item, and at least one is a write. The three conflict types: write-write, write-read, read-write.
A schedule is conflict-serializable if you can reach a serial schedule purely by swapping adjacent non-conflicting operations. The standard tool is the precedence graph (conflict graph):
Here R = read, W = write, A
is a data item. Time runs left to right:
Schedule S: R1(A) W2(A) W1(A) Conflicts on A: R1(A) before W2(A) => edge T1 -> T2 (read-write conflict) W2(A) before W1(A) => edge T2 -> T1 (write-write conflict) Precedence graph: T1 -> T2 and T2 -> T1 => CYCLE A cycle exists => NOT conflict-serializable => this interleaving is unsafe.
Because there's a cycle, no amount of swapping non-conflicting neighbours can untangle S into a serial
order. If instead the graph had been just T1 → T2 with no back-edge, S would be
serializable and equivalent to running "T1 then T2."
Two-Phase Locking (2PL) — a rule that guarantees serializability
Checking precedence graphs after the fact is impractical at runtime. Instead the database enforces a discipline that makes every schedule it produces conflict-serializable automatically. The classic one is Two-Phase Locking (2PL). Each transaction takes locks on the items it uses (a shared lock to read, an exclusive lock to write), and it must obey one rule about the order in which it acquires and releases them:
The single rule: once a transaction releases any lock, it may never acquire another. Acquiring all goes in the growing phase; releasing all goes in the shrinking phase — hence "two phase."
Every transaction has a single lock point — the instant it grabs its last lock, just before it starts releasing. It turns out you can order all transactions by their lock points, and the resulting order is a valid serial order equivalent to the actual run. The reason: if Ti and Tj conflict on item A, one must hold A's lock first and only release it (entering its shrinking phase) before the other can grab it. So Ti's lock point provably comes before Tj's. There's no way to create a cycle of conflicts, so the precedence graph is always acyclic — i.e. conflict-serializable. That's the guarantee: obey 2PL and every schedule is serializable, with zero runtime graph-checking.
Basic 2PL guarantees serializability but it can cause deadlocks — T1 holds A
and wants B while T2 holds B and wants A, so both wait forever. The database detects this and aborts one.
Also, plain 2PL can still allow a transaction to read another's uncommitted data right before a
rollback (a cascading-abort problem). The fix — Strict 2PL, where all locks are
held until COMMIT/ROLLBACK — plus deadlock handling and
the lock-free alternative (MVCC) are the heart of Session 13: Concurrency Control.
★ Putting it all together
You just learned how databases stay correct when many users hit them at once. Here's the one-paragraph story connecting all four topics:
A transaction bundles work into one unit that obeys ACID — and the tricky letter is Isolation, because running transactions concurrently can produce anomalies (dirty reads, non-repeatable reads, phantoms, lost updates, write skew). To control which anomalies you tolerate, you choose an isolation level — from loose Read Uncommitted up to strict Serializable, trading speed for safety. "Serializable" is defined by serializability theory: an interleaved schedule is safe when it's equivalent to some serial order, which we verify via conflict serializability and a precedence graph. And the database achieves that safety automatically with Two-Phase Locking — grow your locks, then shrink them, never grabbing a lock after releasing one — whose stricter cousin and deadlock handling we'll meet in Session 13.
Quick self-check
Which ACID property stops a crash mid-transfer from "losing" money, and how?
Atomicity. It's all-or-nothing: on restart the database uses its write-ahead log to roll back the half-finished transfer, so the debit is undone and no money disappears.
What's the difference between a non-repeatable read and a phantom read?
A non-repeatable read is an existing row's value changing between two reads (an UPDATE). A phantom is the set of rows matching a query changing — new rows appearing or vanishing (an INSERT/DELETE) when you re-run a range query.
You read 100, re-read in the same transaction and get 150. Which isolation level were you on, and which would fix it?
You were on Read Committed (which allows non-repeatable reads). Stepping up to Repeatable Read pins the value to what you first saw, fixing it.
Which isolation level is needed to prevent write skew, and why don't lower ones suffice?
Serializable. Write skew involves two transactions reading overlapping data then writing different rows, so no single value is overwritten — snapshot/repeatable-read levels miss it. Only a truly serializable guarantee catches the joint invariant violation.
How do you test whether a schedule is conflict-serializable?
Build a precedence graph: a node per transaction, and an edge Ti → Tj whenever an operation of Ti precedes a conflicting operation of Tj (same item, at least one write). If the graph has no cycle, the schedule is conflict-serializable.
State the single rule of Two-Phase Locking and what it guarantees.
Once a transaction releases any lock, it may never acquire another (growing phase then shrinking phase). This guarantees every schedule it produces is conflict-serializable — provably no cycle in the precedence graph.
📚 References & Further Reading
Class material
- 📄 Original course notes / handout (source sheet) — open the shared class material for this session.
- 📘 Class handout: "DBMS Session 12 — Transactions" — the in-class slides and worked schedules for this session.
- 📝 Written assignment: compare 2PL vs MVCC — write up how lock-based Two-Phase Locking and multi-version concurrency control differ in handling conflicts, readers-vs-writers, and aborts.
Papers, docs & deep dives
- CMU 15-445 — Database Systems — Andy Pavlo's free lectures on concurrency control and 2PL; the gold-standard course video set for this material.
- A Critique of ANSI SQL Isolation Levels (Berenson et al., 1995) — the classic paper showing the standard's anomaly definitions are ambiguous; it introduces snapshot isolation and write skew.
- PostgreSQL — Transaction Isolation — clear, practical official docs on what each level really does in a real engine (including Serializable Snapshot Isolation).
- Database System Concepts (Silberschatz, Korth, Sudarshan) — the transactions chapter is the standard textbook treatment of ACID, serializability and locking.
- Two-Phase Locking (overview) — a concise reference on growing/shrinking phases, strict 2PL, and how locking guarantees serializability.