CS Core & Software Engineering · Databases
Transactions, Accidents and Recovery
ACID on one sale, dirty/lost/phantom accidents, conflict serializability and write-ahead logging.
Two cashiers at the same kiosk. A transaction is one sale treated as a bundle: all-or-nothing, rules still hold, the other cashier does not see a half-write, and a crash after commit does not erase it. This lesson names the accidents and the schedule test. Isolation levels — which accidents a setting still allows — are the next lesson.
- CS Core & Software Engineering
- Hard level
- 5 concepts
- 3 practice questions
1ACID on one sale
A transaction is a bundle of reads and writes the kiosk wants to treat as one event. Asha paying for two samosas might decrement stock and insert sale 100. Atomicity: both happen, or neither — we do not keep the stock drop if the sale insert fails. Consistency: the bundle leaves the shop satisfying its rules (qty ≥ 1, stock ≥ 0, foreign keys live). Isolation: Ravi's concurrent tea sale must not see Asha's half-finished write. Durability: once we say the sale committed, a power cut must not erase it.
The four letters are promises, not mechanisms. Logging gives Durability and helps Atomicity undo. Locks or snapshots give Isolation. Constraints give Consistency. The next concepts show what goes wrong when Isolation is weak, and how a schedule records the interleaving.
Figure. Four promises on one sale. Isolation is the one the next concepts spend time on.
Asha's sale as ACID
- AtomicStock decrement and Sale insert commit together, or both roll back.
- ConsistentAfterwards stock is non-negative and student_id 1 still exists.
- Isolated / DurableRavi must not see a half-write; a crash after commit still shows sale 100.
| Letter | Promise on sale 100 |
|---|---|
| Atomicity | stock and Sale row both land, or neither |
| Consistency | rules still hold after commit |
| Isolation | Ravi does not see Asha mid-write |
| Durability | committed sale 100 survives a crash |
Which ACID property says a committed sale still exists after a crash?
- Atomicity
- Consistency
- Isolation
- Durability
Durability is "committed means it stays". Atomicity is all-or-nothing while the transaction is still running.
2Dirty read, lost update, phantom
When two cashiers interleave, three named accidents appear. A dirty read: T1 writes Tea stock = 50 and has not committed; T2 reads 50; T1 aborts back to 8. T2 planned on a number that never became real. A lost update: both read stock 8, both add 10, both write 18 — the second add vanished. A phantom: T2 counts tea sales (two rows), T1 inserts sale 104 for Tea, T2 counts again and sees three. The new row is the phantom.
A non-repeatable read is the middle sibling: T2 reads Asha's hostel A, T1 commits a move to hostel C, T2 reads again and sees C. Same row, different committed value. Phantoms are new rows; non-repeatable reads are changed rows. Isolation levels in the next lesson are named by which of these they still allow.
Figure. T2 read 50 while T1 was unfinished. After the abort the real stock is 8. That is a dirty read.
Tea stock dirty read
- T1 writesstock := 50, not committed.
- T2 readssees 50 and maybe sells against it.
- T1 abortsstock is 8 again. T2's 50 was dirty.
| Name | What T2 saw at the kiosk |
|---|---|
| Dirty read | uncommitted stock 50 that later vanished |
| Non-repeatable | Asha's hostel A, then committed C |
| Phantom | two tea sales, then a new third row |
| Lost update | two +10 restocks, final stock 18 not 28 |
T2 reads a value T1 wrote before T1 committed. T1 then rolls back. T2 performed a
- Phantom read
- Dirty read
- Non-repeatable read
Dirty = read uncommitted data that may vanish. Non-repeatable = two different committed values. Phantom = a new matching row.
3Schedules and conflicting operations
A schedule is the interleaving of two (or more) transactions' reads and writes, in the order they hit the same data. Serial means one transaction finishes before the other starts: Asha's whole sale, then Ravi's. Concurrent means their steps mix.
Two operations conflict when they belong to different transactions, touch the same item, and at least one is a write. R1(stock) and W2(stock) conflict. R1(stock) and R2(stock) do not. Conflict is the raw material of the next test: if we can swap non-conflicting neighbours until the schedule is serial, the mix was only apparent.
Figure. Left pair conflicts (a write). Right pair is two reads of stock — no conflict.
Do these two steps conflict?
- Different transactions?T1 versus T2 — yes.
- Same item?Both mention Tea stock — yes.
- A write?If either writes, they conflict; two reads do not.
| Pair | Conflict? |
|---|---|
| R1(stock), R2(stock) | no |
| R1(stock), W2(stock) | yes |
| W1(stock), W2(stock) | yes |
| W1(stock), R2(samosa) | no — different items |
R1(A) and W2(A) conflict because
- They are in the same transaction
- Different transactions, same item, one write
- Every pair of operations conflicts
Conflict needs all three: different transactions, same item, at least one write.
4Conflict serializability
Draw a precedence graph: a node per transaction, an edge T1 → T2 when a conflicting operation of T1 appears before one of T2 on the same item. The schedule is conflict-serializable exactly when that graph has no cycle. Acyclic means there is a serial order that agrees with every conflict.
Example: T1 reads stock, T2 writes stock (edge T1 → T2). Later T2 reads samosa, T1 writes samosa (edge T2 → T1). Cycle — not conflict-serializable. If both conflicts run T1 then T2, the graph is a single arrow and the mix is allowed: it matches the serial order T1 then T2.
Figure. Edges both ways: a cycle. The schedule is not conflict-serializable.
Build the graph
- NodesOne per transaction — T1, T2.
- EdgesTi → Tj when a conflicting Ti-op precedes a conflicting Tj-op on the same item.
- Cycle?Yes → reject. No → some serial order matches the conflicts.
Two edges, a cycle
Schedule: R1(A) W2(A) R2(B) W1(B). Is it conflict-serializable? How many serial schedules exist for these two transactions?
- R1(A) before W2(A)edge T1 → T2
- R2(B) before W1(B)edge T2 → T1
- cycle?yes — not conflict-serializable
- serial schedules for 2 txns2! = 2
Pro tip. n transactions have n! serial schedules. Conflict-serializable means "equivalent to one of those".
R1(A) W2(A) R2(B) W1(B) is conflict-serializable?
- Yes — each item is touched by both
- No — the precedence graph has a cycle
- Yes — there are no write–write conflicts
R1(A)–W2(A) gives T1→T2; R2(B)–W1(B) gives T2→T1. The cycle means not conflict-serializable.
5Write-ahead logging
Durability and Atomicity after a crash need a log: a sequential file of "I am about to change this". Write-ahead logging (WAL) is the rule that the log record for an update must reach stable storage before the dirty data page does. If the page hit disk first and then we crashed, we would have a change with no record of how to undo it.
On restart: undo the losers (transactions that never committed) and redo the winners (those whose commit record is in the log). Asha's sale 100 with a commit record is replayed even if the Sale page never flushed. A restock that aborted is undone even if its page did flush.
Figure. Log record on stable storage, then the data page may flush. The other order is illegal.
Crash, then recover
- WALLog the stock change before the stock page may flush.
- Redo winnersSale 100 committed — replay it if the page is stale.
- Undo losersThe restock never committed — put stock back to 8.
Who is a winner?
Log: W1(stock=50), COMMIT T2 (sale 101), W1(stock=8), crash. T1 never committed. What does recovery do to stock and to sale 101?
- T2 commit in log?yes — winner
- T1 commit in log?no — loser
- sale 101redo / keep
- T1's stock writesundo
Pro tip. Commit record in the log decides winner versus loser, not whether a page flushed.
Under write-ahead logging, which action is illegal?
- Flushing a log record for an update before flushing the data page
- Flushing the dirty data page before its log record is on stable storage
- Replaying a committed update during redo
WAL forbids data-before-log. Log-before-data and redo of winners are the legal path.
Notes
- ACID: Atomicity (all-or-nothing), Consistency (valid state to valid state), Isolation (concurrent = serial effect), Durability (committed changes persist).
- Conflict serializability is tested with a precedence (serialization) graph; a schedule is conflict-serializable iff the graph is acyclic.
- Two-Phase Locking (2PL) has a growing phase (acquire locks) and shrinking phase (release locks); 2PL guarantees conflict-serializability.
- Strict 2PL holds all exclusive locks until commit/abort, preventing cascading rollbacks and ensuring recoverability.
- Recovery uses a log with WAL (write-ahead logging); undo removes uncommitted changes, redo reapplies committed ones after a crash.
Formulas
- Conflict-serializable iff the precedence graph has no cycle.
- Two operations conflict if they belong to different transactions, access the same item, and at least one is a write.
- Number of possible serial schedules for n transactions = n! (ordering).
- 2PL = growing phase then shrinking phase; no lock is acquired after the first release.
- Strict schedule: no transaction reads or writes an item written by an uncommitted transaction.
Exam traps & shortcuts
- Draw the precedence graph: an edge Ti->Tj for each conflicting pair; a cycle means NOT conflict-serializable.
- 2PL guarantees serializability but can cause deadlocks; timestamp ordering avoids deadlock but may abort more.
- View-serializable is a superset of conflict-serializable (every conflict-serializable schedule is view-serializable).
Reference tables
| Promise | Breaks when |
|---|---|
| Atomicity | stock drops but Sale insert fails |
| Isolation | dirty 50, lost +10, or a phantom tea row |
| Durability | committed sale 100 gone after a crash |
Recap
A bundle, three accidents, a graph, a log.
- ACID
- All-or-nothing, rules hold, no half-writes visible, commit survives.
- Dirty
- Read uncommitted 50 that later becomes 8.
- Conflict
- Different txns, same item, at least one write.
- CSR
- Precedence graph acyclic ⇔ conflict-serializable.
- WAL
- Log before page. Redo winners, undo losers.
Practise Transactions, Accidents and Recovery
Reading is free and needs no account. Practice, mocks and progress live in the app.
- 3 exam-style questions on this topic, with explanations
- A 3-question practice set that ends the chapter
- Timed mocks scored with the real marking scheme
- Readiness tracked per topic, kept on your device