Recovery Techniques Based on Immediate Update

1. Introduction

In Immediate Update recovery techniques, the database may be updated on disk before a transaction reaches its commit point.

This means:

• Some updates of a transaction can appear on disk before commit.

• If the transaction fails, these updates must be undone to maintain database consistency.

Therefore, the system must maintain log records containing both old and new values of updated data items.

---

2. Key Idea of Immediate Update

When a transaction performs an update operation:

1. The update may be written immediately to the database on disk.

2. Before the update is written, the log record must be written.

3. If the transaction fails later, the system rolls back the changes using the log.

This is achieved using UNDO operations.

---

3. Logging Requirements

Because the database may contain updates of uncommitted transactions, the log must store:

[write_item, Transaction_ID, Data_Item, Old_Value, New_Value]

Where:

Term	Meaning
Old_Value	Before Image (BFIM)
New_Value	After Image (AFIM)

• BFIM is used for UNDO

• AFIM is used for REDO

---

4. Buffer Management Strategy

Immediate update techniques use the Steal Policy.

Steal Policy

Updated buffers can be written to disk before the transaction commits.

This requires UNDO operations during recovery.

---

5. Types of Immediate Update Recovery Algorithms

There are two types of immediate update algorithms.

Algorithm	Undo	Redo
UNDO / NO-REDO	Yes	No
UNDO / REDO	Yes	Yes

---

6. UNDO / NO-REDO Recovery Algorithm

Concept

In this technique:

• All updates of a transaction must be written to disk before commit.

• Therefore, if a crash occurs after commit, the database already contains all changes.

Thus:

• REDO is not required

• UNDO is required for uncommitted transactions

---

Disk Policy Used

Steal + Force

Policy	Meaning
Steal	Updated pages may be written before commit
Force	All updates written to disk before commit

---

Recovery Action

If system crashes:

1. Identify transactions that did not commit.

2. Undo their updates using BFIM values.

3. Committed transactions require no redo.

---

7. UNDO / REDO Recovery Algorithm

Concept

This is the most general and commonly used recovery technique.

In this approach:

• Updates may be written to disk before commit.

• Committed transactions may not have all updates written to disk.

Therefore both operations are required:

UNDO → for uncommitted transactions
REDO → for committed transactions

---

Disk Policy Used

Steal + No-Force

Policy	Meaning
Steal	Updated pages may be written before commit
No-Force	Updates may remain in memory after commit

This strategy improves system performance.

---

8. Immediate Update Recovery Algorithm (RIU_M)

In a multiuser environment, recovery is performed using the RIU_M procedure.

The system maintains two lists:

1. Committed Transactions List

Transactions that committed after the last checkpoint.

2. Active Transactions List

Transactions that started but did not commit before crash.

---

9. Steps of RIU_M Recovery Procedure

Step 1: Identify Transactions

From the log after the last checkpoint:

• Identify committed transactions

• Identify active transactions

---

Step 2: UNDO Operations

Undo all updates made by active (uncommitted) transactions.

Important rule:

• Undo operations must be performed in reverse order of log entries.

This ensures correct restoration.

---

Step 3: REDO Operations

Redo all updates made by committed transactions.

Important rule:

• Redo operations must be performed in the same order as in the log.

---

10. UNDO Operation

The UNDO procedure restores the before image (BFIM).

Log record format:

[write_item, T, X, old_value, new_value]

UNDO operation:

X = old_value

This restores the database to the state before the transaction update.

---

11. REDO Operation

The REDO procedure restores the after image (AFIM).

Log record format:

[write_item, T, X, old_value, new_value]

REDO operation:

X = new_value

This reapplies committed changes.

---

12. Order of UNDO and REDO

Operation	Order
UNDO	Reverse order of log
REDO	Same order as log

This ensures correct recovery.

---

13. Efficiency Improvement

To improve performance:

Optimized REDO

• Start scanning log from the end.

• Redo only the last update of each data item.

• Maintain a list of redone items.

---

Optimized UNDO

• Scan log forward.

• Undo each item only once.

• Maintain a list of undone items.

---

14. Role of Concurrency Control

Immediate update recovery usually works with Strict Two-Phase Locking (Strict 2PL).

Strict schedules guarantee:

• Transactions cannot read uncommitted data

• No cascading rollback

• Safe recovery

However, deadlocks may occur, which may cause transaction aborts and UNDO operations.

---

15. Advantages of Immediate Update

1. Supports higher concurrency

2. Allows long transactions

3. Uses buffer space efficiently

4. Most practical recovery technique

---

16. Disadvantages

1. Recovery process is more complex

2. Requires both UNDO and REDO

3. Needs detailed logging

---

17. Summary

Immediate update allows database updates before transaction commit, requiring recovery mechanisms to handle failures.

Algorithm	Disk Policy	Undo	Redo
Deferred Update	No-Steal	No	Yes
Immediate Update (UNDO/NO-REDO)	Steal + Force	Yes	No
Immediate Update (UNDO/REDO)	Steal + No-Force	Yes	Yes

The UNDO/REDO algorithm is the most widely used recovery technique in modern DBMS.

---

Immediate update recovery allows database updates before the transaction commits. If a transaction fails, its updates are undone using before images stored in the log. Depending on the policy used, the recovery process may require UNDO operations, REDO operations, or both.