CSE Roadmap

Core tier · about 2 hours · 5 parts

Part 5 of 5 · 4 min read

Exercises

Easy

Easy 1: Name what redo does (15 minutes)

State, in one sentence, what redo does during crash recovery.

Done when: reapplying a logged change for a transaction that had already committed is correctly described.

Hint

It reapplies a logged change to the data page for a transaction that had already committed before the crash.

Easy 2: Name what undo does (15 minutes)

State, in one sentence, what undo does during crash recovery.

Done when: reverting a logged change for a transaction that had not yet committed is correctly described.

Hint

It reverts a logged change, using its recorded old value, for a transaction that had not yet committed before the crash.

Easy 3: Name which ACID property each operation satisfies (15 minutes)

State which ACID property redo satisfies, and which ACID property undo satisfies.

Done when: durability for redo and atomicity for undo are both correctly named.

Hint

Redo satisfies durability; undo satisfies atomicity.

Medium

Medium 1: Decide whether to redo or undo a specific entry (25 minutes)

A crash occurs. A log entry exists for a transaction that had already issued COMMIT before the crash. Determine whether this entry's change should be redone or undone during recovery.

Done when: redo is correctly chosen, since the transaction had already committed before the crash.

Hint

Redo, since the transaction had already committed before the crash occurred.

Medium 2: Decide whether to redo or undo a second entry (25 minutes)

A crash occurs. A log entry exists for a transaction that was still in progress, with no COMMIT issued, at the moment of the crash. Determine whether this entry's change should be redone or undone.

Done when: undo is correctly chosen, since the transaction never reached commit before the crash.

Hint

Undo, since the transaction never reached commit before the crash occurred.

Medium 3: Explain why redoing an already-flushed page causes no harm (30 minutes)

Explain why redoing a committed transaction's change, even if its data page had actually already been flushed before the crash, does not cause any incorrect result.

Done when: the explanation correctly notes reapplying the same already-correct change to a page that already reflects it simply leaves the page unchanged, so redoing it regardless of prior flush status causes no harm.

Hint

Reapplying an already-correct value to a page that already holds it simply leaves the page unchanged, so there is no harm in redoing it regardless of whether it had already been flushed.

Hard

Hard 1: Explain why undo needs the log's old value specifically (30 minutes)

Explain why undo specifically needs the old value recorded in a log entry, rather than simply being able to delete the row or leave the page as it currently is.

Done when: the explanation correctly notes the in-memory or on-disk page may already reflect the uncommitted transaction's new value, so reverting correctly requires restoring the specific prior value the log entry recorded, not just erasing or ignoring the current state.

Hint

The current page may already reflect the uncommitted transaction's new, incorrect value, so correctly reverting requires restoring the specific old value the log recorded, not merely deleting the row or leaving the page in its current, possibly-wrong state.

Hard 2: Trace a full recovery scenario with both redo and undo (35 minutes)

A crash occurs with two log entries present: one from a committed transaction A, and one from an uncommitted transaction B. Trace what recovery does with each entry, in terms of redo and undo.

Done when: the trace correctly applies redo to transaction A's entry, reapplying its change to ensure durability, and undo to transaction B's entry, reverting its change to preserve atomicity.

Hint

Transaction A's entry is redone, reapplying its change to guarantee durability for the committed transaction; transaction B's entry is undone, reverting its change to preserve atomicity for the transaction that never committed.

Hard 3: Explain why recovery must process every log entry, not just the most recent (40 minutes)

Explain why crash recovery needs to examine every relevant log entry since the last point of certainty, rather than only the single most recent entry for each data item.

Done when: the explanation correctly notes that multiple transactions' changes to different items, and even multiple changes to the same item, may need to be redone or undone individually and in the correct order to reconstruct the exact correct final state, which only examining the single most recent entry could not reliably reproduce.

Hint

Multiple transactions, and even multiple changes to the same item, may each need their own correct redo or undo applied in the right order to reach the exact correct final state, something that examining only the single most recent entry per item could not reliably reconstruct.