GATE CSE 2006 | Question: 20, ISRO2015-17

Question

Consider the following log sequence of two transactions on a bank account, with initial balance $12000,$ that transfer $2000$ to a mortgage payment and then apply a $5\%$ interest. 

1. T1 start 
2. T1 B old $=12000$ new $=10000$
3. T1 M old $=0$ new $=2000$
4. T1 commit
5. T2 start
6. T2 B old $=10000$ new $=10500$
7. T2 commit

Suppose the database system crashes just before log record $7$ is written. When  the system is restarted, which one statement is true of the recovery procedure? 

• A. We must redo log record $6$ to set B to $10500$ 
• B. We must undo log record $6$ to set B to $10000$ and then redo log records $2$  and $3$
• C. We need not redo log records $2$ and $3$ because transaction T1 has committed 
• D. We can apply redo and undo operations in arbitrary order because they are idempotent

Comments

hey i think u have missed one line in the question . when does the failure happened. u missed it i think .

---

You are right

---

not 1200  but 12000 .. value is wrong for B old

---

yes, i think it's typing mistake.

---

https://www.youtube.com/watch?v=H9zYo0KY1Kw

upto 15:15

---

@MRINMOY_HALDER thanks bro.really helped. 

---

Is this topic still in syllabus?? Because it is in recovery system chapter in korth which i think is not in syllabus.. Correct me if iam wrong...

---

(In Case the video is not opening.)

So, once the crash happens the log is read backwards up to the checkpoint and the ... So, this
is read backwards this is very importantly, this is read backwards up to the checkpoint and the
following thing is done , if there is a (commit, Ti) is found in this backward scan then there is
a redo list, where Ti is added to the redo list. Now, on this scanning backward if suppose on
the other hand somebody founds the (start, Tj) then there is an undo list, where Tj is added.

And suppose there is some other Tk which started earlier ... Now, note that scanning of the log
goes only up to the checkpoint, however, what will happen is that since Tk started before the
checkpoint and has not committed, Tk must appear somewhere in this TL. So, this is, must be
in the active, in the list of active transactions, so this is the list of active transactions. So, Tk
must be appearing somewhere in that. So, Tk is not found using this scanning, but Tk is in the
active list, then Tk is also added to the undoing list.

Of course, if Tk has not been in the redo list; that means, Tk there is no commit Tk entry of
this, if there is (commit, Tk) entry, then Tk would have been added to the redo list then nothing needs to be done. But, otherwise Tk needs to be added to the undo list. So, this is the way how
the redo list and the undo list are being made and then we follow the same thing. So, undos
are first done in a reverse order and then the redos are being done in a forward order. 

So, the transactions in the undo list are first revert it back in the reverse order as they appear
in the log and the transactions in the redo list are then done in the forward order as they
appear in the log. And one more thing only the operations after the checkpoint, so, this is read
only up to the checkpoint, so, only the operations after the checkpoint needs to be either
undone or redone, that is it, because before that everything has been either undone or redone
correctly.

Source : https://nptel.ac.in/content/storage2/nptel_data3/html/mhrd/ict/text/106104135/lec32.pdf 

---

Anything committed after Checkpoint, needs to be redone

Any transaction who started earlier but not committed before CHECKPOINT, needs to be undone.

---

Similar question: https://gateoverflow.in/8246/gate2015-2-46

---

https://www.youtube.com/watch?v=sjHLXU4Jvrk&list=PLC36xJgs4dxEKjYXHSoKN35wRb_MJx9Yn&index=37

---

https://drive.google.com/file/d/1bPUx7LD3pW0rBiQa4bs_el2CS6SYjg7C/view

---

Steps after database crashes:-

Step 1) UNDO the uncommitted transactions. Even UNDO the uncommitted records which are before the checkpoint. UNDO happens in reverse order (from bottom to top).

Step 2) REDO the committed transactions. No need to REDO the records which are already committed before the last checkpoint. REDO happens in original order (from top to bottom).

With these simple steps any questions on deferred database (recovery) can be solved very easily.

Similar qs:-

Databases: GATE CSE 2015 Set 2 | Question: 46 (gateoverflow.in)

Databases: GATE CSE 2021 Set 1 | Question: 13 (gateoverflow.in)

---

@Abhrajyoti00 Great Man :) 

Answer 1

Answer should be B. Here we are not using checkpoints so, redo log records $2$ and $3$ and undo log record $6$.
Consider the following steps taken from the book 'Navathe':

PROCEDURE RIU_M

1. Use two lists of transactions maintained by the system: the committed transactions since the last checkpoint and the active transactions
2. Undo all the $write$_$item$ operations of the $active$ (uncommitted) transaction, using the UNDO procedure. The operations should be undone in the reverse order in which they were written into the log.
3. Redo all the $write$_$item$ operations of the $committed$ transactions from the log, in the order in which they were written into the log.

Comments

I don't understand the need (or rather can't think of a use case) of redoing the committed transactions.

According to me,

• In Deferred database modification, just restart of uncommitted transaction will do.
• In Immediate database modification, undo and then restart of uncommitted transactions will do.

---

Why option B is correct instead of C?

Answer

---

One small doubt , as per what I have read in sudarshan,korth that redo operations are done first and after that for whom we have not found commit or abort log record are undo. So I think option B should be Redo log records 2 and 3 and then Undo log record 6, if its wrong please correct me

Answer 2

Checkpoint : 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.

When a system with concurrent transactions crashes and recovers, it behaves in the following manner −

 

 

=>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.

All the transactions in the undo-list are then undone and their logs are removed. All the transactions in the redo-list and their previous logs are removed and then redone before saving their logs

so we must undo log record 6 to set B to 10000 and then redo log records 2 and 3 because system fail before commit operation. So we need to undone active transactions(T2) and redo committed transactions (T1)

So Answer is B redo log records 2 and 3 and undo log record 6

 

 

Comments

Second Last Paragraph:  All the transactions in the redo-list and their previous logs are removed and then redone before saving their logs ??

What do you mean by this??

---

@LeenSharma

@Shaik Masthan

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 log sees <Tx start>...<Tx,abort >  then it will be added to REDO list right ??

---

@jatin khachane 1

yes ! But think,

" is there any problem if i add abort transactions to UNDO-LIST ? " ---- NO problem

" is there any problem if i doesn't add abort transactions to either UNDO-LIST or REDO-LIST ? (i.e., simply ignoring ) " --- yes, problem arises !

Answer 3

The database can be modified using two approaches by executing logs:

1. Deferred database modification: permanent database update happens when transaction commits and only new values needs in logs.
2. Immediate database modification: permanent database update happens immediately and old and new both values needs in logs.

By looking on logs and options in this question, it seems to follow immediate database modification. It means till crash of system, few of log records has written in database. But system do not know after crashing that how many log records already written in database.

 

So after restart system, undo all uncommitted transactions like T2 (reverse log record 6 to set B back to 10000) and then redo all committed transactions like T1 (log records 2 and 3). Thus, it needs to undone active transactions (T2) and redo committed transactions (T1). Process Steps:

1. Go to log record (vii) where system crashed and reads the logs backwards.
2. If find some committed transaction then puts to Redo List; If find some uncommitted transaction then executes its logs in reverse like T2 writes B to 10000.
3. Redo T1's log records like write B to 10000 and M to 2000 without caring already existing values of A & B in database.

Answer obviously is B. No need to discuss checkpoints for answer of this question.

Comments

Yes correct. It is immediate database modification because "old values" are mentioned.

Answer 4

We must undo log record 6 to set B to 10000 and then redo log records 2  and 3 bcoz system fail before commit operation. So we need to undone active transactions(T2) and redo committed transactions (T1). https://gateoverflow.in/8246/gate2015-2_46