Recoverable, Cascadeless and Strict Schedules in DBMS

5
0

Introduction

Transactions do not always complete successfully. An operation may fail, or an application may cancel its work. When transactions overlap, a failure becomes more complicated if another transaction has already used the unfinished changes.

Recoverable, cascadeless, and strict schedules place progressively stronger restrictions on these interactions. Their purpose is to make recovery safer and prevent one transaction’s failure from unnecessarily affecting other transactions.

Example Table and Schedule Notation

A schedule is the order in which operations from different transactions execute, while preserving each transaction’s internal operation order.

The examples use an Account table containing each account’s identifier, holder name, and balance.

Account: initial data

AccountID

HolderName

Balance

1

Asha

1000.00

2

Ravi

500.00

AccountID is the primary key. Each conceptual example starts with this initial data.

In the schedules:

  • R1(A): Transaction T1 reads Asha’s balance.

  • W1(A): Transaction T1 writes Asha’s balance.

  • C1: T1 commits.

  • Abort1: T1 aborts and its changes are rolled back.

The number identifies the transaction, and A represents Asha’s balance. These are schedule symbols, not SQL commands.

The theoretical examples use the classical single-version model, where each data item has one current value. The SQL example later explains how modern database behavior relates to this model.

Why Commit Order Matters

Suppose T1 changes Asha’s balance from 1000.00 to 800.00 without committing. T2 then reads 800.00.

This is a dirty read because T2 has read another transaction’s uncommitted value. T2 now depends on a change that T1 might cancel.

Consider this schedule:

W1(A), R2(A), C2, Abort1

Step

Action

Consequence

1

T1 writes 800.00 without committing.

The new balance is unfinished work.

2

T2 reads 800.00.

T2 depends on T1’s change.

3

T2 commits.

T2 finishes before its dependency is confirmed.

4

T1 aborts.

The balance returns to 1000.00.

This schedule is non-recoverable: T2 has already committed after reading a value from a transaction that later aborted.

An ordinary rollback cannot undo an already committed transaction. Correcting its effects would require additional corrective work rather than normal transaction rollback.

Recoverable Schedules and Cascading Rollback

A schedule is recoverable if every transaction that reads another transaction’s write commits only after that writer commits.

If T2 reads a value written by T1, the required commit order is T1 first, then T2.

W1(A), R2(A), C1, C2

Step

T1

T2

1

Writes Asha’s balance as 800.00.

2

Reads 800.00 before T1 commits.

3

Commits.

4

Commits.

Outcome:

AccountID

HolderName

Balance

1

Asha

800.00

2

Ravi

500.00

The schedule is recoverable because T2 commits after T1. However, it still contains a dirty read.

If T1 aborts instead, T2 must also abort because its work depended on T1’s cancelled change:

W1(A), R2(A), Abort1, Abort2

This is a cascading rollback: one transaction’s rollback forces a dependent transaction to roll back. The effect can spread further if other transactions have read the dependent transaction’s uncommitted writes.

Recoverability therefore protects commit order, but does not prevent cascading rollback.

Why rollbacks cascade

Why rollbacks cascade

Cascadeless Schedules

A schedule is cascadeless if transactions read values written by other transactions only after those writers commit.

The restriction moves earlier: instead of merely delaying T2’s commit, it prevents T2 from reading T1’s uncommitted value.

W1(A), C1, R2(A), C2

T2 reads 800.00 only after it becomes committed data. If T1 had aborted before committing, T2 would not have depended on that cancelled value.

Cascadeless schedules prevent dirty reads and the cascading rollbacks caused by them. They do not prevent transactions from aborting for unrelated reasons.

Cascadeless does not necessarily mean strict. Consider:

W1(A), W2(A), C1, C2

There are no reads, so the schedule does not violate the cascadeless reading rule. However, T2 overwrites A while T1’s write is still uncommitted. This is a dirty write, which strict schedules prohibit.

This is a theoretical distinction, not an execution that MySQL or PostgreSQL would normally permit for conflicting updates to the same row.

Strict Schedules

A schedule is strict if, after a transaction writes a data item, no other transaction may read or write that item until the writer commits or aborts.

Strictness prevents both:

  • Dirty reads: Reading another transaction’s uncommitted value.

  • Dirty writes: Overwriting an item written by another transaction that has not yet committed or aborted.

For example:

Step

T1

T2

1

Writes Asha’s balance as 800.00.

2

Remains uncommitted.

Any requested read or write of A must wait.

3

Commits.

4

Reads 800.00.

5

Writes 850.00 and commits.

Expected final table:

AccountID

HolderName

Balance

1

Asha

850.00

2

Ravi

500.00

If T1 aborts instead, its balance change is undone before T2 accesses A. T2 can then read the restored 1000.00.

Strict schedules simplify recovery because another transaction has neither consumed nor overwritten the unfinished value. Strictness does not require the entire database to execute transactions one at a time: work on unrelated items can still overlap.

Strict schedules : wait before access

Strict schedules : wait before access

The relationship is:

Strict schedules are a subset of cascadeless schedules, which are a subset of recoverable schedules.

Property

Recoverable

Cascadeless

Strict

Dependent transaction commits after the writer commits

Required

Guaranteed by the read rule

Guaranteed by the access rule

Dirty reads

May occur

Prevented

Prevented

Dirty writes

Not prohibited by this property alone

Not prohibited by this property alone

Prevented

Cascading rollback caused by dirty reads

May occur

Prevented

Prevented

Main restriction

Commit order

When another transaction’s value may be read

When a written item may be read or overwritten

The reverse implications do not always hold. A recoverable schedule may contain dirty reads, and a cascadeless schedule may contain dirty writes.

These are recovery properties, not substitutes for serializability. Serializability asks whether an interleaved execution is equivalent to a serial execution. Strictness alone does not guarantee that equivalence.

Three schedule rules

Three schedule rules

A Compact SQL Example

Objective: Make a second transaction wait before reading an account being updated, then let it continue after the first transaction commits.

The example uses two separate database connections:

  • Session A: Deducts 200 from Asha’s balance.

  • Session B: Reads the balance with a lock, then adds 50.

Run the numbered steps in order. Session A remains open while Session B requests its locking read.

1. Create the Initial Data

Consider the following queries to create and populate the account table.

CREATE TABLE Account (
AccountID INT PRIMARY KEY,
HolderName VARCHAR(50) NOT NULL,
Balance DECIMAL(10, 2) NOT NULL
);
START TRANSACTION;
INSERT INTO Account (AccountID, HolderName, Balance)
VALUES
(1, 'Asha', 1000.00),
(2, 'Ravi', 500.00);
COMMIT;

Initial table:

AccountID

HolderName

Balance

1

Asha

1000.00

2

Ravi

500.00

2. Session A: Update Without Committing Yet

Consider the following queries to deduct 200 while keeping the transaction open.

SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
START TRANSACTION;
UPDATE Account
SET Balance = Balance - 200
WHERE AccountID = 1;
-- Keep the transaction open.

Session A has changed Asha’s balance to 800.00, but the change is not committed. Its update holds a lock on the row.

3. Session B: Request a Locking Read

Consider the following queries to read and lock Asha’s account before changing it.

SET TRANSACTION ISOLATION LEVEL READ COMMITTED;
START TRANSACTION;
SELECT AccountID, Balance
FROM Account
WHERE AccountID = 1
FOR UPDATE;

FOR UPDATE requests a row lock for a later update. Because Session A already holds a conflicting lock, this query waits. It does not immediately return a result table.

4. Session A: Commit, Then Finish Session B

Consider the following command to commit Session A’s deduction and release its lock.

COMMIT;

Session B’s waiting query can now complete.

Result returned to Session B:

AccountID

Balance

1

800.00

Consider the following queries to add 50 in Session B and display the final balances.

UPDATE Account
SET Balance = Balance + 50
WHERE AccountID = 1;
COMMIT;
SELECT AccountID, HolderName, Balance
FROM Account
ORDER BY AccountID;

Expected result:

AccountID

HolderName

Balance

1

Asha

850.00

2

Ravi

500.00

The balance is 1000 - 200 + 50 = 850. Session B accessed the updated row only after Session A committed.

If Session A used ROLLBACK instead of COMMIT in step 4, Session B’s waiting read would return 1000.00. Its subsequent addition would produce 1050.00.

This example deliberately uses a locking read. An ordinary SELECT at READ COMMITTED in MySQL or PostgreSQL can read an older committed version instead of waiting. Reading that committed version is not a dirty read, and it differs from the classical single-version model used in the theoretical schedules.

Summary

Recoverable schedules require a transaction to commit only after the transactions whose writes it read have committed. Cascadeless schedules go further by preventing reads of uncommitted values, avoiding cascading rollback caused by those reads.

Strict schedules also prevent overwriting an item while another transaction’s write remains uncommitted. Every strict schedule is cascadeless and recoverable, but recovery safety and serializability remain separate properties that a database must consider.

CS Core

Read Similar Blogs

Comments0