Understanding Transaction Recovery

Question

In the following reference, there is an algorithm outlining a transaction recovery algorithm using redo and undo. The algorithm is as follows:

UNDO and REDO: lists of transactions

UNDO = all transactions running at the last checkpoint
REDO = empty

For each entry in the log, starting at the last checkpoint
  If a BEGIN TRANSACTION entry is found for T
    Add T to UNDO
  If a COMMIT entry is found for T
    Move T from UNDO to REDO

It then gives the example:

but this is clearly wrong?? Since T2 has been committed, T must be in the REDO list. Am I missing something?

Answer 1

If you look throught the slides from beginning to end you will find that the explanation is pretty accurate.

1. The recovery of the database starts.

The depicted slide is showing you the situation as it is at the time when the vertical axis is at the checkpoint.

2. At that time T2 and T3 are put into the UNDO queue.

3. Moving forward (in the reference) the examined time (vertical axis) moves forward and reaches the BEGIN of T4. The transaction T4 is put into the UNDO queue.

4. Moving forward (in the reference) the examined time (vertical axis) moves forward and reaches the BEGIN of T5. The transaction T5 is put into the UNDO queue.

You now have all four transactions T1, T2, T3, T4 in the UNDO queue.

5. Moving further forward (in the reference) the examined time (vertical axis) moves forward and reaches the END of T2. The transaction T2 is put into the REDO queue.

6. Moving forward (in the reference) the examined time (vertical axis) moves forward and reaches the END of T4. The transaction T4 is put into the REDO queue.

The transactions T3 and T5 are in the UNDO queue.
The transactions T2 and T4 are in the REDO queue.

Moving even further forward (in the reference) the examined time (vertical axis) moves forward and reaches the Failure.

T3 and T5 are UNDO-ne and T2 and T4 are REDO-ne (or reapplied).

The database is now in a consistent state.