Recoverable, cascadeless and strict schedules

Why it exists

Serializability assumes every transaction commits. In real systems a transaction can abort (an error, a deadlock victim, a failed constraint). If another transaction has already used its values, that transaction depends on something that never happened. A schedule must therefore be arranged so that aborting one transaction can be done without undoing committed work. This page defines the classes of schedules that allow this, from weak to strong.

Prerequisites

You need schedules, conflicts and serializability (schedules and serializability).

Precise definitions

$T_j$ reads from $T_i$ (with $i \ne j$) if $T_j$ reads an item $X$ whose latest preceding write was made by $T_i$ (and $T_i$ has not aborted before the read: its write would have been undone).

• A schedule is recoverable if whenever $T_j$ reads from $T_i$ and $T_j$ commits, then $T_i$ commits before $T_j$ commits. (If $T_i$ later aborted, $T_j$ would have committed a result built on a value that vanished, and a commit cannot be undone.)
• A schedule avoids cascading aborts (is cascadeless, ACA) if every transaction reads only values written by committed transactions: $c_i$ comes before $r_j(X)$ whenever $T_j$ reads $X$ from $T_i$. Then no abort ever forces another transaction to abort.
• A schedule is strict if no transaction reads or overwrites an item written by another transaction until that transaction has committed or aborted.
• A schedule is rigorous if it is strict and also no transaction writes an item that an uncommitted transaction has read: in no conflict does the later operation come before the other transaction has finished.

The inclusions: $\text{rigorous} \subset \text{strict} \subset \text{cascadeless} \subset \text{recoverable} \subset \text{all schedules}$. Each class forbids more than the one before; the inclusions are proper (the examples below separate them).

Independence from serializability. A schedule can be conflict serializable and not recoverable, or recoverable and not conflict serializable. Rigorous schedules are conflict serializable (every conflicting pair is separated by the end of the first transaction, so the schedule is equivalent to the order of commits).

How it works

The classes on examples

Reading the rows (each ends with the commits shown):

• $w_1(A)\ r_2(A)\ c_2\ c_1$: $T_2$ read from $T_1$ and committed first. Not recoverable: if $T_1$ aborted after $c_2$, the committed $T_2$ would have used a vanished value.
• $w_1(A)\ r_2(A)\ c_1\ c_2$: recoverable (the commit order is right), but $T_2$ read uncommitted data, so an abort of $T_1$ before $c_1$ would force $T_2$ to abort too: not cascadeless.
• $w_1(A)\ w_2(A)\ c_1\ c_2$: nobody reads uncommitted data, so cascadeless, but $T_2$ overwrote an uncommitted write: not strict.
• $r_1(A)\ w_2(A)\ c_2\ c_1$: strict (nothing written by an uncommitted transaction is touched; $T_2$ overwrites an item that $T_1$ only read), but not rigorous.
• The serial schedule is rigorous.
• The last row (the view serializable schedule of the previous page) is recoverable and cascadeless but neither strict nor conflict serializable: the two properties are independent.

Cascading rollback

$T_2$ read an uncommitted value of $T_1$, $T_3$ read an uncommitted value of $T_2$. When $T_1$ aborts, both $T_2$ and $T_3$ have used values that never existed and must abort: a cascading rollback (the abort spreads along the reads-from relation, transitively). Cascadeless schedules make this impossible, at the price of making readers wait for commits.

Why strictness matters for undo

If $T_2$ overwrites an uncommitted write of $T_1$ and $T_1$ then aborts, restoring $T_1$'s before-image ($100$) destroys the value $130$ that $T_2$ wrote and committed. In a strict schedule no transaction touches an item written by an active transaction, so undoing a transaction simply restores the before-images of its own writes. That is why practical systems produce strict (usually rigorous) schedules.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Locking protocols produce these classes: strict two-phase locking gives strict schedules, rigorous two-phase locking rigorous ones (two-phase locking). Undo and redo with a log are the subject of log-based recovery.

PYQs

A schedule of three database transactions T1,T2, andT3 is
shown. Ri(A) and Wi (A) denote read and write of data
item A by transaction Ti, i=1,2,3 The transaction T1 aborts
at the end. Which other transaction(s) will be required to
be rolled back?
R1(X); W1(Y); R2(X); R2(Y); R3(Y) ;ABORT(T1);

Let S be the following schedule of operations of three
transactions T1, T2 and T3 in a relational database system:

R2(Y), R1(X), R3(Z), R1(Y), W1(X), R2(Z), W2(Y),
R3(X), W3(Z)

Consider the statements P and Q below:

P: S is conflict-serializable.

Q: If T3 commits before T1 finishes, then S is recoverable.

Which one of the following choices is correct?

Consider the following two statements about database
transaction schedules:

I. Strict two-phase locking protocol generates conflict
serializable schedules that are also recoverable.

II. Timestamp-ordering concurrency control protocol with
Thomas write rule can generate view serializable schedules
that are not conflict serializable.

Which of the above statements is/are TRUE?

Consider the following database schedule with two
transactions, T1 and T2.

S – r2(X); r1(X); r2(Y); w1(X); r1(Y); w2(X); a1; a2

Where ri(Z) denotes a read operation by transaction Ti
on a variable Z, wi(Z) denotes a write operation by Ti on
a variable Z and ai denotes an abort by transaction Ti.

Which one of the following statements about the above
schedule is TRUE?

Consider the partial Schedule S involving two transactions
T1 and T2. Only the read and the write operations have
been shown. The read operation on data item P is denoted
by read(P) and write operation on data item P is denoted by
write(P).

Schedule S

Time Instance
Transaction ID

T1
T2
1
read(A)

2
write (A)

3

read(C)
4

write (C)
5

read(B)
6

write (B)
7

read(A)
8

commit
9
read(B)

Suppose that the transaction T1 fails immediately after
time instance 9. Which of the following statements is
correct?

Consider the following schedule S of transactions T1, T2,
T3, T4:

T1
T3
T3
T.
Writes
(X)
Commit

Writes
(Y)
Reads (Z)
Commit

Reads
(X)
Reads
(Y)
Commit

Which one of the following statements is CORRECT?

Self-check

Revision card

References