Recoverable, cascadeless and strict schedules; how they nest

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. What creates the gap between view and conflict serializability? from Lesson 6.4.3
2. When is a schedule conflict serializable? from Lesson 6.4.2
3. What is a dirty read? from Lesson 6.2.1

1 · The Hook

T1 writes A, T2 reads that A and commits, then T1 aborts. T1's write must be undone, but T2 has already committed a result computed from it, and committed transactions cannot be undone (durability). The database is stuck in an impossible state. Serializability did not prevent this; recoverability rules do.

2 · Predict First

Which order of commits would have made W1(A) R2(A) … safe if T1 might abort: C2 before C1, or C1 before C2?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

C1 before C2. If T2 waits to commit until T1 commits, an abort of T1 can still abort T2 too. A schedule where readers commit only after the writers they read from is recoverable.

Reads-from

Tj reads from Ti if Tj reads an item X whose last write before that read was by Ti (and Ti had not aborted).

Recoverable schedule

A schedule is recoverable if, whenever Tj reads from Ti, Ti commits before Tj commits.

• Non-recoverable example: W1(A) R2(A) C2 … A1 (or C1 after C2).
• Recoverable but with cascades: W1(A) R2(A) C1 C2 is fine; if instead T1 aborts before C2, T2 must also abort: a cascading rollback.

Cascadeless schedule (ACA: avoids cascading aborts)

A schedule is cascadeless if every transaction reads only committed values: whenever Tj reads X written by Ti, Ti has already committed before that read.

• W1(A) C1 R2(A) is cascadeless; W1(A) R2(A) C1 is not.

Strict schedule

A schedule is strict if no transaction reads or writes an item X until the last transaction that wrote X has committed or aborted.

• Strictness also forbids overwriting uncommitted writes: W1(A) W2(A) C1 is cascadeless (no reads) but not strict.
• Benefit: undo is simple (restore the before-image of each written item).

How they nest

Strict ⊂ Cascadeless ⊂ Recoverable ⊂ all schedules. Serial schedules are strict.

Recoverability is independent of serializability: a schedule can be serializable and not recoverable, or recoverable and not serializable.

Classifying (verified examples)

4 · Visual

Strict ⊂ Cascadeless ⊂ Recoverable. Serial schedules are strict.

5 · Worked Examples

Example 1 Easy

W1(X) R2(X) C1 C2: recoverable? cascadeless?

Solution

T2 reads from T1 and T1 commits first: recoverable. T2 read X before T1 committed: not cascadeless.

Example 2 Medium

R1(X) W1(X) R2(Y) W2(Y) C2 R1(Y) C1: classify.

Solution

T1 reads Y after T2 committed it, so T1 reads from a committed transaction: cascadeless; recoverable (C2 before C1). Strict? T1 reads Y after T2's commit; no one touches X after W1(X) before C1: strict.

Example 3 GATE

Which is true? (A) Every recoverable schedule is cascadeless. (B) Every cascadeless schedule is recoverable. (C) Every conflict serializable schedule is recoverable. (D) Every strict schedule is serial.

Solution

(B). A is false (W1 R2 C1 C2), C is false (R1 W1 R2 W2 C2 C1 is CS but not recoverable), D is false.

8 · Connect the Dots

Chapter 6.4 decided which schedules are equivalent to serial ones; this lesson added what is safe under aborts. Next: how a DBMS produces good schedules in practice: locks.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Recoverable

Which schedule is not recoverable?

1. (A) W1(A) R2(A) C1 C2
2. (B) W1(A) C1 R2(A) C2
3. (C) R1(A) R2(A) C2 C1
4. (D) W1(A) R2(A) C2 C1

Q2 · MCQ · 2 mark(s) — Cascadeless

R1(A) W1(A) R2(A) C1 W2(A) C2 is:

1. (A) recoverable but not cascadeless
2. (B) not recoverable
3. (C) strict
4. (D) cascadeless but not strict

Q3 · MCQ · 2 mark(s) — Strict

W1(A) W2(A) C1 C2 is:

1. (A) strict
2. (B) recoverable, cascadeless, not strict
3. (C) not cascadeless
4. (D) not recoverable

Q4 · MSQ · 2 mark(s) — Facts

Which are true?

1. (A) Every strict schedule is cascadeless.
2. (B) Every conflict serializable schedule is recoverable.
3. (C) Every serial schedule is strict.
4. (D) Every cascadeless schedule is recoverable.

Q5 · MCQ · 1 mark(s) — Cascading rollback

A cascading rollback happens when:

1. (A) two transactions deadlock
2. (B) a transaction reads uncommitted data and the writer aborts
3. (C) a transaction commits twice
4. (D) a schedule is serial

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

reads-from (recovery)recoverable schedulecascading rollbackcascadeless schedule (ACA)strict schedulenesting of recoverability classes