Register

GATE CSE 2015 Set 2 | Question: 46

• edited by
25,829 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
User Avatar

5 Answers

Best answer
90 votes
90 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
User Avatar
48 votes
48 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
User Avatar
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)

User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

15.3k
views
4 answers
33 votes
go_editor asked Feb 12, 2015
15,314 views
GATE CSE 2015 Set 2 | Question: 1
Consider the following transaction involving two bank accounts $x$ and $y$.read(x); x:=x-50; write (x); read(y); y:=y+50; write(y)The constraint that the sum of the accou...
User Avatar
9.2k
views
2 answers
31 votes
go_editor asked Feb 12, 2015
9,246 views
GATE CSE 2015 Set 2 | Question: 32
Consider two relations $R_1(A,B)$ with the tuples $(1,5), (3,7)$ and $R_2(A,C) = (1,7),(4,9)$.Assume that $R(A,B,C)$ is the full natural outer join of $R_1$ and $R_2$. Co...
User Avatar
13.5k
views
3 answers
44 votes
go_editor asked Feb 12, 2015
13,542 views
GATE CSE 2015 Set 2 | Question: 6
With reference to the B+ tree index of order $1$ shown below, the minimum number of nodes (including the Root node) that must be fetched in order to satisfy the following...
User Avatar
13.6k
views
9 answers
73 votes
go_editor asked Feb 12, 2015
13,554 views
GATE CSE 2015 Set 2 | Question: 31
A Young tableau is a $2D$ array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with $\infty$, and hence there cannot be...
User Avatar
Link Copied!