Advanced Recovery Algorithms in DBMS: ARIES Worked Step by Step

A crash does not neatly separate committed from uncommitted work. Some uncommitted changes may already be on disk, while committed changes may survive only in a lost buffer. Using write-ahead logging and ARIES, recovery rebuilds the transaction table and dirty page table before deciding exactly what to redo and undo for one crash. Each decision will come directly from the log.

Why advanced recovery algorithms are needed

Recovery must answer two independent questions: which transactions committed, and which page versions reached disk? With steal, the buffer manager may write an uncommitted dirty page, so recovery needs UNDO. With no-force, commit need not flush every changed page, so recovery needs REDO. A steal/no-force system needs both.

Write-ahead logging (WAL) imposes two precise rules. An update log record must reach stable storage before its changed page is written. A transaction's commit record must be forced before success is reported. WAL orders log persistence; it does not force every data page at commit. For conventional WAL, checkpoints, and winner/loser classification, start with Database Recovery in DBMS: Log-Based Recovery, Checkpoints, and a Fully Worked Crash Example. ARIES goes further through fuzzy-checkpoint TT/DPT reconstruction, pageLSN redo tests, CLRs and restartable undo. Use CS Fundamentals for Exams & Placements as the wider subject route.

From basic recovery to ARIES data structures

Deferred update avoids writing uncommitted changes and mainly needs REDO. Immediate update may need UNDO and REDO. Shadow paging switches page-table roots, but copying, fragmentation and concurrency introduce trade-offs. ARIES supports steal/no-force through WAL, fuzzy checkpoints, repeating history and logged undo. Real databases need not reproduce every ARIES internal identically.

The analysis relies on five fields. An LSN orders log records. prevLSN links one transaction's records backwards. A page's pageLSN is the latest update reflected on that page. A dirty page table (DPT) entry's recLSN is the earliest record that may need redo for that page. The transaction table (TT) stores status and lastLSN.

A compensation log record (CLR) logs an undo's effect. It is redo-only and carries undoNextLSN, so recovery can resume without reversing completed undo. A fuzzy checkpoint snapshots TT and DPT while work continues. It supplies a starting point, not proof that dirty pages were flushed.

ARIES worked crash setup

Initially, stable storage has P1: A=10, pageLSN=0, P2: B=20, pageLSN=0 and P3: C=30, pageLSN=0. The stable log at the crash is:

After the checkpoint, WAL permits flushing P1 as A=15, pageLSN=10. Updates 20, 60 and 70 are not flushed. Disk at the crash therefore holds P1 A=15 pageLSN=10, P2 B=20 pageLSN=0, P3 C=30 pageLSN=0; buffer values P1=18, P2=27, P3=24 vanish. T1 committed and ended. T2 was running and T3 was aborting, so recovery must preserve T1's change and finish at A=15, B=20, C=30.

ARIES analysis phase: tables and losers

The master record points to BEGIN_CHECKPOINT at LSN 30. Merge the LSN 40 snapshot, then scan forward. LSN 50 makes T1 COMMITTING with lastLSN=50. LSN 60 adds T3 as RUNNING and P3 recLSN=60. LSN 70 sets T2 lastLSN=70; P1 conservatively keeps recLSN=10. LSN 80 removes T1 after END. LSN 90 makes T3 ABORTING with lastLSN=90.

Before cleanup, TT is {T2 RUNNING lastLSN 70, T3 ABORTING lastLSN 90} and DPT is {P1 recLSN 10, P2 recLSN 20, P3 recLSN 60}. P1 retains 10 because ordinary page flushes do not appear as records in this analysis scan. T1 is complete; T2 and T3 are losers. Recovery appends LSN 100: T2 ABORT, prevLSN=70, making T2 recovery-aborting with lastLSN=100.

ARIES redo phase: repeat history

Redo starts at min(recLSN)=10. For an update, ARIES checks that its page is in the DPT, its LSN is not earlier than that page's recLSN, and the disk pageLSN is smaller. Only then does it reapply the after-image and advance pageLSN.

• Skip LSN 10: P1 already has pageLSN=10.

• Redo LSN 20: P2 has 0<20, giving B=27, pageLSN=20.

• Redo LSN 60: P3 has 0<60, giving C=24, pageLSN=60.

• Redo LSN 70: P1 has 10<70, giving A=18, pageLSN=70.

Non-page records do not change these values. The deliberate post-redo state is A=18, B=27, C=24: ARIES repeats logged history before removing loser effects. Redo includes loser updates and, after a recovery crash, any CLRs that require reapplication.

ARIES undo phase: CLRs and a second crash

Start with the losers' latest undoable records, T2=70 and T3=60, and process the largest LSN first.

1. Undo T2's LSN 70. Restore P1 A=15, then write CLR 110 with prevLSN=100, undoNextLSN=20 and pageLSN=110.

2. Undo T3's LSN 60. Restore P3 C=30, write CLR 120 with prevLSN=90 and undoNextLSN=null, then write T3 END at LSN 130.

3. Undo T2's LSN 20. Restore P2 B=20, write CLR 140 with prevLSN=110 and undoNextLSN=null, then write T2 END at LSN 150.

The recovered logical state is exactly P1 A=15, P2 B=20, P3 C=30.

Now suppose another crash occurs after CLR 110 but before CLR 120. The next redo pass reapplies CLR 110 if needed, preserving A=15. Undo resumes T2 at LSN 20 through undoNextLSN and still processes T3 at LSN 60. It never undoes CLR 110. Logged undo therefore makes recovery restartable.

Recovery algorithm traps and exam checks

Keep these distinctions clean. WAL does not immediately flush data pages. A checkpoint does not put every dirty page on disk. Analysis reconstructs metadata, not values. Redo is not winner-only. A sufficiently high pageLSN makes an older redo unnecessary. recLSN belongs to a DPT page entry, not a transaction. A CLR is never undone.

For this example, the answer-first checks are:

• Redo begins at LSN 10.

• T2 and T3 are the losers.

• LSN 10 is skipped because disk P1 already has pageLSN=10.

• Temporary post-redo A is 18.

• Final A is 15 because undo removes T2's LSN 70 while T1's LSN 10 remains.

• Steal creates UNDO; no-force creates REDO.

Questions may ask you to select actions from buffer policies, reconstruct TT and DPT, find the redo start, decide redo or skip, classify winners and losers, follow prevLSN and undoNextLSN, or calculate final page values. Continue with DBMS Transaction MCQs: 12 Solved (ACID, Locking).

The short version and next step

WAL makes page writes reconstructable. Analysis rebuilds TT and DPT, redo repeats history from the smallest recLSN, undo removes loser effects, and CLRs make undo restartable. Here redo reaches 18,27,24; undo finishes at 15,20,30, preserving only T1's committed change.

For a broader semester-oriented path, use Zero to Hero - Complete CS Course. For placement-focused revision, use CS Fundamentals for Placements by Sanchit Sir. Rebuild both tables, justify all four redo decisions, reproduce CLRs 110, 120 and 140, and explain how undo resumes after a second crash.