Chapter 5: Database Recovery Techniques
Previous Lectures
◼ Transactions(Chapter-3)
◼ Concurrency control(Chapter-4)
This Lecture
◼ Recovery(Chapter-5)
Topics to be covers
What is database Recovery?
Recovery Concepts Based on Deferred Update
Recovery Concepts Based on Immediate Update
Shadow Paging
The ARIES Recovery Algorithm
5.1. What is database recovery?
Database recovery is the process of restoring a database to a
consistent state after a failure.
Data recovery means to get back the information which was lost
This can be done by using
◼ Backup and
◼ Log files
Recovery is the rebuilding of a database or table after a failure
If there is a failure
Some transactions must be redone or undone using
different recovery techniques.
5.2. Failures in DBMS
Storage media failure
◼ E.g., memory, hard disk, etc.
Power interruption
Network failure
Transaction failure
◼ E.g., incorrect input
Application failure
Hardware and software failure
Natural disasters
Carelessness or unintentional destruction of data
◼ Accidentally deleting files in database
◼ Formatting/resetting a storage device
Intentional corruption or hampering of data
◼ Deliberately damaging or destroying data
5.3. Recovery and redundancy
Solution for failure: → Recovery techniques
All recovery techniques require redundant/duplication data
What are the disadvantages of duplicating a DB for
recovery?
Two times storage is required
Have to operate two DBs simultaneously
Two DBs should have independent failure modes
5.4. Commit Point of a Transaction
5.6. Database Recovery Techniques
The following techniques are used to recover data in a DBMS,
1. Log-based recovery
2. Recovery through deferred update
3. Recovery through Immediate update
4. Shadow paging
5.6. Database Recovery Techniques(cont.)
1. Log-based recovery:
◼ Any DBMS has its own system logs
◼ System logs have the records for all activity/
transactions/operations that has occurred in the system
◼ All transactions records have their own ID, status, and
timestamps.
5.6. Database Recovery Techniques(cont.)
1. Log-based recovery (cont…):
The following information can be found in log files for
transactions:
◼ Transaction ID:
◼ It is a unique identifier for the transaction.
◼ Transaction start time:
◼ It is the time at which the transaction started.
◼ Transaction end time:
◼ It is the time at which the transaction ended.
◼ Transaction type:
◼ It is the type of transaction, such as insert, update, or delete.
◼ Transaction status:
◼ It is the status of the transaction, such as committed, aborted, or
rolled back.
◼ Transaction data:
◼ It is the data that was changed by the transaction.
5.6. Database Recovery Techniques(cont.)
1. Log-based recovery (cont…):
◼ We can use the log information presented in the previous
slide to see the change and recover the data.
◼ Suppose we have the following transaction(i.e., T) and two
operation, I.e., undo and redo
◼ [write_item, T, X, old_value, new_value]
◼ A redo operation can be done to convert from the old state of data to
the new state of data
◼ A undo operation can be used to convert from the new state of data to
the old state of data
5.6. Database Recovery Techniques(cont.)
2. Recovery through Deferred Update:
◼ Also called NO-UNDO/REDO
◼ All the log files entries are made first but the actual updates are
done later
◼ Or, the actual updates are made after the transaction is
committed.
◼ In other words, during a transaction, updates are only recorded
in the log.
◼ The log file holds the updates that are going to be applied.
◼ To summarize, a deferred update is an update that is applied
after the transaction is committed
5.6. Database Recovery Techniques(cont.)
2. Recovery through Deferred Update (cont..):
◼ While a transaction runs:
◼ Changes made by that transaction are not recorded in the database
◼ But, recorded in the log file.
◼ On a commit:
◼ The new/updated data is recorded in the actual database
◼ On an abort:
◼ Do nothing → why the database has not been changed
◼ On a system restart after a failure:
◼ REDO the log
5.6. Database Recovery Techniques(cont.)
3. Recovery through Immediate Update:
an immediate update is applied as soon as it is issued
When a transaction issues an update command, the
database can be updated without any need to wait for
the transaction to reach its commit point.
In this technique, the database is modified immediately
after every operation.
After write/read operation, the database is updated
immediately without commit operation.
Deferred Update Vs. Immediate Update in DBMS
Example, suppose that we have a database with a table of
customers and consider the following two SQL statements.
SQL statement for Immediate Update
SQL statement for Deferred update
Database Recovery Techniques(cont.)
4. Shadow Paging:
◼ It is recovery technique that is used to recover database.
◼ The idea is to maintain two page tables during the life of a
transaction:
◼ the current page table and
◼ the shadow page table
◼ When the transaction starts, both tables are identical.
◼ The shadow page is never changed during the life of the
transaction
◼ The shadow page table is stored in non-volatile memory.
Database Recovery Techniques(cont.)
4. Shadow Paging (cont…):
Now let see the concept of shadow paging step by step:
Step 1:
◼ The database system creates a shadow page for each page in the
database.
◼ So, we have two tables,
◼ The current page table and
◼ The shadow page table.
◼ Shadow page table is a copy of the current page table.
Step 2:
◼ When a transaction starts, both the tables look identical,
◼ But, once the transaction started its operations, both tables look
difference, since the current table is updated for each write
operation.
◼ The shadow page is never changed during the life of the transaction.
Database Recovery Techniques(cont.)
4. Shadow Paging (cont…):
Now let see the concept of shadow paging step
by step:
Step 3:
◼ When the current transaction is committed, the shadow page entry
becomes a copy of the current page table entry
Step 4:
◼ The shadow page table is stored in non-volatile memory.
◼ If the system crash occurs, then the shadow page table is copied to
the current page table.
Database Recovery Techniques(cont.)
Shadow Paging (cont…):
Advantages and disadvantages of shadow paging
◼ The advantages of shadow paging are as follows:
◼ No need for log records.
◼ No undo/ Redo algorithm.
◼ Recovery is faster.
◼ The disadvantages of shadow paging are as follows:
◼ Data is fragmented or scattered.
◼ Garbage/duplicated collection problem.
◼ Concurrent transactions are difficult to execute.
ARIES Recovery Algorithm
It is an example of a recovery algorithm used in database
systems
ARIES Stands for Algorithm for Recovery and Isolation Exploiting
Semantics
It is based on the concept of log-based recovery
It keeps track of all changes made to the database in a log file
When a failure occurs, the ARIES algorithm uses the log file to
reconstruct the database
It was developed by IBM
ARIES Recovery Algorithm(cont…)
ARIES is a technique to ensure properties of transaction, includes
Consistency
Atomicity
Isolation
Durability
The ARIES recovery algorithm consists of 3 phases:
Phase-1: Analysis
Phase-2: Redo
Phase-3: Undo
ARIES Recovery Algorithm(cont…)
The ARIES recovery algorithm consists of 3 phases:
Phase-1: Analysis
◼ The analysis phase identifies
◼ the dirty (updated) pages in the buffer/memory → this
information is used by next two phases.
◼ the set of transactions that were active at the time of the crash.
◼ It determines operation, e.g., REDO operation
Phase-2: Redo
◼ This phase reapplies updates from the log to the database
◼ Only the necessary REDO operations are applied during recovery.
Phase-3: Undo
◼ During the UNDO phase,
◼ the log is scanned backwards and
◼ the operations of transactions that were active at the time of the
crash are undone in reverse order.
