Recoverable schedules and cascading aborts
Recoverable schedules ensure transactions that read others' updates wait for those writers to commit; cascadeless and strict schedules are stronger forms that prevent cascading aborts and dirty-accesses.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Two or three sentences: where an engineer uses this.
Database engines, recovery modules and transaction managers use these ideas when designing concurrency control and crash recovery. Choosing a recoverable or strict scheduling policy prevents lost updates, inconsistent reads and long chains of aborts (cascading aborts) that complicate recovery and reduce throughput.
Key ideas
Explain plainly, define every term before use, and give exact statements and derivations.
Assumptions: We assume a standard transaction model (atomic transactions that end with commit or abort), a schedule is a sequence of operations from transactions, and operations use data items (X, Y, ...). We use the notation r_i(X), w_i(X), c_i, a_i for read, write, commit and abort by transaction T_i.
Schedule: a sequence of operations (reads/writes/commits/aborts) from a set of transactions, showing their interleaving.
Dirty read: A read that returns a value written by a transaction that has not yet committed.
Reads-from relation (also written wr(Tj, Ti, X) or “Ti reads-from Tj on X”): If schedule S has w_j(X) followed later by r_i(X) and no intervening write to X, then Ti reads-from Tj for X. Define this precisely before using it.
Recoverable schedule: A schedule S is recoverable iff for every pair of transactions T_i and T_j, if T_i reads a data item previously written by T_j (Ti reads-from Tj), then T_j must commit before T_i commits. Exact formal statement:
- For all Ti, Tj and data item X, if wr(Tj, Ti, X) holds in S, then c_j < c_i in S (where c_k denotes the position of T_k's commit in the schedule). If T_j aborts, T_i must not commit; in practice, the system will abort T_i to maintain correctness. An irrecoverable (non-recoverable) schedule is one in which some T_i commits after reading a value from T_j before T_j commits (i.e., there exists wr(Tj, Ti, X) with c_i < c_j).
Cascading abort: A cascading abort occurs when one transaction aborts and that forces one or more other transactions that read its uncommitted writes to abort; this abort may in turn force further aborts, creating a chain.
Cascadeless schedule: A schedule is cascadeless iff no transaction ever reads a data item written by an uncommitted transaction. Equivalently, for all Ti, Tj, if Ti reads-from Tj, then T_j must have already committed before Ti's read: c_j < r_i(X). This forbids dirty reads and so prevents cascading aborts caused by reads of uncommitted data.
Strict schedule: A schedule is strict iff no transaction reads or writes a data item that has been written by an uncommitted transaction. Formally:
- For any Ti, Tj and item X, if w_j(X) appears before some operation op_i(X) (read or write) of Ti, then either c_j or a_j must appear before op_i(X). This implies that all reads and writes on X by other transactions wait until the last writer on X has committed or aborted.
Important logical implications (exact statements you may be asked to prove):
- Strict ⇒ Cascadeless ⇒ Recoverable.
Derivations (step-by-step proofs universities typically expect):
Proof that Strict ⇒ Cascadeless:
- Assume schedule S is strict. By definition, strict prohibits any read of X by Ti if a previous uncommitted write w_j(X) exists; thus if Ti reads X that was written by Tj, Tj must have already committed. Therefore S is cascadeless. QED.
Proof that Cascadeless ⇒ Recoverable:
- Assume S is cascadeless. If Ti reads-from Tj on X, then by cascadeless definition Tj committed before the read r_i(X). Since commit order respects time, c_j < r_i(X) < c_i (because Ti cannot commit before its read). Therefore c_j < c_i, satisfying the recoverable condition for this pair. Since this holds for every reads-from relation, S is recoverable. QED.
Note assumptions used: transactions eventually commit or abort; read operations occur before a transaction's commit.
Diagram to draw (describe exactly what to draw and label):
- Draw a horizontal timeline for each transaction T1, T2, T3 (three parallel horizontal lines). On each line place boxes for operations in order (e.g., w1(X), r2(X), c1, c2). Use arrows from a write operation box on one timeline to a read operation box on another timeline where reads-from holds (label these arrows "reads-from"). Mark commits with a filled dot labeled c_i and aborts with an X labeled a_i. This diagram helps visualise causal dependencies and cascading abort chains.
Formulas
For this theory topic, list the schedule notation and the exact conditions to remember:
r_i(X): Transaction T_i reads item X.w_i(X): Transaction T_i writes item X.c_i: Transaction T_i commits.a_i: Transaction T_i aborts.- Recoverable condition:
if wr(Tj, Ti, X) then c_j < c_i(meaning commit of writer precedes commit of reader). - Cascadeless condition:
if wr(Tj, Ti, X) then c_j < r_i(X)(writer must commit before reader reads). - Strict condition:
if w_j(X) < op_i(X) where op_i is r or w, then (c_j or a_j) < op_i(X)(the writer must have committed or aborted before any other transaction reads or writes X).
Symbols: < means "appears before in the schedule". No SI units apply.
Worked examples
Model-answer style schedules and reasoning the examiner expects.
Example 1 — recoverable but not cascadeless (show steps): Schedule S1 (operations in order):
w_1(X)r_2(X)(reads value written by T1)c_1c_2
Analysis steps:
- Identify reads-from: wr(T1, T2, X) because w1(X) precedes r2(X) and no other write intervenes.
- Check recoverable: c_1 appears before c_2, so the recoverable condition
if wr(T1,T2,X) then c_1 < c_2holds — S1 is recoverable. - Check cascadeless: cascadeless requires c_1 < r_2(X). Here r_2(X) happens before c_1, so this fails — S1 is not cascadeless.
- Check strict: strict forbids r_2(X) if w_1(X) is uncommitted, so S1 is not strict.
- Conclusion: S1 is recoverable; it permits a dirty read but avoids inconsistency because writer eventually committed before reader committed.
Example 2 — cascading abort occurs (model-exam answer): Schedule S2:
w_1(X)r_2(X)(reads from T1)a_1(T1 aborts)
Analysis:
- wr(T1,T2,X) holds (T2 read value from T1).
- T1 aborts; T2 has read a value that is now invalid. To maintain correctness, T2 must also abort (or else database would reflect a value from an aborted transaction). This forced abort of T2 is a cascading abort.
- S2 causes a cascading abort; to remain recoverable, T2 must not commit (in practice it will be aborted). S2 is not cascadeless and not strict.
Example 3 — strict schedule (model answer): Schedule S3:
w_1(X)c_1r_2(X)w_2(X)c_2
Analysis:
- Any op by T2 on X happens after c_1, so no reads/writes on X access uncommitted writes. This satisfies strict definition.
- Therefore S3 is strict ⇒ cascadeless ⇒ recoverable.
- No cascading aborts possible for X here.
Each worked example must be justified by pointing to the reads-from relations and commit ordering.
Common mistakes
- Forgetting that if writer aborts, any readers that read its uncommitted data must abort (not commit).
- Mixing up time order: check whether commit appears before the read or before the reader's commit depending on cascadeless vs recoverable.
- Not drawing reads-from arrows in diagrams; the arrows make dependencies clear.
For your exam
Types of questions and what full-marks answers include:
- Definitions: Give precise definitions of recoverable, cascadeless, strict, and cascading abort. State the exact formal condition (using r_i(X), w_j(X), c_k) for each.
- Short notes: Explain why cascading aborts are undesirable, and name protocols that guarantee strictness (e.g., strict two-phase locking). Mention trade-offs (strictness reduces concurrency but simplifies recovery).
- Derivations / proofs: Prove the implication chain Strict ⇒ Cascadeless ⇒ Recoverable with clear use of definitions; draw a counterexample for the reverse implications.
- Diagram questions: Draw timelines for transactions and show reads-from arrows; label commits and aborts; explain whether schedule is recoverable / cascadeless / strict.
- Long question / model answer: Given a schedule, identify reads-from relations, determine recoverability/cascadeless/strict, and show any cascades if aborts occur. Always state which rule you used to decide.
What examiners expect: precise formal conditions, clear identification of reads-from edges, correct commit-order reasoning, and a small diagram or timeline if asked.
Quick check
Three short questions:
- Define a recoverable schedule in one line.
- What is a cascading abort?
- Which is stronger: cascadeless or strict?
Answers: 1) A schedule where if Ti reads from Tj then Tj must commit before Ti commits. 2) When abort of one transaction forces aborts of other transactions that read its uncommitted writes. 3) Strict is stronger than cascadeless.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?