Recoverability: Recoverable, Cascadeless and Strict Schedules

Serializability ignores failures: it assumes every transaction commits. A real system must also handle a transaction that aborts after other transactions have read what it wrote. Recoverability classifies schedules by how safely they survive such aborts, using the positions of commits and aborts. A schedule can be serializable and still unacceptable because an abort would force the system to undo a committed transaction.

The tasks are to decide whether a given schedule is recoverable, cascadeless or strict, and how these classes relate to each other and to conflict serializability.

Reads from. $T_j$ reads $X$ from $T_i$ if $R_j(X)$ reads the value written by the latest $W_i(X)$ before it, and $T_i \ne T_j$. A write by a transaction that has already aborted has been undone, so a later read does not read from it.

Recoverable. Whenever $T_j$ reads from $T_i$, $T_i$ commits before $T_j$ commits. (If $T_j$ never commits, the condition places no constraint.) In a non-recoverable schedule, an abort of $T_i$ after $T_j$ has committed cannot be handled correctly: $T_j$ read a value that is being undone, but a committed transaction cannot be rolled back.

Cascading rollback. In a recoverable schedule an abort of $T_i$ may still force every transaction that read from $T_i$ to abort, then every transaction that read from those, and so on.

Cascadeless (avoids cascading aborts, ACA). A transaction reads an item only after any other transaction whose still-uncommitted value it would read has committed (or its aborted write has been undone). No dirty reads, so no cascading rollback.

Strict. No transaction reads or writes $X$ until the other transaction that last wrote $X$ has committed or aborted. Undo can then simply restore before-images.

Hierarchy:

Each inclusion is strict. Recoverability is independent of serializability: a schedule can be conflict serializable but not recoverable, or strict but not conflict serializable.

Check the strongest property first: a strict schedule is automatically cascadeless and recoverable.

Why strict implies cascadeless. Cascadeless restricts reads of uncommitted data; strict restricts both reads and writes, so it forbids more.

Why cascadeless implies recoverable. If $T_j$ reads from $T_i$ only after $C_i$, then $C_i$ precedes $R_j(X)$ and therefore precedes $C_j$.

Why strict matters for recovery. If $T_2$ overwrites an uncommitted $W_1(X)$ and then $T_1$ aborts, restoring $T_1$'s before-image would wipe out $T_2$'s write. Strictness rules this out, so undo by before-images is always correct.

Which transactions a cascade reaches. Draw a reads-from graph with an edge $T_i \to T_j$ when $T_j$ reads from $T_i$ and $T_i$ has not yet ended at the time of the read. When $T_i$ aborts, every transaction reachable from $T_i$ in this graph that has not committed must abort too. For $W_1(A)\, R_2(A)\, R_3(A)\, W_3(C)\, R_4(C)\, W_5(D)$, the edges are $T_1 \to T_2$, $T_1 \to T_3$ and $T_3 \to T_4$, so an abort of $T_1$ forces $T_2$, $T_3$ and $T_4$ to abort, while $T_5$, which read nothing, is unaffected. In a cascadeless schedule the graph has no edges, so an abort affects only the aborting transaction.

Link to locking. Strict two-phase locking holds exclusive locks until commit, which makes every schedule it allows strict (and conflict serializable); see Lock-Based Concurrency Control.

Example 1: not recoverable. $S_1 = R_1(A)\, W_1(A)\, R_2(A)\, C_2\, C_1$. $T_2$ reads $A$ from $T_1$ and commits first. If $T_1$ aborted instead of committing, the committed $T_2$ would hold a value that never existed. $S_1$ is conflict serializable (edge $T_1 \to T_2$ only) but not recoverable.

Example 2: recoverable, not cascadeless. $S_2 = R_1(A)\, W_1(A)\, R_2(A)\, C_1\, C_2$. $T_1$ commits before $T_2$, so it is recoverable; $R_2(A)$ is a dirty read, so it is not cascadeless.

Example 3: cascadeless, not strict. $S_3 = R_1(A)\, W_1(A)\, W_2(A)\, C_1\, C_2$. Nobody reads uncommitted data, so it is cascadeless (and recoverable); $W_2(A)$ overwrites an uncommitted write, so it is not strict.

Example 4: strict. $S_4 = R_2(B)\, W_1(A)\, C_1\, R_2(A)\, W_2(A)\, C_2$. Item $A$ is touched by $T_2$ only after $C_1$. Strict, hence cascadeless and recoverable, though not serial.

Example 5: cascading rollback. $S_5 = W_1(A)\, R_2(A)\, W_2(B)\, R_3(B)\, A_1$. $T_2$ read $A$ from $T_1$, and $T_3$ read $B$ from $T_2$. When $T_1$ aborts, $T_2$ must abort, and then $T_3$ must abort. The schedule is recoverable (nobody has committed) but not cascadeless.

Example 6: independence from serializability.

Example 7: placing commits. The operations $W_1(A)\, R_2(A)\, W_2(B)\, R_3(B)$ are followed by the three commits in some order. $T_2$ reads from $T_1$ and $T_3$ reads from $T_2$, so recoverability needs $C_1$ before $C_2$ and $C_2$ before $C_3$: of the $3! = 6$ commit orders only $C_1\, C_2\, C_3$ gives a recoverable schedule. No commit order makes it cascadeless, because the dirty reads have already happened before any commit.

Example 8: a read from a transaction that aborts. $S_8 = W_1(A)\, R_2(A)\, A_1\, C_2$. $T_2$ read a value written by $T_1$, and $T_1$ aborted, yet $T_2$ commits: not recoverable. A recoverable system must abort $T_2$ when $T_1$ aborts, giving $W_1(A)\, R_2(A)\, A_1\, A_2$, which is recoverable.

Summary of the examples.

Making a schedule safer. A non-recoverable schedule becomes recoverable by delaying the reader's commit until the writer commits (Example 1 with $C_1$ moved before $C_2$). It becomes cascadeless only by delaying the read itself until the writer commits, which is what holding exclusive locks to commit achieves.

Related material. A schedule is rigorous if no transaction may perform any operation that conflicts with an operation of an uncommitted transaction, including overwriting an item that an uncommitted transaction has only read. Rigorous two-phase locking, which holds all locks to commit, produces such schedules; the commit order is then also a valid serialization order.

Common misconceptions.