edited by
24,605 views
57 votes
57 votes

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?

  1. Undo: T3, T1; Redo: T2
  2. Undo: T3, T1; Redo: T2, T4
  3. Undo: none; Redo: T2, T4, T3, T1
  4. Undo: T3, T1, T4; Redo: T2
edited by

5 Answers

Best answer
89 votes
89 votes
$${\begin{array}{|c|c|c|c|}\hline
\textbf{T1}&    \textbf{T2}&  \textbf{T3}& \textbf{T4} \\\hline
&     &    &      \text{start}  \\ \hline  
&     & &      \text{w(y, 2, 3)} \\     \hline
\text{start} &     &  &           \\\hline
&&&     \text{commit}    \\\hline
\text{w(z, 5, 7) }\\\hline   
\text{checkpoint}&     \text{checkpoint}& \text{checkpoint}&      \text{checkpoint}  \\\hline  
&     \text{start}  \\\hline
&     \text{w(x, 1, 9)}      \\\hline
&     \text{commit}&  &            \\\hline
&    &  \text{start}&   \\\hline && \text{w(z, 7, 2)} \\\hline \text{crash} & \text{crash}&\text{crash}&\text{crash} \\\hline
\end{array}}$$

Now from the table we can find that $T1$ and $T3$ has uncommitted write operation, so they must be undone. Even though $T2$ has committed after writing, but it is after checkpoint. So, it needs to be redone.

Answer is A.
edited by
47 votes
47 votes

To solve this problem we need to follow certain steps :-

Read the log file backwards up to the checkpoint (not before it) :-

1) If you find (commit, Ti) , add Ti to Redo-list.

2) If you find (start, Tj), add Tj to Undo-list. (Here note that Tj is a transaction which has only started and not committed i.e. no (commit, Tj) is found before (start, Tj) while retracing backwards).

3) Suppose there was a transaction which started before checkpoint but has not committed either before or after the checkpoint( in this case it is T1). Now how will we get to know about it as we can't go before checkpoint? Here is a thing we need to know that checkpoint maintains a list of all active transactions. Add such transaction to the Undo-list.

So now using these we can go ahead :-

(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);

We move backwards, find (start, T3) and no (commit, T3) before (in our path of going backwards). So put it in Undo-list. <Step 2>

Then find (commit, T2) so put it in Redo-list. <Step 1>

Since T4 has already committed before checkpoint so this checkpoint does not have T4 in it's list of active transaction. Only T1 is there as it has started but has not committed anywhere. So put T1 in Undo-list. <Step 3>

Final answer: Undo-list- {T3,T1} ; Redo-list- {T2}. Option A.

Reference: https://www.youtube.com/watch?v=H9zYo0KY1Kw&t=889s

edited by
19 votes
19 votes

Ans: A)

Checkpoint is a mechanism where all the previous logs are removed from the system and stored permanently in a storage disk. Checkpoint declares a point before which the DBMS was in consistent state, and all the transactions were committed.

The recovery system reads the logs backwards from the end to the last checkpoint.

It maintains two lists, an undo-list and a redo-list.

If the recovery system sees a log with <Tn, Start> and <Tn, Commit> or just <Tn, Commit>, it puts the transaction in the redo-list. (Redo: T2)

If the recovery system sees a log with <Tn, Start> but no commit or abort log found, it puts the transaction in undo-list. (Undo: T3, T1)

Answer:

Related questions

33 votes
33 votes
4 answers
1
44 votes
44 votes
3 answers
3