The Story That Explains Schedules
Now T2 is in trouble. Their editorial contains a quote that no longer exists. T2 has to also erase their work. If a third writer T3 used T2's draft, they too must roll back. One bad source triggers a chain of forced retractions. This is the cascading abort problem.
A simple rule kills the chain: nobody is allowed to quote a colleague until that colleague has officially signed off on it. If T2 had waited until T1 committed their story, T2 would be safe. In databases, that rule is what makes a schedule cascadeless.
A schedule is an ordering of the operations (reads, writes, commits, aborts) of one or more concurrent transactions. The order matters: it decides what each transaction sees, what it produces, and how badly things break when one of them fails. This tutorial covers the three foundational schedule types you will be asked about — Serial, Non-Serial, and Cascadeless — plus where they sit in the wider hierarchy.
Serial Schedules — Safe but Slow
A serial schedule is one in which the operations of different transactions are not interleaved. One transaction executes from start to commit before the next one begins. With n transactions there are exactly n! possible serial schedules.
Serial: each transaction runs to completion before the next starts. Non-Serial: operations of T1 and T2 are interleaved — faster, but only correct if the interleaving is well-chosen.
Non-Serial Schedules — Fast but Risky
A non-serial schedule interleaves the operations of two or more transactions in time. They are faster because the CPU and disk can work on multiple transactions in parallel — but not every interleaving is safe. Only some non-serial schedules are equivalent to a serial one (those are the serializable ones; the rest produce anomalies).
| Time | Transaction 1 | Transaction 2 |
|---|---|---|
| t1 | R(A) | |
| t2 | R(A) | |
| t3 | W(A) | |
| t4 | W(A) | |
| t5 | Commit | |
| t6 | Commit |
In the table above, both T1 and T2 read the original value of A, compute updates separately, then write back. T2's write overwrites T1's. T1's update is lost. This is a non-serial schedule that is not serializable — a textbook example of the kind of interleaving the DBMS must prevent.
The Cascading Abort Problem
Imagine T2 reads a value that T1 has written but not yet committed. This is called a dirty read. If T1 later aborts, every byte T1 wrote must be undone — and T2's read becomes invalid. T2 must abort too. If T3 read from T2, T3 must also abort. One failure cascades into many.
Top row: T1 aborts → T2 and T3 are forced to abort because they read uncommitted values. Bottom row: in a cascadeless schedule, T2 and T3 wait for T1 to commit, so an abort cannot cascade.
Cascading aborts amplify the cost of any single failure. A timeout on one query can force dozens of unrelated transactions to roll back. The work is wasted, the user-visible latency spikes, and the lock manager thrashes. In a high-throughput system this is unacceptable — which is why every real engine guarantees at least cascadeless schedules.
Cascadeless Schedules
A schedule is cascadeless (sometimes written ACA — Avoids Cascading Aborts) if every transaction reads only values that have been written by already-committed transactions.
A schedule S is cascadeless if, whenever a transaction Tj reads a value of X written by Ti (where i ≠ j), the commit of Ti precedes the read by Tj. In symbols: Wi(X) → Commit(Ti) → Rj(X).
Example — Comparing Cascading vs Cascadeless
| Time | T1 | T2 |
|---|---|---|
| t1 | R(A) | |
| t2 | W(A) | |
| t3 | R(A) | |
| t4 | W(A) | |
| t5 | Abort | |
| t6 | forced abort |
| Time | T1 | T2 |
|---|---|---|
| t1 | R(A) | |
| t2 | W(A) | |
| t3 | Commit | |
| t4 | R(A) | |
| t5 | W(A) | |
| t6 | Commit |
The only difference: in S2, T1's Commit at t3 happens before T2's R(A) at t4. That one ordering constraint is enough to kill the cascading abort problem entirely.
The Full Schedule Hierarchy
The schedule classes nest inside each other like Russian dolls. Each inner class is a stricter promise than the one around it.
Serial ⊂ Strict ⊂ Cascadeless ⊂ Recoverable ⊂ All Schedules. Every serial schedule is strict, every strict schedule is cascadeless, and so on.
| Class | Guarantee | Cost |
|---|---|---|
| Serial | No interleaving at all — trivially safe | Zero concurrency — too slow |
| Strict | No read OR write of X until all earlier writers of X have committed/aborted | Most blocking |
| Cascadeless | Reads only see committed data — no cascading aborts | Some blocking on reads |
| Recoverable | Tj commits only after every Ti it read from has committed | Allows dirty reads — cascading aborts still possible |
| Other | No guarantees — may be unrecoverable | Should never be allowed by a DBMS |
Most production databases enforce strict schedules via Strict Two-Phase Locking (SS2PL): locks are held until commit, which means no read or write of an item can happen while another transaction has it — preventing both cascading aborts and many other anomalies. Strict implies cascadeless implies recoverable, so SS2PL gives all three guarantees with one mechanism.
Numerical 1 — Identify the Schedule Type
Problem: Classify each schedule below as Serial, Non-Serial (cascading), or Cascadeless. Justify your choice.
Schedule A
Schedule B
Schedule C
Schedule D
Numerical 2 — Fix a Cascading Schedule
Problem: Schedule S below allows a cascading abort. Modify it minimally to make it cascadeless.
The fixed schedule is cascadeless — in fact it is also serial. In this particular problem (each transaction reads what the previous one wrote), avoiding cascading aborts forces serial execution. In schedules where transactions touch different items, cascadelessness can coexist with significant concurrency.
Numerical 3 — Mixed Items, Real Concurrency
Problem: Determine whether Schedule T is cascadeless, given:
| Time | T1 | T2 | T3 |
|---|---|---|---|
| t1 | R(A) | ||
| t2 | W(A) | ||
| t3 | R(B) | ||
| t4 | W(B) | ||
| t5 | Commit | ||
| t6 | R(A) | ||
| t7 | W(C) | ||
| t8 | Commit | ||
| t9 | W(A) | ||
| t10 | Commit |
Every cross-transaction read happens after the relevant writer has committed. The schedule is cascadeless. Notice that T2 and T3 are actually running concurrently around t6–t8 — cascadelessness does not forbid concurrency, it only forbids reading uncommitted data.
Academic View vs Industry View
| Aspect | Detail |
|---|---|
| Focus | Formal definitions and class hierarchy |
| Goal | Prove a schedule belongs to a class |
| Tools | Time-ordered operation lists, precedence graphs |
| Common ask | "Is this schedule cascadeless / recoverable / strict?" |
| Insight | Hierarchy: Serial ⊂ Strict ⊂ Cascadeless ⊂ Recoverable |
| Aspect | Detail |
|---|---|
| Focus | Throughput while avoiding production pain |
| Default | Strict via SS2PL or MVCC + commit visibility |
| Cost saved | No cascading aborts → predictable latency |
| Trade-off | Locks held longer → some throughput loss vs weaker levels |
| Practical advice | Trust the default isolation; don't read uncommitted data unless you know exactly why |
Almost every mainstream engine (PostgreSQL, MySQL/InnoDB, SQL Server, Oracle) produces at least cascadeless schedules at any normal isolation level. The READ UNCOMMITTED level (where allowed at all) is the only place dirty reads — and therefore potential cascading aborts — can appear. It exists mostly for read-only reporting where occasional dirty data is acceptable.
Rapid-Fire Concept Check
| Question | Answer |
|---|---|
| Schedule with no interleaving of operations | Serial |
| Number of serial schedules for n transactions | n! |
| A schedule where one transaction's abort forces others to abort | Cascading |
| The rule that defines cascadeless schedules | Read only committed data |
| Alternative name for cascadeless | ACA (Avoids Cascading Aborts) |
| A read of an uncommitted write is called | Dirty read |
| Class containing both reads and writes restricted to committed data | Strict |
| Strict implies cascadeless implies… | Recoverable |
| Protocol that produces strict schedules | SS2PL (Strict 2PL) |
| Isolation level that allows cascading aborts | Read Uncommitted |