Log-Based Recovery Techniques in DBMS: WAL, UNDO/REDO and a Worked Crash Example

At crash time, a durable log answers three separate questions: which transactions committed, which updates may already be on disk, and which committed pages may still be missing. Atomicity and durability follow from the order of log records and page writes. Classify each transaction first; then install exact before- and after-images and verify the recovered values.

System crash scope: what survives and what recovery protects

A transaction failure affects one transaction through an error or explicit abort. A system crash loses volatile memory but leaves durable storage and its log available. A media failure damages durable storage, so recovery also needs a backup or replica plus archived logs. Assume a system crash here: buffer contents vanish, while the durable log and database pages survive.

Recovery supports ACID in two precise ways. UNDO protects atomicity by removing surviving effects of transactions that did not commit. REDO protects durability by restoring committed effects missing from database pages. Transactions and constraints enforce consistency; recovery restores the stored state to committed effects. For the broad recovery map, including failure types, shadow paging, a checkpointed example and ARIES context, use Database Recovery in DBMS: Log-Based Recovery, Checkpoints, and a Fully Worked Crash Example. Physical WAL adds a narrower task: infer disk possibilities from steal and no-force, classify winners and losers, then apply before- and after-images. CS Fundamentals for Exams & Placements is the wider subject route.

Physical log records and the two WAL ordering rules

A physical log may contain <START T1>, update <T1, A, old=1000, new=900>, <COMMIT T1> or <ABORT T1>, and a completed checkpoint. Increasing log sequence numbers, or LSNs, fix the durable order. An update's old image supports UNDO, while its new image supports REDO.

Write-ahead logging, or WAL, imposes two ordering guarantees:

1. Before a dirty database page is written, the log record describing its change must be durable.

2. Before commit is acknowledged, all log records for that transaction, including its commit record, must be durable.

WAL orders log writes before page writes. It does not force every changed page at commit. A steal policy permits a page with an uncommitted update to reach disk, creating a possible need for UNDO. A no-force policy permits commit before all changed pages reach disk, creating a possible need for REDO.

Buffer policies: derive UNDO and REDO from disk possibilities

The name matters less than what may be present or absent on disk.

Deferred update is the textbook NO-UNDO/REDO case. Its log records still appear as work occurs; only page updates are deferred. With immediate update, steal and no-force give the textbook UNDO/REDO case.

A question may specify force, no-force, steal, or no-steal without naming either technique. Derive the answer from disk possibilities. If uncommitted data may be on disk, consider UNDO. If committed data may still be missing from disk, consider REDO.

Physical WAL trace: classify T1 and T2, then repair exact values

At the completed checkpoint LSN 05, the active set is empty and the durable database holds A=1000, B=2000, and C=500. The system uses immediate update with steal and no-force, and it obeys WAL. Its durable log is exactly:

LSN 10 <START T1>
LSN 20 <T1, A, old=1000, new=900>
LSN 30 <T1, B, old=2000, new=2100>
LSN 40 <COMMIT T1>
LSN 50 <START T2>
LSN 60 <T2, C, old=500, new=550>
CRASH

At the crash, disk holds A=900, B=2000, and C=550. This mixed state is legal. The A page and T2's uncommitted C page were stolen to disk. T1's B page was not forced, even after T1 committed. In every case, the relevant update log record became durable before the page write.

T1 is a winner because its commit record is durable. T2 is a loser because it has no commit or abort record.

Now REDO T1's after-images in forward log order:

1. At LSN 20, assign A:=900. A is already 900, so this idempotent assignment changes nothing.

2. At LSN 30, assign B:=2100. This restores T1's committed update that was missing from disk.

Then UNDO T2 in reverse log order. At LSN 60, assign the old image C:=500, then mark T2 aborted in this simplified model.

The final recovered state is A=900, B=2100, C=500. Check the arithmetic: T1 moves 100 from A to B, so 900 + 2100 = 3000, matching 1000 + 2000 = 3000. T2 leaves no effect, so C returns from 550 to 500. Do not subtract 100 from A again during REDO. Physical REDO installs new=900; it does not repeat the business calculation.

Completed checkpoints versus an ARIES restart

The completed checkpoint at LSN 05 bounds the recovery starting point, avoiding a scan of irrelevant older history. It is neither a backup nor a substitute for the log, and it does not commit later transactions.

The active set is {}, so T1 and T2 began later. A listed active transaction is not automatically a loser; later records may show a commit before the crash.

For this conventional, non-overlapping log, recovery has three steps: classify, REDO T1's committed after-images, then UNDO T2's before-image. No data item is updated by both transactions, so the two repair passes do not interfere. ARIES follows a different rule: its REDO phase repeats history, including loser updates, before CLR-guided UNDO. Use Advanced Recovery Algorithms in DBMS: ARIES Worked Step by Step for transaction-table and dirty-page-table reconstruction, pageLSN tests and restartable undo.

Physical recovery traps: direction, idempotence and disk state

Keep these distinctions exact:

• A durable commit record does not mean every changed data page is already on disk.

• A transaction without a commit record is a loser, even if its new value reached disk.

• WAL means log before page, not page before log.

• A checkpoint does not commit transactions that are active at that point.

• Deferred update is normally NO-UNDO/REDO, not automatically UNDO/REDO.

Always reason from what disk may contain.

UNDO direction also matters. If T2 logged C:500->550 and then C:550->530, reverse UNDO restores 530->550 and then 550->500. A forward pass can stop at the wrong intermediate value. Idempotence matters if recovery itself crashes: repeating the assignment B:=2100 still leaves B at 2100, not 2200.

Exam variants: alter one log fact at a time

Questions may ask you to identify winners and losers, compute final values, choose UNDO, REDO, both, or neither from buffer policies, find a WAL violation, locate the useful checkpoint, or distinguish a commit record from a flushed page.

For this log, check your answer first:

• Winners: {T1}

• Losers: {T2}

• REDO assignments: A:=900, then B:=2100

• UNDO assignment: C:=500

• Final state: (900, 2100, 500)

Two counterfactuals test whether the method is clear. If B were already 2100 at the crash, REDO would leave it at 2100. If the crash occurred just before LSN 40 <COMMIT T1> and before T2 began, T1 would be a loser. Reverse UNDO would restore B to 2000 and A to 1000. Once you can classify these variants without guessing, continue with DBMS Transaction MCQs: 12 Solved (ACID, Locking) for exam-style transaction practice.

Physical WAL recovery: the short version and next trace

• Logs preserve ordered evidence.

• WAL makes evidence durable before page writes.

• Winners may need REDO.

• Losers may need UNDO.

• Checkpoints reduce scanning without changing commit status.

For broad core-CS study including DBMS, use Zero to Hero.

Repeat the trace twice: first with B already at 2100 when the crash occurs, then with the crash before T1 commits. The first case keeps (900, 2100, 500); the second restores (1000, 2000, 500). Explain each result using disk state, commit status and log direction.