The Gateway to Computer Science Excellence
+31 votes
6.7k views

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
in Databases by Veteran (105k points)
edited by | 6.7k views
+2

I will really recommend to go through these series of 4-5 videos. 

( It is taught by IIT professor... actually it is an nptel​​ course but are just segmented by some youtuber ... so this is a standard and relevant source to clear this concept )

This one and subsequent 4-5 videos, after that you can easily solve these problems

0

@HeadShot

After GATE 2015 the syllabus has been revised which was followed from GATE 2016 till date.

Are these topics in the syllabus GATE 2020?

4 Answers

+59 votes
Best answer
$${\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.
by Active (3.8k points)
edited by
+1
sir,  here wt is puprose of check point and why it is used.??
0

Here in place of W(X,1,9)   , if we have W(Z,7,10)

And  In place of  W(Z,7,2) , we have  W(Z,10,2)

Then we should go for IRRECOVERABLE option??

+72
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.

If the recovery system sees a log with <Tn, Start> but no commit or abort log found, it puts the transaction in undo-list.
+2
T1 T2 T3 T4 T5          
        start
        w(y,3,6)
      start  
      W(y,2,3)  
start        
      commit  
W(z,5,7)        
Checkpoint Checkpoint Checkpoint Checkpoint Checkpoint
  start      
  W(x,1,9)      
  commit      
    start    
    W(z,7,2)    
crash crash crash crash crash


suppose we add a couple of operations in T5.

Now for the above question, does t5 needs to be undone ?? According to korth ("Scan backwards from end of log to find the most recent < checkpoint > record. Continue scanning backwards till a record < T i , start > is found. Need only consider the part of log following this record; earlier part of log can be ignored, and can be erased
whenever desired
"), it should be ignored. But I think it should be undone. Please someone comment on this ?

+3
Checkpoint maintains a list of active transactions also during checkpointing...

So T1,T5 will be in the list.
0

@ learncp

T1,T3,T5 are undone and T2 redone

Order:T5,T3,T1,T2

Operation

T5:X

T3:C=7

T1:X

T2:x=9

+15

srestha I THINK THIS WILL BE ORDER FOR UNDO T3,T1,T5 which works reverse of log order

correct me if wrong?

+2
Nice example

Awesome video @set2018
+1
first undo===>reverse of log order then redo ==> in the same way as log order
0
Why is there a need for REDO of already committed transactions? According to me just UNDO of failed transaction should work.
0
Because Commit operation is After the Checkpointing. That's Why we have to do redone.
0

My question is why do we need REDO in general?

When we do all UNDO operations, we reach a state in which database already have all the changes made by committed transactions. How is REDOing of same committed transactions doing any good?

0
Why not T4 is Redo? We need to perform redo on Commited and Undo on uncommitted right?
+1
T4 is not redo because it is committed before checkpoint.
0
what will be answer if T1 will commit after checkpoint.

will it be added to redo list or not.
+1
Yes it will be added to redo list
0
It will be in Redo list.
+18 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)

by Active (1.1k points)
+1
but here for T1, recovery system can not find anything between end of log and recent checkpoint. how it decided to put it in undo list?
0
Why t1 is in undo.lis.how u decide bcoz their is nothing in between end and checkpoint ?
+2
"The recovery system reads the logs backwards from the crash point to last checkpoint "

please correct your statement
+18 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

by Boss (23.1k points)
edited by
0
this answer deserves to be the best @arjun sir
+1

@Phalkey This compliment is more than enough _/\_ Thanks :) :P

0

Combine this answer with the table provided in the answer of @worst_engineer and this answer is golden!

0

@MiNiPanda

Nice explanation.

I have a doubt. In this question, suppose the active transaction T1 gets committed after checkpoint and then the system failure occurs then where would I put T1 then, in UNDO List or REDO List?

0
BEST Answer!!!!! @arjun sir, Beautiful concept explanation
0

suppose if there is no checkpoint then all committed transactions should be redone and uncommitted transaction should be undone?  Is this interpretation correct? @MiNiPanda @PRANAV M

+1 vote
answer is a
by Active (1.4k points)
0
explain pls?
+6
@naresh-answer a hai to kya kru vo to sbko pta hai?

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,644 questions
56,531 answers
195,622 comments
101,350 users