Schedules & Recoverability
Press Next → or use ← → arrow keys
The Newsroom Retraction
"Nobody may quote a colleague until that colleague has officially signed off." In database terms: read only committed data. A schedule is simply an ordering of the reads, writes, commits and aborts of concurrent transactions.
Serial vs Non-Serial Schedules
R1(A) W1(A) R1(B) W1(B) Commit1
R2(A) W2(A) R2(B) W2(B) Commit2R1(A) R2(A) W1(A) W2(A) Commit1 Commit2Both read the original A; T2's write overwrites T1's — T1's update is lost.
Bad: non-serializable (anomalies) → Better: serializable (equals some serial) → Best: cascadeless (serializable + one abort never forces others).
The Cascading Abort Problem
A dirty read is reading a value another transaction wrote but hasn't committed. If that writer aborts, the reader's work is invalid — and the failure cascades.
Cascading aborts amplify the cost of any single failure — one timeout on one query can force dozens of unrelated transactions to roll back. This is an operational disaster, not a theoretical curiosity.
Recoverable Schedules
A schedule is recoverable if a transaction Tj commits only after every transaction Ti it read from has already committed. You never commit on top of data that might still be undone.
Recoverability only fixes commit order — it still permits reading uncommitted data, so cascading aborts are still possible. To stop those, we need a stricter class: cascadeless.
Cascadeless Schedules (ACA)
Every transaction reads only committed values. Formally, whenever Tj reads X written by Ti, the commit of Ti comes first: Wi(X) → Commit(Ti) → Rj(X). Also called ACA — Avoids Cascading Aborts.
| t | T1 | T2 |
|---|---|---|
| t1 | R(A) | |
| t2 | W(A) | |
| t3 | R(A) | |
| t4 | W(A) | |
| t5 | Abort | |
| t6 | forced abort |
| t | T1 | T2 |
|---|---|---|
| t1 | R(A) | |
| t2 | W(A) | |
| t3 | Commit | |
| t4 | R(A) | |
| t5 | W(A) | |
| t6 | Commit |
S2 simply moves T1's Commit before T2's read. Now an abort by T1 cannot reach T2 — no cascade is possible.
Cascadeless Does NOT Mean Serial
Two transactions touching different items can run fully concurrently and still be cascadeless — the restriction is only on reading uncommitted data.
| t | T1 | T2 | T3 |
|---|---|---|---|
| t1–t2 | R(A) · W(A) | ||
| t3–t4 | R(B) · W(B) | ||
| t5 | Commit | ||
| t6 | R(A) ← after Commit1 | ||
| t7–t8 | W(C) · Commit | ||
| t9–t10 | W(A) · Commit |
The only cross-transaction read — R3(A) at t6 — happens after Commit1 at t5. Meanwhile T2 and T3 overlap freely around t6–t8. Cascadelessness forbids dirty reads, not concurrency.
Strict Schedules — The Strongest
A schedule is strict if no transaction may read OR write an item X until every earlier transaction that wrote X has committed or aborted. It restricts not just reads (like cascadeless) but writes too.
Because no one touches X until its writer finishes, undoing an aborted transaction is a clean, local operation — the strongest recovery guarantee short of running serially.
The Recoverability Hierarchy
Each inner class is a stricter promise than the one around it — and membership in an inner class automatically grants every outer-class guarantee. Serial is safest but slowest; recoverable is the loosest that's still safe to undo.
The Classes Side by Side
| Class | Guarantee | Cost |
|---|---|---|
| Serial | No interleaving — trivially safe | Zero concurrency |
| Strict | No read/write of X until earlier writers commit/abort | Most blocking |
| Cascadeless | Reads only committed data — no cascading aborts | Some blocking on reads |
| Recoverable | Tj commits only after every Ti it read from commits | Allows dirty reads; cascades possible |
| Other | No guarantees — unrecoverable | Never allow |
Almost every engine (PostgreSQL, MySQL/InnoDB, SQL Server, Oracle) produces at least cascadeless schedules at any normal isolation level. Only READ UNCOMMITTED — where even allowed — lets dirty reads and cascading aborts appear.
Identify the Schedule Type
| Schedule | Type |
|---|---|
| R1(X) W1(X) Commit1 R2(X) W2(X) Commit2 | Serial (also cascadeless & strict) |
| R1(X) W1(X) R2(X) W2(X) Commit1 Commit2 | Non-serial, NOT cascadeless — T2 dirty-reads X at step 3 |
| R1(X) W1(X) Commit1 R2(X) W2(X) Commit2 | Cascadeless (T1 commits before T2 reads) |
| R1(X) R2(Y) W1(X) Commit1 W2(Y) R2(X) Commit2 | Non-serial AND cascadeless — R2(X) at step 6 is after Commit1 |
Find every cross-transaction read of an item. If each one happens after the writer's Commit → cascadeless. If even one reads uncommitted data → not.
Fix a Cascading Schedule
R1(A) W1(A)
R2(A) W2(A)
R3(A) W3(A)
Commit1 Commit2 Commit3T2 reads A written by T1 before Commit1; T3 reads A written by T2 before Commit2 — two dirty reads.
R1(A) W1(A) Commit1
R2(A) W2(A) Commit2
R3(A) W3(A) Commit3Each writer commits before the next reads A. Cascadeless (here, also serial).
Move each writer's Commit before the next transaction's read of the same item. No other change is usually needed to remove every cascade.
Academic vs Industry Lenses
Cascadelessness costs a little read-blocking but buys predictable recovery. That trade is almost always worth it — which is why every mainstream engine makes it the default.
Rapid-Fire Concept Check
| Concept | Answer |
|---|---|
| Schedule with no interleaving | Serial |
| Serial schedules for n transactions | n! |
| One transaction's abort forces others | Cascading |
| Cascadeless rule | Read only committed data |
| Alternative term for cascadeless | ACA (Avoids Cascading Aborts) |
| Uncommitted read term | Dirty read |
| Restricts both reads and writes to committed | Strict |
| Strict implies → cascadeless implies → | Recoverable |
| Protocol producing strict schedules | SS2PL (Strict 2PL) |
| Isolation level allowing cascading aborts | READ UNCOMMITTED |
Golden Rules of Schedules
Read Only What's Signed Off
A schedule's safety on abort is a ladder: recoverable fixes commit order, cascadeless forbids dirty reads so one abort never drags others down, and strict forbids touching uncommitted data at all — making rollback trivial. The fix for a cascade is always the same: commit the writer before anyone else reads it.
Read only committed data and you're cascadeless; that one habit turns a domino of aborts into a single, contained rollback.
🧾 End of tutorial · Press ← to review, or click Restart