Characterizing Schedules Based on Recoverability

When transactions execute concurrently, their operations are interleaved in a schedule.

Some schedules allow the system to recover easily after failures, while others make recovery difficult or impossible.

Therefore, schedules are classified based on recoverability to ensure that:

• The durability property of transactions is preserved

• Committed transactions never need to be rolled back

• Recovery after failures is safe and manageable

These classifications do not describe the recovery algorithm, but instead define the types of schedules that allow correct recovery.

---

1. Recoverable Schedules

Definition

A schedule is recoverable if:

A transaction T commits only after all transactions whose data it has read have committed.

In other words:

If T2 reads a value written by T1, then:

T1 must commit before T2 commits

This ensures that if T1 aborts, T2 will not have committed yet, so T2 can also be rolled back safely.

---

Why Recoverability is Important

If a transaction commits using data written by another transaction that later aborts, the committed transaction becomes invalid, and the database becomes inconsistent.

Recoverable schedules prevent this situation.

---

Example: Recoverable Schedule

Schedule:

Sa′: r1(X); r2(X); w1(X); r1(Y); w2(X); c2; w1(Y); c1;

Explanation:

1. T1 writes X

2. T2 reads X

3. T2 commits after T1 writes but before T1 commits

Even though this schedule suffers from a lost update problem, it is still recoverable because:

• T2 did not commit before reading an uncommitted value that later gets invalidated.

Such problems are handled by serializability theory, not recoverability.

---

2. Nonrecoverable Schedules

A schedule becomes nonrecoverable if:

A transaction commits before the transaction whose value it read commits.

---

Example: Nonrecoverable Schedule

Sc: r1(X); w1(X); r2(X); r1(Y); w2(X); c2; a1;

Explanation:

1. T1 writes X

2. T2 reads X

3. T2 commits

4. Later T1 aborts

Now the value read by T2 is invalid, but T2 has already committed.

The system would need to rollback a committed transaction, which violates the durability property.

Therefore:

Sc is a nonrecoverable schedule

Such schedules must not be allowed by a DBMS.

---

3. Correcting the Problem

To make the schedule recoverable, T2 must delay its commit until T1 commits.

Example:

Sd: r1(X); w1(X); r2(X); r1(Y); w2(X); w1(Y); c1; c2;

Here:

• T1 commits first

• T2 commits later

So if T1 aborts, T2 can also abort safely before committing.

Thus:

Sd is a recoverable schedule

---

4. Cascading Rollback (Cascading Abort)

Even in recoverable schedules, another problem may occur called cascading rollback.

Definition

A cascading rollback occurs when:

A transaction must be rolled back because it read data from another transaction that later aborts.

---

Example

Se: r1(X); w1(X); r2(X); r1(Y); w2(X); w1(Y); a1; a2;

Explanation:

1. T1 writes X

2. T2 reads X

3. T1 aborts

4. Since T2 used invalid data, T2 must also abort

This causes a chain reaction of rollbacks, which is called cascading rollback.

---

Why Cascading Rollback is a Problem

It can cause:

• Many transactions to be rolled back

• Significant performance overhead

• Complex recovery procedures

Therefore, DBMS designers try to avoid cascading rollbacks.

---

5. Cascadeless Schedules

To prevent cascading rollback, we define cascadeless schedules.

Definition

A schedule is cascadeless if:

A transaction reads a data item only after the transaction that wrote it has committed.

This ensures that no transaction reads uncommitted data.

---

Example

Correct cascadeless schedule:

w1(X)
c1
r2(X)
w2(X)
c2

Here:

• T2 reads X only after T1 commits

• Therefore no cascading rollback occurs

---

Fixing Earlier Schedules

To make earlier schedules cascadeless:

r2(X)

must occur after T1 commits or aborts.

This delays T2 but ensures safe recovery.

---

6. Strict Schedules

A strict schedule is a stronger condition than cascadeless schedules.

Definition

A schedule is strict if:

A transaction cannot read or write a data item until the transaction that last wrote it has committed or aborted.

This prevents both:

• Reading uncommitted data

• Writing over uncommitted data

---

Example Problem (Non-Strict Schedule)

Sf: w1(X,5); w2(X,8); a1;

Initial value of X = 9

Steps:

1. T1 writes X = 5

2. T2 writes X = 8

3. T1 aborts

During recovery, the system restores before image = 9.

But T2 already changed X to 8, so restoring 9 overwrites valid data.

This produces incorrect results.

---

Why Strict Schedules Solve This

In strict schedules:

T2 cannot write X until T1 commits or aborts

So the situation above cannot occur.

Recovery becomes simple and safe.

---

7. Relationship Between Schedule Types

These schedules form a hierarchy.

Strict Schedules
        ⊂
Cascadeless Schedules
        ⊂
Recoverable Schedules
        ⊂
All Possible Schedules

Meaning:

• Every strict schedule is cascadeless

• Every cascadeless schedule is recoverable

• But the reverse is not always true

---

8. Why DBMS Prefer Strict Schedules

Most DBMS recovery protocols allow only strict schedules because:

• Recovery becomes simpler

• No cascading rollback occurs

• Database consistency is easier to maintain

• Undo operations become straightforward

Recovery simply restores the before image (BFIM) of data items.

---

Summary Table

Schedule Type	Property	Advantage
Recoverable	Transactions commit only after transactions they depend on commit	Prevents rollback of committed transactions
Cascadeless	Transactions read only committed data	Avoids cascading rollback
Strict	Transactions cannot read/write until previous writer commits	Simplifies recovery

---

Final Concept

Characterizing schedules based on recoverability ensures that database systems can recover correctly from failures while maintaining the durability and consistency of transactions.

For this reason, most modern DBMS enforce strict schedules, which provide the safest and simplest recovery process.