Official PYQ · 2015Set 2 · Q46Transactions and Concurrency ControlMCQ1 mark

GATE CS 2015 Set 2 Q46 — Transactions and Concurrency Control

Consider a simple checkpointing protocol and the following set of operations in the log.

(start, T4); (write, T4, y, 2, 3); (start, T1); (commit, T4); (write, T1, z, 5, 7);

(checkpoint);

(start, T2); (write, T2, x, 1, 9); (commit, T2); (start, T3); (write, T3, z, 7, 2);

If a crash happens now and the system tries to recover using both undo and redo operations, what are the contents of the undo list and the redo list?

View worked solution

Answer: A

To find the Undo and Redo lists during recovery, we analyze the state of each transaction relative to the (checkpoint) and the crash point.

Redo List: Contains transactions that committed after the last checkpoint. Transactions that committed before the checkpoint (like $T_4$ ) are already guaranteed to be flushed to the non-volatile storage, so they do not need to be redone.
Undo List: Contains transactions that were active (started but not committed) at the time of the crash. This includes:
- Transactions that were active during the checkpoint and never committed.
- Transactions that started after the checkpoint but did not commit before the crash.

Let's trace the transactions chronologically:

$T_4$ : Starts and commits before the checkpoint. Since it is already committed and checkpointed, it requires no action (neither Undo nor Redo).
$T_1$ : Starts before the checkpoint but does not commit before the checkpoint. It remains uncommitted at the time of the crash. Thus, it must be undone.
$T_2$ : Starts after the checkpoint and commits before the crash. Thus, it must be redone.
$T_3$ : Starts after the checkpoint but does not commit before the crash. Thus, it must be undone.