Mumbai University > Computer Engineering > Sem 4 > Database Management System

Marks: 10M

Year: May 2015

• A recoverable schedule is one where, for each pair of Transaction Ti and Tj such that Tj reads data item previously written by Ti the commit operation of Ti appears before the commit operation Tj .

• Suppose that the system allows $T_9$ to commit immediately after execution of read(A) instruction. Thus $T_9$ commit before $T_8$ does.
• Now suppose that $T_8$ fails before it commits. Since $T_9$ has read the value of data item A written by $T_8$ we must abort $T_9$ to ensure transaction Atomicity.
• However, $T_9$ has already committed and cannot be aborted. Thus we have a situation where it is impossible to recover correctly from the failure of $T_8$.
• Recoverable schedules are desirable because failure of a transaction might otherwise bring the system into an irreversibly inconsistent state.

• Non recoverable schedules may sometimes be needed when updates must be made visible early due to time constraints, even if they have not yet been committed, which may be required for every long duration transactions.

• Recovery with Concurrent Transactions:

  When more than one transaction are being executed in parallel, the logs are interleaved. At the time of recovery, it would become hard for the recovery system to backtrack all logs, and then start recovering. To ease this situation, most modern DBMS use the concept of 'checkpoints'.

• Checkpoint:

  • Keeping and maintaining logs in real time and in real environment may fill out all the memory space available in the system. As time passes, the log file may grow too big to be handled at all.
  • 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.
  • During recovery we need to consider only the most recent transaction Ti that started before the checkpoint, and transactions that started after Ti.
    • Scan backwards from end of log to find the most recent <checkpoint>record
    • Continue scanning backwards till a record <tistart>is found.
    • Need only consider the part of log following above start record. Earlier part of log can be ignored during recovery, and can be erased whenever desired.
    • For all transactions (starting from Ti or later) with no <ticommit>,executeundo(Ti). (Done only in case of immediate modification.)
    • Scanning forward in the log, for all transactions starting from Ti or later with a <ticommit>,executeredo(Ti).

• Recovery:

  • We modify the log-based recovery schemes to allow multiple transactions to execute concurrently.
  • All transactions share a single disk buffer and a single log .A buffer block can have data items updated by one or more transactions.
  • We assume concurrency control using strict two-phase locking ;i.e. the updates of uncommitted transactions should not be visible to other transactions
  • Otherwise how to perform undo if T1 updates A, then T2 updates A and commits, and finally T1 has to abort?
  • Log records of different transactions may be interspersed in the log. The check pointing technique and actions taken on recovery have to be changed since several transactions may be active when a checkpoint is performed.
  • Checkpoints are performed as before, except that the checkpoint log record is now of the form

  <checkpoint l=""> where L is the list of transactions active at the time of the checkpoint

  • We assume no updates are in progress while the checkpoint is carried out (will relax this later)
  • When the system recovers from a crash, it first does the following:
    • Initialize undo-list and redo-list to empty
    • Scan the log backwards from the end, stopping when the first <checkpoint l="">record is found.
  • For each record found during the backward scan:
    • if the record is <ti commit="">, add Ti to redo-list
    • if the record is <ti start="">, then if Ti is not in redo-list, add Ti to undolist.
  • For every Ti in L, if Ti is not in redo-list, add Ti to undo-lis
  • 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=""> 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.