Module 5

TRANSACTION MANAGEMENT

The ACID Properties

(Reference Book 1)
The ACID Properties; Transactions and Schedules; Concurrent Execution of
Transactions; Concurrency Control Mechanisms; Error recovery methods.
 Transaction Concepts
 Transactions are a set of operations used to perform a logical set of work.

 A transaction usually means that the data in the database has changed.

 One of the major uses of DBMS is to protect the user’s data from system
failures.

 The transaction is any one execution of the user program in a DBMS.

 One of the important properties of the transaction is that it contains a

finite number of steps. Executing the same program multiple times will
generate multiple transactions.

 A transaction is a unit of program execution that

accesses and possibly updates various data items.
Transaction Concepts
 Example: Consider the following example of
transaction operations to be performed to
withdraw cash from an ATM vestibule.

 Steps for ATM Transaction

 Transaction Start.
 Insert your ATM card.
 Select a language for your transaction.
 Select the Savings Account option.
 Enter the amount you want to withdraw.
 Enter your secret pin.
 Wait for some time for processing.
 Collect your Cash.
 Transaction Completed.
 Transaction
Concepts
• A transaction can include the following basic database access
operation.

• Read/Access data (R): Accessing the database item from disk (where the
database stored data) to memory variable.

• Write/Change data (W): Write the data item from the memory variable
to the disk.

• Commit: Commit is a transaction control language that is used to

permanently save the changes done in a transaction

 Two main issues to deal with:

◦ Failures of various kinds, such as hardware failures
and system crashes
◦ Concurrent execution of multiple transactions
 Transaction
Concepts

 E.g., transaction to transfer $50

from account R(A)
A to-- 500account B:RAM.
// Accessed from
1. read(A) A = A-50 // Deducting 50₹ from A.
2. A := A –W(A)--450
50 // Updated in RAM.
R(B) -- 800 // Accessed from RAM.
3. write(A)B=B+50 // 50₹ is added to B's Account.
4. read(B) W(B) --850 // Updated in RAM.
5. B := B +commit
50 // The data in RAM is taken back
Hard Disk.
to

6. write(B)
Transaction and System Concepts
(cont’d.)

Figure 20.4 State transition diagram illustrating the states for transaction execution
 Transaction
States
• ACTIVE - It is the initial state. A transaction will be in active
state while it is executing its instructions.

• PARTIALLY COMMITED - After the final instruction of a transaction

has been processed, if the actual output is still temporarily
stored in the main memory rather than on disc, then the transaction
will remain in the partially committed state because it is still
possible that the transaction will need to be aborted (due to any
problem).

• FAILED - Whenever it is detected that the transaction has failed

due to any hardware and software problem, then that transaction
will be in the failed state.

• ABORTED - When a transaction has been rolled back, and the database
has been returned to how it was before the execution began, the
transaction is said to be in an Aborted state.

• COMMITED - After a transaction is successfully completed, the

Transaction Recovery
• Transaction recovery refers to the process of
restoring a database or a system to a
consistent state after a failure or an
unexpected interruption occurs during the
execution of a transaction.

• In a database management system (DBMS) or any

system that involves transactional processing,
ensuring data consistency is crucial.

•A failure could be due to hardware

malfunctions, software errors, power outages,
or other unforeseen events.
ACID
Properties
• Desirable Properties of Transaction (ACID Properties)
• For a transaction to be performed in DBMS, it must possess
several properties often called ACID properties.
• A – Atomicity
• C – Consistency
• I – Isolation
• D – Durability

These are used to maintain consistency in a database, before and

after the transaction.
ACID Properties

• A - Atomicity:
• Definition: Transactions are treated as atomic
units, meaning they either succeed entirely or
fail entirely.

Atomicity involves the following two operations:

• Abort: If a transaction aborts, then all the changes made
are not visible.
• Commit: If a transaction commits then all the changes
made are visible.
• Example: In a bank transaction, either the
money is transferred successfully, or the
entire transaction is rolled back.
ACID Properties

• C- Consistency:
• Definition: Ensures that the database remains
in a consistent state before and after the
transaction.

• The integrity constraints are maintained so that the database is

consistent before and after the transaction.

• The transaction is used to transform the database from one

consistent state to another consistent state.

• Example: If a database starts in a consistent

state, all transactions will bring it to
another consistent state.
ACID Properties
• I-Isolation:
• Definition: Transactions operate in isolation
from each other, ensuring that the execution
of one transaction does not impact others.
• In isolation, if the transaction T1 is being executed and using
the data item X, then that data item can’t be accessed by any
other transaction T2 until the transaction T1ends.
• The concurrency control subsystem of the DBMS enforced the
isolation property
• Example: Two transactions occurring
simultaneously should not interfere with each
other's results.
ACID Properties
• D-Durability:
• Definition: Once a transaction is committed,
its effects are permanent and will survive
subsequent failures.

• Example: Data is stored in a way that, even in

the event of a power outage or system crash,
committed transactions are not lost.

• The recovery subsystem of the DBMS has the responsibility of

Durability property.
--------- END --------
 LECTURE-2
CHAPTER 20

Introduction to Transaction
Processing Concepts and Theory
(Textbook 1)
 20.1 Introduction to
Transaction Processing
• This section, we have to discuss the concepts of
concurrent execution of transactions and recovery from
transaction failures.

• One criterion for classifying a database

system is according to the number of
users who can use the system
concurrently.

 Single-user DBMS
 At most one user at a time can use the system
 Example: home computer
 Multiuser DBMS
 Many users can access the system (database) concurrently.

 Example: airline reservations system, banking Database

Introduction to Transaction
Processing (cont’d.)
 Multiprogramming
 Allows operating system to execute multiple
processes concurrently
 Executes commands from one process, then
suspends that process and executes commands
from another process, etc.
Introduction to Transaction
Processing (cont’d.)
 Interleaved processing
 Parallel processing
 Processes C and D in figure below executes
parallelly using multiple CPU

Figure 20.1 Interleaved processing versus parallel processing of concurrent

transactions
 Transactio
ns
 Transaction:
 an executing program forms logical unit of
database processing
 A transaction includes one or more database access
operations—these can include insertion, deletion,
modification (update), or retrieval operations.
 Begin and End transaction statements
 Specify transaction boundaries explicitly within the
application program
 Read-only transaction- only retrieve data
 Read-write transaction- otherwise
Database
Items
 Database represented as a collection of named
data items.
 Size of a data item called its granularity

 Data item can be (unique name) either-

 Record—Record ID
 Disk block-whole– Address of block
 Attribute value of a record

 Transaction processing concepts independent of

item granularity
Read and Write
Operations
 The basic database access operations that a
transaction can include
 read_item(X)
 Reads a database item named X into a program variable named X
 Process includes finding the address of the disk block, and
copying to and from a memory buffer

 write_item(X)
 Writes the value of program variable X into the database item
named X
 Process includes finding the address of the disk block, copying to
and from a memory buffer, and storing the updated disk block back
to disk
Read and Write Operations
(cont’d.)
 Read set of a transaction
 Set of all items read
 Write set of a transaction
 Set of all items written

Figure 20.2 Two sample transactions (a) Transaction T1 (b) Transaction T2

WHY Concurrency Control
NEEDED
 Several problems can occur when concurrent
transactions execute in an uncontrolled manner.
 Ex. Airline reservations database in which a record is stored for
each airline flight. Each record includes the number of
reserved seats as a data item.

 T1 that transfers N reservations from one flight whose number of

reserved seats is stored in the database item named X to
another flight whose number of reserved seats is stored in the
database item named Y.
WHY Concurrency Control
NEEDED
 The types of problems we may encounter
with these two simple transactions if they run
concurrently.
 Transactions submitted by various users may
execute concurrently
 Access and update the same database items
 Some form of concurrency control is needed
 1. The lost update problem
 Occurs when two transactions that access the
same database items have operations interleaved
 Results in incorrect value of some database items
The Lost Update
Problem

For example, if X = 80 at the start (originally there were 80 reservations on the flight), N
= 5 (T1 transfers 5 seat reservations from the flight corresponding to X to the flight
corresponding to Y), and M = 4 (T2 reserves 4 seats on X), the final result should be X =
79.
However, in the interleaving of operations shown in Figure 20.3(a), it is X = 84 because
the update in T1 that removed the five seats from X was lost.

Figure 20.3 Some problems that occur when concurrent execution

is uncontrolled. (a) The lost update problem
2. The Temporary Update Problem
(or Dirty Read)

known as the dirty read

problem.

Figure 20.3 (cont’d.) Some problems that occur when concurrent execution is
uncontrolled (b) The temporary update problem
3. The Incorrect Summary
Problem
For example, suppose that a transaction T3 is calculating the
total number of reservations on all the flights;

Figure 20.3 (cont’d.) Some problems that occur when concurrent execution
is uncontrolled (c) The incorrect summary problem
4. The Unrepeatable Read
Problem
 Transaction T reads the same item twice
 Value is changed by another transaction T′
between the two reads
 T receives different values for the two reads of
the same item
Why Recovery is
Needed
 Committed transaction
 Effect recorded permanently in the database
 Aborted transaction
 Does not affect the database
 Types of transaction failures
 Computer failure (system crash)
 Transaction or system error
 Local errors or exception conditions detected by
the transaction
Why Recovery is Needed
(cont’d.)
 Types of transaction failures (cont’d.)
 Concurrency control enforcement
 Disk failure
 Physical problems or catastrophes
 System must keep sufficient information to
recover quickly from the failure
 Disk failure or other catastrophes have long
recovery times
-----END-----
 LECTURE-3
CHAPTER 20
20.2 Transaction and System
Concepts
 20.2 Transaction and System
Concepts
 For recovery purposes, the system needs to
keep track of when each transaction starts,
terminates, and commits, or aborts.

 Therefore, the recovery manager of the DBMS

needs to keep track of the following operations:
 BEGIN_TRANSACTION
 READ or WRITE
 END_TRANSACTION
 COMMIT_TRANSACTION
 ROLLBACK (or ABORT)
Figure 20.4 State transition diagram illustrating the states for transaction execution
20.3 Desirable Properties of
Transactions

 ACID properties
 Atomicity
 Transaction performed in its entirety or not at all
 Consistency preservation
 Takes database from one consistent state to
another
 Isolation
 Not interfered with by other transactions
 Durability or permanency
 Changes must persist in the database
Isolation: A transaction should appear as though it is being
executed in isolation from other transactions, even though many
transactions are executing concurrently. That is, the execution of a
transaction should not be interfered with by any other transactions
executing concurrently.
 Levels of isolation
 Level 0 isolation does not overwrite the dirty reads
of higher-level transactions
 Level 1 isolation has no lost updates
 Level 2 isolation has no lost updates and no dirty
reads
 Level 3 (true) isolation has repeatable reads
 In addition to level 2 properties
 Snapshot isolation
 20.4 Characterizing Schedules
Based on Recoverability
 Schedule or history (S)
 Order of execution of operations from all
transactions (Ti)
 Operations from different transactions can be
interleaved in the schedule
 Total ordering of operations in a schedule
 For any two operations in the schedule, one must
occur before the other
20.4 Characterizing Schedules
Based on Recoverability

Sa: r1(X); r2(X); w1(X); r1(Y);

w2(X); w1(Y);
 Conflicting Operations in a
Schedule.
 Two operations in a schedule are said to conflict if
they satisfy all three of the following conditions:
 Operations belong to different transactions
 Operations access the same item X
 At least one of the operations is a write_item(X)
 Two operations conflict if changing their order
results in a different outcome

 Read-write conflict

 Write-write conflict
 For example, in schedule Sa, the operations r1(X)
and w2(X) conflict, as do the operations r2(X) and
w1(X), and the operations w1(X) and w2(X).
 However, the operations r1(X) and r2(X) do not
conflict, since they are both read operations.

 Read-write conflict
Ex. r1(X); w2(X) to w2(X); r1(X)
 Write-write conflict
Ex. w1(X); w2(X) to w2(X); w1(X).
 It is important to characterize the types of schedules for
which recovery is possible for failed transaction, as well as
those for which recovery is relatively simple.

 1. Recoverable schedules
 Recovery is possible for committed transaction

 2. Non-recoverable schedules should not be

permitted by the DBMS.

 3. No committed transaction ever needs to be rolled back.

 4. Cascading rollback may occur in some recoverable
schedules
 uncommitted transaction has to be rolled back

because it read an item from a transaction that failed

 5. Cascadeless schedule
 Avoids cascading rollback
 6. Strict schedule
 Transactions can neither read nor write an item X
until the last transaction that wrote X has committed
or aborted
 Simpler recovery process
 Restore the before image
 20.5 Characterizing Schedules
Based on Serializability

 Serializable schedules
 Always considered to be correct when concurrent
transactions are executing
 Places simultaneous transactions in series
 Transaction T1 before T2, or vice versa
Figure 20.5 Examples of serial and nonserial schedules involving transactions T1
and T2 (a) Serial schedule A: T1 followed by T2 (b) Serial schedule B: T2 followed
by T1 (c) Two nonserial schedules C and D with interleaving of operations
 Problem with serial schedules
 Limit concurrency by prohibiting interleaving of
operations
 Unacceptable in practice
 Solution: determine which schedules are
equivalent to a serial schedule and allow those to
occur
 Serializable schedule of n transactions
 Equivalent to some serial schedule of same n
transactions
 Result equivalent schedules
 Produce the same final state of the database
 May be accidental
 Cannot be used alone to define equivalence of
schedules

Figure 20.6 Two schedules that are result equivalent for the initial value
of X = 100 but are not result equivalent in general
 Characterizing Schedules Based
on Serializability (cont’d.)
 Conflict equivalence
 Relative order of any two conflicting operations is
the same in both schedules
 Serializable schedules
 Schedule S is serializable if it is conflict equivalent
to some serial schedule S′.
 Testing for serializability of a schedule

• There is a simple algorithm for determining whether

a particular schedule is (conflict) serializable or not.
• read_item and write_item operations in
a schedule to construct a precedence
graph (or serialization graph).

Algorithm 20.1 Testing conflict serializability of a schedule S

Algorithm 20.1 Testing conflict serializability of a schedule S
 The schedule S is serializable
if and only if the precedence
graph has no cycles.

Figure 20.7 Constructing the precedence graphs for schedules A to D from Figure 20.5 to
test for conflict serializability (a) Precedence graph for serial schedule A (b) Precedence
graph for serial schedule B (c) Precedence graph for schedule C (not serializable) (d)
Precedence graph for schedule D (serializable, equivalent to schedule A)
 How Serializability is Used for
Concurrency Control
 Being serializable is different from being serial
 Serializable schedule gives benefit of concurrent
execution
 Without giving up any correctness
 Difficult to test for serializability in practice
 Factors such as system load, time of transaction
submission, and process priority affect ordering of
operations
 DBMS enforces protocols
 Set of rules to ensure serializability
-------------- END ------------
-------
 LECTURE-4
CHAPTER 21

Concurrency Control Techniques

(Textbook 1)
Introduct
ion
 Concurrency control protocols
 Set of rules to guarantee serializability
 Two-phase locking protocols
 Lock data items to prevent concurrent access
 Timestamp
 Unique identifier for each transaction
 Multiversion currency control protocols
 Use multiple versions of a data item
 Validation or certification of a transaction
21.1 Two-Phase Locking Techniques
for Concurrency Control
 Lock
 Variable associated with a data item describing
status for operations that can be applied on it.
 One lock for each item in the database
 Binary locks
 Two states (values)
 Locked (1)
 Item cannot be accessed
 Unlocked (0)
 Item can be accessed when requested
 Transaction requests access by issuing a lock_item(X)
operation
 Two operations, lock_item and unlock_item, are used
with binary locking.
 Hence, a binary lock enforces mutual exclusion on the
data item.

Figure 21.1 Lock and unlock operations for binary locks

 Lock table specifies items that have locks.
 The DBMS has a Lock manager subsystem
 Keeps track of and controls access to locks

 Rules enforced by lock manager module

 At most one transaction can hold the lock on an item at

a given time
 Binary locking too restrictive for database items
 Every transaction must obey the following rules:
 1. A transaction T must issue the operation lock_item(X) before any
read_item(X) or write_item(X) operations are performed in T.
 2. A transaction T must issue the operation unlock_item(X) after all
read_item(X) and write_item(X) operations are completed in T.
 3. A transaction T will not issue a lock_item(X) operation if it already holds the
lock on item X.1
 4. A transaction T will not issue an unlock_item(X) operation unless it already
holds the lock on item X.
 Shared/exclusive or read/write locks
 Read operations on the same item are not
conflicting.
 Must have exclusive access to lock to write
operations.
 A different type of lock, called a multiple-mode lock,
is used.
 Three locking operations
 read_lock(X)
 write_lock(X)

 unlock(X)

 Read-locked item is also called the shared locked item.

 a write-locked item is called exclusive-locked because a
single transaction exclusively holds the lock on the item.
Figure 21.2 Locking and unlocking operations for two-mode (read/write, or shared/exclusive) locks
 Lock conversion
 Transaction that already holds a lock allowed to
convert the lock from one state to another
 Upgrading
 Issue a read_lock operation then later issue a
write_lock operation.
 If T is the only transaction holding a read lock
on X at the time it issues the write_lock(X)
operation, the lock can be upgraded.
 Downgrading
 Issue a read_lock operation after a write_lock
operation.
• Using binary locks or read/write locks in transactions, as
described earlier, does not guarantee serializability of schedules
on its own.

Figure 21.3 Transactions that

do not obey two-phase
locking (a) Two transactions
T1 and T2 (b) Results of
possible serial schedules of
T1 and T2 (c) A
nonserializable schedule S
that uses locks
 Guaranteeing
Serializability by Two-
Phase Locking
 A transaction is said to follow the two-phase
locking protocol if all locking operations (read_lock,
write_lock) precede the first unlock operation in the
transaction.
 Two phases
 an expanding or growing (first) phase, during
which new locks on items can be acquired but
none can be released.
 a shrinking (second) phase, during which
existing locks can be released but no new locks
can be acquired.
 If every transaction in a schedule follows the two-
phase locking protocol, schedule guaranteed to
be serializable

 Two-phase locking may limit the amount of

concurrency that can occur in a schedule

 Some serializable schedules will be prohibited by

two-phase locking protocol
Guaranteeing Serializability by
Two- Phase Locking
 If lock conversion is allowed

 Then upgrading of locks (from read-locked to

write-locked) must be done during the
expanding phase.
 The downgrading of locks (from write-locked to
read-locked) must be done in the shrinking
phase.

 Transactions T1 and T2 in Figure 21.3(a) do not follow the two-phase

locking protocol because the write_lock(X) operation follows the
unlock(Y) operation in T1, and similarly the write_lock(Y) operation
follows the unlock(X) operation in T2.
Guaranteeing Serializability by
Two- Phase Locking
2-Phase
Locking
----------- END--------------
21.1.3 Dealing with Deadlock
and Starvation
 Dealing with Deadlock and
Starvation
 Deadlock
 Occurs when each transaction T in a set is waiting
for some item locked by some other transaction T′
 Both transactions stuck in a waiting queue
 T1′ is in the waiting queue for X, which is locked
by T2′, whereas T2′ is in the waiting queue for Y,
which is locked by T1′.

Figure 21.5 Illustrating the deadlock problem. (a) A partial schedule of T1′ and T2′ that is
in a state of deadlock. (b) A wait-for graph for the partial schedule in (a).
Dealing with Deadlock and
Starvation (cont’d.)
 Deadlock prevention protocols
 1. Every transaction locks all the items it
needs in advance
 2. Ordering all items in the database
 ordering all the items in the database and making
sure that a transaction that needs several items will
lock them according to that order
 Both approaches impractical
 Transaction timestamp TS(T′), which is a unique
identifier assigned to each transaction.
 Protocols based on a timestamp
 Wait-die
 Wound-wait
Dealing with Deadlock and
Starvation (cont’d.)
 Transaction timestamp TS(T′), which is a unique
identifier assigned to each transaction.
 The timestamps are typically based on the order
in which transactions are started; hence, if
transaction T1 starts before transaction T2, then
TS(T1) < TS(T2).
 Notice that the older transaction (which starts
first) has the smaller timestamp value.
 Two schemes that prevent deadlock based on a
timestamp
 Wait-die
 Wound-wait
Dealing with Deadlock and
Starvation (cont’d.)
 Wait-die
 If TS(Ti) < TS(Tj), then (Ti older than Tj) Ti is
allowed to wait; otherwise (Ti younger than Tj)
abort Ti (Ti dies) and restart it later with the
same timestamp.
 Wound-wait (Opposite)
 If TS(Ti) < TS(Tj), then (Ti older than Tj) abort
Tj (Ti wounds Tj) and restart it later with the
same timestamp; otherwise (Ti younger than
Tj) Ti is allowed to wait.
Dealing with Deadlock and
Starvation (cont’d.)
 No waiting algorithm (NW)
 If transaction unable to obtain a lock, immediately
aborted and restarted later
 Cautious waiting algorithm (CW)
 Deadlock-free
Dealing with Deadlock and
Starvation (cont’d.)
 Deadlock detection
 System checks to see if a state of deadlock exists
 Wait-for graph
 Victim selection
 Deciding which transaction to abort in case of deadlock
 Timeouts
 If system waits longer than a predefined time, it aborts the
transaction
 Starvation
 Occurs if a transaction cannot proceed for an indefinite period of
time while other transactions continue normally
 Solution: first-come-first-served queue
 21.2 Concurrency Control Based
on Timestamp Ordering
 A different approach to concurrency control involves using
transaction timestamps to order transaction execution for
an equivalent serial schedule.
 Timestamp
 Unique identifier assigned by the DBMS to identify a
transaction
 timestamp values are assigned in the order in which
the transactions are submitted to the system,
 Transaction start time
 Concurrency control techniques based on
timestamps do not use locks
 Deadlocks cannot occur
Concurrency Control Based on
Timestamp Ordering (cont’d.)

 Generating timestamps
 Counter incremented each time its value is
assigned to a transaction
 Current date/time value of the system clock
 Ensure no two timestamps are generated during the
same tick of the clock
 General approach
 Enforce equivalent serial order on the transactions
based on their timestamps
Concurrency Control Based
on Timestamp Ordering
(cont’d.)
 Timestamp ordering (TO)
 Allows interleaving of transaction operations
 Must ensure timestamp order is followed for each
pair of conflicting operations
 Each database item assigned two timestamp
values
 read_TS(X)
 write_TS(X)
 CHAPTER 22

Database Recovery Techniques

Introduct
ion
 Recovery algorithms
 Recovery concepts
 Write-ahead logging
 In-place versus shadow updates
 Rollback
 Deferred update
 Immediate update
 Certain recovery techniques best used with
specific concurrency control methods
22.1 Recovery
Concepts
 Recovery process restores database to most
recent consistent state before time of failure
 Information kept in system log
 Typical recovery strategies
 Restore backed-up copy of database
 Best in cases of extensive damage
 Identify any changes that may cause inconsistency
 Best in cases of noncatastrophic failure
 Some operations may require redo
Recovery Concepts
(cont’d.)
 Deferred update techniques
 Do not physically update the database until after
transaction commits
 Undo is not needed; redo may be needed
 Immediate update techniques
 Database may be updated by some operations of
a transaction before it reaches commit point
 Operations also recorded in log
 Recovery still possible
Recovery Concepts
(cont’d.)
 Undo and redo operations required to be
idempotent
 Executing operations multiple times equivalent to
executing just once
 Entire recovery process should be idempotent
 Caching (buffering) of disk blocks
 DBMS cache: a collection of in-memory buffers
 Cache directory keeps track of which database
items are in the buffers
Recovery Concepts
(cont’d.)
 Cache buffers replaced (flushed) to make space
for new items
 Dirty bit associated with each buffer in the cache
 Indicates whether the buffer has been modified
 Contents written back to disk before flush if dirty
bit equals one
 Pin-unpin bit
 Page is pinned if it cannot be written back to disk
yet
Recovery Concepts
(cont’d.)
 Main strategies
 In-place updating
 Writes the buffer to the same original disk location
 Overwrites old values of any changed data items
 Shadowing
 Writes an updated buffer at a different disk location,
to maintain multiple versions of data items
 Not typically used in practice
 Before-image: old value of data item
 After-image: new value of data item
Recovery Concepts
(cont’d.)
 Write-ahead logging
 Ensure the before-image (BFIM) is recorded
 Appropriate log entry flushed to disk
 Necessary for UNDO operation if needed
 UNDO-type log entries
 REDO-type log entries
Recovery Concepts
(cont’d.)
 Steal/no-steal and force/no-force
 Specify rules that govern when a page from the
database cache can be written to disk
 No-steal approach
 Cache buffer page updated by a transaction
cannot be written to disk before the transaction
commits
 Steal approach
 Recovery protocol allows writing an updated buffer
before the transaction commits
Recovery Concepts
(cont’d.)
 Force approach
 All pages updated by a transaction are
immediately written to disk before the transaction
commits
 Otherwise, no-force
 Typical database systems employ a steal/no-
force strategy
 Avoids need for very large buffer space
 Reduces disk I/O operations for heavily updated
pages
Recovery Concepts
(cont’d.)
 Write-ahead logging protocol for recovery
algorithm requiring both UNDO and REDO
 BFIM of an item cannot be overwritten by its after
image until all UNDO-type log entries have been
force-written to disk
 Commit operation of a transaction cannot be
completed until all REDO-type and UNDO-type log
records for that transaction have been force-
written to disk
Transaction Rollback
(22.1.5)
 Transaction failure after update but before
commit
 Necessary to roll back the transaction
 Old data values restored using undo-type log
entries
 Cascading rollback
 If transaction T is rolled back, any transaction S
that has read value of item written by T must also
be rolled back
 Almost all recovery mechanisms designed to avoid
this
Figure 22.1 Illustrating
cascading rollback (a
process that never occurs
in strict or cascadeless
schedules) (a) The read
and write operations of
three transactions (b)
System log at point of
crash (c) Operations
before the crash
22.3 Recovery Techniques
Based on Immediate Update

 Database can be updated immediately

 No need to wait for transaction to reach commit
point
 Not a requirement that every update be immediate
 UNDO-type log entries must be stored
 Recovery algorithms
 UNDO/NO-REDO (steal/force strategy)
 UNDO/REDO (steal/no-force strategy)
Figure 22.3 An example
of recovery using
deferred update with
concurrent transactions
(a) The READ and
WRITE operations of
four transactions (b)
System log at the point
of crash
22.4 Shadow
Paging
 No log required in a single-user environment
 Log may be needed in a multiuser environment for
the concurrency control method
 Shadow paging considers disk to be made of n
fixed-size disk pages
 Directory with n entries is constructed
 When transaction begins executing, directory
copied into shadow directory to save while current
directory is being used
 Shadow directory is never modified
Shadow Paging
(cont’d.)
 New copy of the modified page created and
stored elsewhere
 Current directory modified to point to new disk
block
 Shadow directory still points to old disk block
 Failure recovery
 Discard current directory
 Free modified database pages
 NO-UNDO/NO-REDO technique
Shadow Paging
(cont’d.)

Figure 22.4 An example of shadow paging

End of Module 5