Register

GATE CSE 2006 | Question: 20, ISRO2015-17

• edited by
41,945 views
106 106 votes

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? 

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

9 Answers

Best answer
159 159 votes

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.
• edited by
106 106 votes

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

 

 

• edited by
26 26 votes

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.

• edited by
9 9 votes

For recovery, we'll be having 2 choices, either Deferred updation or Immediate updation techniquee.

Now If we take Deferred Updation which says only REDO and no UNDO then no option is matching.Then we'll take Immediate Updation, which is having two choices further as UNDO/No-REDO and UNDO/REDO.

If we follow UNDO/No-REDO then we'll have to UNDO active transaction T2 only (no REDO on T1 as changes are immediate to DB and T1 already committed).Again no option matches with this choice.

So we'll follow UNDO/REDO which says that all committed transactions up to checkpoint need not be REDO, committed but not checkpointed are need to be REDO and active transaction need to be UNDO.Hence T2 needs UNDO and then T1 needs REDO. Thus, answer is option B

1 1 vote

Up until the checkpoint, do nothing.

For the logs after the checkpoint (which is the case here, we see no checkpoints) undo all uncommitted transactions, and redo all committed transactions.

A is wrong, because we have to undo record 6, not redo.

B is correct.

C is wrong, because we redo committed transactions that are not checkpointed. (We see no checkpoint here)

D is just extremely stupid. Would lead to race condition / data inconsistency.

Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 2006 | Ques...Next → · GATE CSE 2006 | Ques...
← Previous in category · GATE CSE 2003 | Ques...Next in category → · GATE CSE 2004 | Ques...
Position:
Show:

Related questions

57 57 votes
11 answers 11 answers
92.9k
92.9k views
Ishrat Jahan asked Nov 1, 2014
92,890 views
GATE IT 2006 | Question: 63, ISRO2015-57
A router uses the following routing table:\begin{array}{|l|l|l|} \hline \textbf {Destination} & \textbf { Mask} & \textbf{Interface} \\\hline \text {144.16.0.0} & \text...
10 10 votes
3 answers 3 answers
4.9k
4.9k views
go_editor asked Jun 17, 2016
4,890 views
ISRO2015-20
Let $\text{R = (A, B, C, D, E, F)}$ be a relation scheme with the following dependencies $\text{C} \rightarrow \text{F, E} \rightarrow \text{A}, \text{EC} \rightarrow \te...
46 46 votes
5 answers 5 answers
18.3k
18.3k views
Rucha Shelke asked Sep 26, 2014
18,349 views
GATE CSE 2006 | Question: 70
The following functional dependencies are given:$ AB\rightarrow CD,AF\rightarrow D,DE\rightarrow F,$$C\rightarrow G,F\rightarrow E,G\rightarrow A $Which one of the follow...
64 64 votes
9 9 answers
27.0k
27.0k views
Rucha Shelke asked Sep 26, 2014
27,044 views
GATE CSE 2006 | Question: 69
Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key. ...