Mumbai University > Information Technology > Sem 3 > Database Management System

Marks: 10M

Year: May 2015, May 2016

1. Log Based Recovery

• One of the most widely used structure for database modifications recording is the log.
• Log can be defined as a sequence of log records, recording all the update activities in the database.
• Log record contains various fields such as Transaction identifier, data item identifier, old value and new value.
• Whenever a transaction performs a write, it is essential that the log record for that write be created before the database is modified.
• Once a log record exists, we can output the modification to the database if that is desirable.
• Also, we have the ability to undo a modification that has already been output to the database.
• We undo it by using the old-value field in log records.
• Shadow Paging:
  • Shadow paging considers the database to be made up of a number of fixed size disk pages.
• A directory with n entries is constructed, where the ith entry points to the ith database page on disk.
• The directory is kept in main memory if it is not too large, and all read and write references, to the database pages on disk go through it.
• When a transaction begins executing, the current directory, whose entries point to the most recent or current database pages on disk, is copied into a shadow directory. The shadow directory is then saved on disk while the current directory is used by the transaction.
• During transaction execution, the shadow directory is never modified. When a write_item operation is performed, a new copy of the modified database page is created, but the old copy of that page is not overwritten.
• Instead, the new page is written elsewhere, on some previously unused disk block. The current directory entry is modified to point to the new disk block, whereas the shadow directory is not modified and continues to point to the old unmodified disk block.

• Comparison:

• The difficulties with log based approach are as follows:

  • The search process is time consuming.
  • Most of the transactions that, according to our algorithm, need to be redone have already written their updates into the database. Although redoing them will cause no harm, it will nevertheless cause recovery to take longer.
• In shadow paging system, the overhead of log-record output is eliminated, and recovery from crashes is significantly faster since no undo or redo operations are needed.

• The commit of a single transaction using shadow paging requires multiple blocks to be output:

  • The actual data blocks
  • The current page table

  • The disk address of the current page table.

    Log-based schemes need to output only the log records, which, for typical small transactions, fit within one block.

• Locality is an important factor which needs to be considered in recovery techniques.
• Locality can be defined as the process of keeping related database pages close physically on the disk.
• Shadow paging causes database pages to change location when they are updated. Hence, the locality property of the pages is lost.
• This results in the usage of complex, higher overhead schemes for physical storage management in shadow paging as compared to log based recovery.
• Also, garbage collection becomes necessary for shadow paging recovery system.
• Because, each time a transaction commits, the database pages containing the old version of data changed by the transaction become inaccessible. Such pages are considered garbage, since they are not part of free space and do not contain usable information.
• Garbage may be created also as a side effect of crashes. Periodically, it is necessary to find all the garbage pages, and to add them to the list of free pages.
• Thus, garbage collection in shadow paging recovery system results in additional overhead and complexity on the system.