GATE CS Mastery
Cheat sheets

GATE CS 2015 Set 2 · Databases

Question 56

MCQPrinted as CS Q.462 marksWrong answer: −2/3Medium (estimate)

Question

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?

Choose one option
Official answer and solution
Official answer
A
From
Official GATE 2015 answer key

Solution

Follow the standard database crash recovery rules for immediate-update logging with checkpoints.

Log contents:

  1. (start, T4)
  2. (write, T4, y, 2, 3)
  3. (start, T1)
  4. (commit, T4)
  5. (write, T1, z, 5, 7)
  6. [checkpoint]
  7. (start, T2)
  8. (write, T2, x, 1, 9)
  9. (commit, T2)
  10. (start, T3)
  11. (write, T3, z, 7, 2)
    CRASH

Recovery algorithm:

  • Undo List: Transactions that were active (started but never committed) at the time of the crash.
    • T1T_1 started before the checkpoint and did not commit   ⟹  T1∈Undo\implies T_1 \in \text{Undo}.
    • T3T_3 started after the checkpoint and did not commit   ⟹  T3∈Undo\implies T_3 \in \text{Undo}.
      Undo list = {T3,T1}\{T_3, T_1\}.
  • Redo List: Transactions that committed after the checkpoint, or were active at checkpoint and subsequently committed.
    • T4T_4 committed before the checkpoint; its changes were already flushed to disk at checkpoint   ⟹  \implies not in Redo list.
    • T2T_2 started after the checkpoint and successfully committed   ⟹  T2∈Redo\implies T_2 \in \text{Redo}.
      Redo list = {T2}\{T_2\}.

Contents: Undo: T3,T1T_3, T_1; Redo: T2T_2 (option A).

Final answer

A

Common trap

Adding T4T_4 to the Redo list, ignoring that it already committed before the checkpoint.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2015 Computer Science and Information Technology (CS) Session 2
Question
56 of 65, printed as CS Q.46
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.