Chapter-6

Transactions Management, Concurrency and Recovery

INTRODUCTION

Collections of operations that form a single logical unit of work are called transactions.

A database system must ensure proper execution of transactions despite failures -

either the entire transaction executes, or none of it does.

Furthermore, it must manage concurrent execution of transactions in a way that avoids

inconsistency of results.

Example:

a transfer of funds from one account to another account is a single operation from the customer’s
standpoint; within the database system, however, it consists of several operations.

Transaction Definition

A transaction is a unit of program execution that accesses and possibly updates various data
items.

Usually, a transaction is initiated by a user program written in a high-level data-manipulation

language (typically SQL), or programming language (for example, C++, or Java), with embedded
database accesses in JDBC or ODBC.

A transaction is delimited by statements (or function calls) of the form begin transaction and end
transaction.

The transaction consists of all operations executed between the begin transaction and end
transaction.
PROPERTIES OF TRANSACTIONS (ACID PROPERTIES)

1. A (ATOMICITY)

Either all operations of the transaction are reflected properly in the database, or none are.

As a collection of steps, transaction must appear to the user as a single, indivisible unit.

Since a transaction is indivisible, it either executes in its entirety or not at all.

Thus, if a transaction begins to execute but fails for whatever reason, any changes to the database
that the transaction may have made must be undone.

This requirement holds regardless of whether

• the transaction itself failed (for example, if it divided by zero),

• the operating system crashed, or

• the computer itself stopped operating.

2. C (CONSISTENCY)

Execution of a transaction in isolation (that is, with no other transaction executing concurrently)
preserves the consistency of the database.

A transaction must preserve database consistency - if a transaction is run atomically in isolation

starting from a consistent database, the database must again be consistent at the end of the
transaction.

Maintaining consistency in transaction execution is the responsibility of the programmer who

codes a transaction.

3. I (ISOLATION)

Since a transaction is a single unit, its actions cannot appear to be separated by other database
operations not part of the transaction.

Even though multiple transactions may execute concurrently, the system guarantees that, for
every pair of transactions T1 and T2, it appears to T1 that either T2 finished execution before T1
started or T2 started execution after T1 finished. Thus, each transaction is unaware of other
transactions executing concurrently in the system.
Even a single SQL statement involves many separate accesses (read/write) to the database, and a
transaction may consist of several SQL statements.

Therefore, the database system must take special actions to ensure that transactions operate
properly without interference from other concurrently executing database statements.

4. D (DURABILITY)

After a transaction completes successfully, the changes it has made to the database persist, even
if there are system failures.

Even if the system ensures correct execution of a transaction, this serves little purpose if the system
subsequently crashes and, as a result, the system “forgets” about the transaction.

Thus, a transaction’s actions must persist across crashes. This property is referred to as
durability.
TRANSACTION MANAGEMENT

Transaction management component ensures that the database remains in a consistent (correct)
state despite system failures (e.g., power failures and operating system crashes) and transaction
failures.

Concurrency control manager controls the interaction among the concurrent transactions, to
ensure the consistency of the database.

Transaction Model

Consider a simple bank application consisting of several accounts and a set of transactions that
access and update those accounts.

Transactions access data using two operations:

• Read (X) - read operation

it transfers the data item X from the database to a variable, also called X, in a buffer in main
memory belonging to the transaction that executed the read operation.

• Write (X) - write operation

it transfers the value in the variable X in the main-memory buffer of the transaction that executed
the write to the data item X in the database.

Assume that the write operation updates the database immediately.

Example: transaction

Consider an account A with ₹ 950 as balance while account B with ₹ 1050 as balance.

Let T1 be a transaction that transfers ₹ 50 from account A to account B.

The transaction T1 can be defined as:

T1: read(A);
A := A − 50;
write(A);
read(B);
B := B + 50;
write(B).
ACID PROPERTIES

Consistency:

As a consistency requirement, the sum of A and B before an execution of the transaction and
after the execution of the transaction should be unchanged.

For money transfer example, sum of balance in accounts A and B,

• before an execution of the transaction (₹ 950 + ₹ 1050 = ₹ 2000) and

• after the execution of the transaction (₹ 900 + ₹ 1100 = ₹ 2000)

should be unchanged.

Ensuring consistency for an individual transaction is the responsibility of the application

programmer who codes the transaction.

This task may be facilitated by automatic testing of integrity constraints.

Atomicity:

Suppose that, during the execution of transaction T1, a failure occurs that prevents T1 from
completing its execution successfully. Further, suppose that the failure happened after the write(A)
operation but before the write(B) operation.

In this case, the values of accounts A and B reflected in the database are ₹900 and ₹1050 (instead
of ₹900 and ₹1100). The system destroyed ₹50 as a result of this failure.

In particular, we note that the sum A + B is no longer preserved.

Thus, because of the failure, the state of the system no longer reflects a real state of the world that
the database is supposed to capture. We term such a state an inconsistent state. We must ensure
that such inconsistencies are not visible in a database system.

If the atomicity property is present, all actions of the transaction are reflected in the database, or
none are.

Ensuring atomicity is handled by a component of the database called the recovery system.
Durability:

Once the execution of the transaction completes successfully, and the user who initiated the
transaction has been notified that the transfer of funds has taken place, it must be the case that no
system failure can result in a loss of data corresponding to this transfer of funds.

The durability property guarantees that, once a transaction completes successfully, all the
updates that it carried out on the database persist, even if there is a system failure after the
transaction completes execution.

We can guarantee durability by ensuring that either:

• The updates carried out by the transaction have been written to disk before the transaction
completes.

• Information about the updates carried out by the transaction and written to disk is sufficient to
enable the database to reconstruct the updates when the database system is restarted after the
failure.

The recovery system of the database is responsible for ensuring durability.

Isolation:

If several transactions are executed concurrently, their operations may interleave in some
undesirable way, resulting in an inconsistent state.

For example, the database is temporarily inconsistent while the transaction to transfer funds from
A to B is executing, with the deducted total written to A and the increased total yet to be written
to B. If a second concurrently running transaction reads A and B at this intermediate

point and computes A+B, it will observe an inconsistent value. Furthermore, if this second
transaction then performs updates on A and B based on the inconsistent values that it read, the
database may be left in an inconsistent state even after both transactions have completed.

The isolation property of a transaction ensures that the concurrent execution of transactions
results in a system state that is equivalent to a state that could have been obtained had these
transactions executed one at a time in some order.

Ensuring the isolation property is the responsibility of a concurrency-control system.

TRANSACTION STATE DIAGRAM

Partially
Committe
committed d

Initial state Active Terminate Final state

d

Failed Aborted

A transaction starts in the active state.

When it finishes its final statement, it enters the partially committed state.

At this point, the transaction has completed its execution, but it is still possible that it may have to
be aborted, since the actual output may still be temporarily residing in main memory, and thus a
hardware failure may preclude its successful completion.

The database system then writes out enough information to disk that, even in the event of a failure,
the updates performed by the transaction can be re-created when the system restarts after the
failure. When the last of this information is written out, the transaction enters the committed state.

A transaction enters the failed state after the system determines that the transaction can no longer
proceed with its normal execution (for example, because of hardware or logical errors). Such a
transaction must be rolled back. Then, it enters the aborted state.

At this point, the system has two options: restart the transaction or kill the transaction.
CONCURRENT EXECUTIONS

Transaction processing systems usually allow multiple transactions to run concurrently.

There are two reasons for allowing concurrency:

• Improved throughput and resource utilization:

• A transaction consists of many steps. Some involve I/O activity; others involve CPU
activity. The CPU and the disks in a computer system can operate in parallel.
Therefore, I/O activity can be done in parallel with processing at the CPU. This
increases the throughput of the system—that is, the number of transactions executed
in a given amount of time.

• Correspondingly, the processor and disk utilization also increase; that is , the processor
and disk spend less time idle, or not performing any useful work.

• Reduced waiting time for transactions: short transactions need not wait behind long ones.
Moreover, it also reduces the average response time, that is , the average time for a transaction
to be completed after it has been submitted.

Example- Concurrent Executions

SCHEDULES

Schedule is a sequence of instructions that specify the chronological order in which instructions
of concurrent transactions are executed.

• A schedule for a set of transactions must consist of all instructions of those transactions

• Must preserve the order in which the instructions appear in each individual transaction.

• A transaction that successfully completes its execution will have a commit instruction as the
last statement.

• A transaction that fails to successfully complete its execution will have an abort instruction
as the last statement.

Schedule can be either

• Serial

• Concurrent

Example: Serial Schedule

Let T1 and T2 be two transactions that transfer funds from one account to another.

It is defined as:
T1: read(A);
A := A − 50;
write(A);
read(B);
B := B + 50;
write(B).
Transaction T2 transfers 10 percent of the balance from account A to account B.

It is defined as:

T2: read(A);
temp := A * 0.1;
A := A − temp;
write(A);
read(B);
B := B + temp;
write(B).
Schedule-1
Suppose the current values of accounts A and B are ₹1000 and ₹2000, respectively.
Suppose also that the two transactions are executed one at a time in the order T1 followed by T2.
This execution sequence appears as in schedule-1,

The final values of accounts A and B, after the execution T1 and T2 takes place, are ₹855 and
₹2145, respectively. Thus, the total amount of money in accounts A and B, that is, the sum A + B
is preserved after the execution of both transactions.

Schedule 1- a serial schedule in which T1 is followed by T2.

Schedule-2

Similarly, if the transactions are executed one at a time in the order T2 followed by T1, then the
corresponding execution sequence is as in schedule-2,
Again, the sum A + B is preserved, and the final values of accounts A and B are ₹850 and ₹2150,
respectively.

Schedule 2- a serial schedule in which T2 is followed by T1.

These schedules (Schedule-1 & Schedule-2) are serial schedules:

Each serial schedule consists of a sequence of instructions from various transactions, where the
instructions belonging to one single transaction appear together in that schedule.

CONCURRENT SCHEDULE

• When the database system executes several transactions concurrently, the corresponding
schedule no longer needs to be serial.

• If two transactions are running concurrently, the operating system may execute one
transaction for a little while, then perform a context switch, execute the second transaction
for some time, and then switch back to the first transaction for some time, and so on.

• With multiple transactions, the CPU time is shared among all the transactions.

The concurrency-control component of the database system ensures that any schedule that is
executed will leave the database in a consistent state.

Schedule-3: Concurrent Schedule

Suppose that the two transactions T1 and T2 are executed concurrently.

One possible schedule-3 is

Schedule 3 is not a serial schedule.

After this execution takes place, it will give same state as the one in which the transactions are
executed serially in the order T1 followed by T2 (schedule-1).

The sum A + B is indeed preserved.

Schedule 3- a concurrent schedule equivalent to schedule 1.

Schedule-4: Concurrent Schedule with inconsistent state

In Schedules 1, 2 and 3, the sum A + B is preserved. But not all concurrent executions result in a
correct (consistent) state.

Consider a schedule-4 as

After the execution of this schedule, we arrive at a state where the final values of accounts A and
B are ₹950 and ₹2100, respectively.

This final state is an inconsistent state, since we have gained ₹50 in the process of the concurrent
execution.

The sum A + B is not preserved by the execution of the two transactions.

Schedule 4-a concurrent schedule resulting in an inconsistent state.

If control of concurrent execution is left entirely to the operating system, many possible schedules,
including ones that leave the database in an inconsistent state,

such as the one just described, are possible.

The concurrency-control component of the database system carries out this task.

SERIALIZABILITY

We can ensure consistency of the database under concurrent execution by making sure that any
schedule that is executed has the same effect as a schedule that could have occurred without any
concurrent execution. That is, the schedule should, in some sense, be equivalent to a serial
schedule. Such schedules are called serializable schedules.

Different forms of schedule equivalence give rise to the notions of:

1. Conflict serializability

2. View serializability

Simplified view of transactions

We ignore operations other than read and write instructions.

We assume that transactions may perform arbitrary computations on data in local buffers in
between reads and writes.

Our simplified schedules consist of only read and write instructions.

We ignore operations other than read and write instructions.

We assume that transactions may perform arbitrary computations on data in local buffers in
between reads and writes. Our simplified schedules consist of only read and write instructions.

Schedule-3
can be represented as

Schedule 6 - a serial schedule that is equivalent to schedule 1.

CONFLICTING INSTRUCTIONS

Consider a schedule S in which there are two consecutive instructions, instructions I1 and I2, of
transactions T1 and T2 respectively (I1 ≠ I2). If I1 and I2 refer to different data items, then we can
swap I1 and I2 without affecting the results of any instruction in the schedule. However, if I1 and
I2 refer to the same data item Q, then the order of the two steps may matter.

With only read and write instructions, there are four cases that we need to consider:

T1 T2 Conflict or not?
I1 = read(Q) I2 = read(Q) I1 and I2 don’t conflict

I1 = read(Q) I2 = write(Q) I1 and I2 conflict

I1 = write(Q) I2 = read(Q) I1 and I2 conflict

I1 = write(Q) I2 = write(Q) I1 and I2 conflict

Thus, only in the case where both I1 and I2 are read instructions, the order of their execution
does not matter.

Thus, I1 and I2 conflict if they are instructions in different transactions on the same data item,
and at least one of these instructions is a write operation.

In Schedule-3

The write(A) instruction of T1 conflicts with the read(A) instruction of T2 as they are instructions
in different transactions on the same data item, and one of these instructions is a write
operation.
However, the write(A) instruction of T2 does not conflict with the read(B) instruction of T1,
because the two instructions access different data items.

NONCONFLICTING INSTRUCTIONS

Let I1 and I2 be consecutive instructions of a schedule S.

If I1 and I2 are instructions of different transactions and I1 and I2 do not conflict, then we can swap
the order of I1 and I2 to produce a new schedule S’.

S is equivalent to S’, since all instructions appear in the same order in both schedules except for
I1 and I2, whose order does not matter.

In Schedule-3

Since the write(A) instruction of T2 in schedule-3 does not conflict with the read(B) instruction
of T1, we can swap these instructions to generate an equivalent schedule, schedule-5.

Schedule-3 is equivalent schedule-5 and both produce the same final system state.

We continue to swap nonconflicting instructions:

• Swap the read(B) instruction of T1 with the read(A) instruction of T2.

• Swap the write(B) instruction of T1 with the write(A) instruction of T2.

• Swap the write(B) instruction of T1 with the read(A) instruction of T2.

The final result of these swaps, schedule 6 is a serial schedule (same as schedule-1)

CONFLICT EQUIVALENT SCHEDULES

If a schedule S can be transformed into a schedule S’ by a series of swaps of non-conflicting

instructions, we say that S and S’ are conflict equivalent.

Schedule 3 and Schedule 5 are conflict equivalent.

Schedule 3

Schedule 5
CONFLICT SERIALIZABLE SCHEDULE

The concept of conflict equivalence leads to the concept of conflict serializability.

We say that a schedule S is conflict serializable if it is conflict equivalent to a serial schedule.

Thus, schedule-3 is conflict serializable, since it is conflict equivalent to serial schedule-1.

schedule-3

Schedule-1
VIEW SERIALIZABLE SCHEDULE

The concept of view equivalence leads to the concept of view serializability.

We say that a schedule S is view serializable if it is view equivalent to a serial schedule.

Every conflict serializable schedule is also view serializable.

Precedence graph

Precedence graph is simple and efficient method for determining conflict serializability of a
schedule.

Consider a schedule S.

We construct a directed graph, called a precedence graph, from schedule S.

This graph consists of a

pair G = (V, E),

where

V is a set of vertices and

E is a set of edges.

The set of vertices consists of all the transactions participating in the schedule.

Example - precedence graph

schedule-1 is as shown below,

The precedence graph for schedule-1 is,

Above precedence graph contains the single edge T1 → T2, since all the instructions of T1 are
executed before the first instruction of T2 is executed.

schedule-2 is as shown below

The precedence graph for schedule-2 is

Above precedence graph shows the precedence graph for schedule 2 with the single edge T2 →
T1, since all the instructions of T2 are executed before the first instruction of T1 is executed.

Schedule-4 is as shown below

The precedence graph for schedule-4 is

The precedence graph contains the edge T1 →T2, because T1 executes read(A) before T2 executes
write(A). It also contains the edge T2→T1, because T2 executes read(B) before T1 executes
write(B).
TESTING FOR SERIALIZABILITY

If the precedence graph for S has a cycle, then schedule S is not conflict serializable.

If the graph contains no cycles, then the schedule S is conflict serializable.

For example, the precedence graph for schedule-4 as shown below and has a cycle,

then schedule-4 is said to be not conflict serializable schedule.

LOCK-BASED PROTOCOLS

One way to ensure isolation is to require that data items be accessed in a mutually exclusive
manner; that is, while one transaction is accessing a data item, no other transaction can
modify that data item.

The most common method used to implement this requirement is to allow a transaction to access
a data item only if it is currently holding a lock on that item.

Locks

A lock is a mechanism to control concurrent access to a data item.

Data items can be locked in two modes:

1. Shared mode- (denoted by S)

If a transaction T1 has obtained a shared-mode lock on item Q, then T1 can read,

but cannot write, Q.

Shared lock is requested using lock-S instruction.

2. Exclusive - (denoted by X)

If a transaction T1 has obtained an exclusive-mode lock on item Q, then T1 can both

read and write Q.

Exclusive lock is requested using lock-X instruction.

 Command unlock(X) is used to free data item X from locking.

The use of these two lock modes allows multiple transactions to read a data item but limits
write access to just one transaction at a time.

Every transaction request a lock in an appropriate mode on data item Q, depending on the types
of operations that it will perform on Q.

The transaction makes the request to the concurrency-control manager.

The transaction can proceed with the operation only after the concurrency-control manager grants
the lock to the transaction.

Banking Example- Lock-Based Protocols

Let A and B be two accounts that are accessed by transactions T1 and T2.

Transaction T1 transfers ₹50 from account B to account A.

Transaction T2 displays the total amount of money in accounts A and B that is, sum (A + B).

Suppose that the values of accounts A and B are ₹100 and ₹200, respectively. If these two
transactions are executed serially, either in the order T1, T2 or the order T2, T1, then transaction
T2 will display the value ₹300.
CONCURRENCY CONTROL

Concurrency Control schemes to ensure isolation of transactions are:

• Lock-based protocols,

• Timestamp-based protocols

TWO-PHASE LOCKING PROTOCOL

Two-Phase Locking Protocol ensures conflict-serializable schedules.
In this protocol, each transaction issues lock and unlock requests in two phases:
1. Growing phase - A transaction may obtain locks, but may not release any lock.
2. Shrinking phase - A transaction may release locks, but may not obtain anynew locks.
• Initially, a transaction is in the growing phase.
• The transaction acquires locks as needed.
• Once the transaction releases a lock, it enters the shrinking phase, and it can issue no
more lock requests.

In any transaction, the point in the schedule where the transaction has obtained its final lock (the
end of its growing phase) is called the lock point of the transaction.

Growing phase lock point

Shrinking phase
Locks

The transactions can be ordered

Time according to their lock points - this ordering is, in fact, a
serializability ordering for the transactions.
For example,
 Transactions T3 and T4 are two phase because they have followed growing and shrinking phase
locking and unlocking.

Types of Two-Phase Locking Protocol

• Strict two-phase locking:
A transaction must hold all its exclusive locks till it commits/aborts.
Ensures recoverability and avoids cascading roll-backs.
• Rigorous two-phase locking:
A transaction must hold all locks till commit/abort.
Transactions can be serialized in the order in which they commit.
Most databases implement rigorous two-phase locking.
Implementation of Locking
• A lock manager can be implemented as a separate process.
• Transactions can send lock and unlock requests as messages.
• The lock manager replies to a lock request by sending a lock grant messages (or a message
asking the transaction to roll back, in case of a deadlock).
• The requesting transaction waits until its request is answered.
• The lock manager maintains an in-memory data-structure called a lock table to record granted
locks and pending requests.

Lock Table

Dark rectangles indicate granted locks while light colored ones indicate waiting requests.
Lock table records the type of lock (exclusive or shared) granted or requested.
New request is added to the end of the queue of requests for the data item, and granted if it is
compatible with all earlier locks.
Unlock requests result in the request being deleted, and later requests are checked to see if they
can now be granted.
If transaction aborts, all waiting or granted requests of the transaction are deleted.

TIMESTAMP-BASED PROTOCOLS
A timestamp-ordering is a method for determining the serializability order to select an ordering
among transactions in advance.
Timestamps
With each transaction T1 in the system, we associate a unique fixed timestamp, denoted by TS
(T1). This timestamp is assigned by the database system before the transaction T1 starts execution.
If a transaction T1 has been assigned timestamp TS(T1 ), and a new transaction T2 enters the
system, then TS(T1 ) < TS(T2) that is, T1 is older than T2.
Thus, if TS(T1 ) < TS(T2), then the system must ensure that the produced schedule is equivalent
to a serial schedule in which transaction T1 appears before transaction T2 .

To implement this scheme, we associate with each data item Q, two timestamp values:
• W-timestamp(Q) denotes the largest timestamp of any transaction that executed write(Q)
successfully.
• R-timestamp(Q) denotes the largest timestamp of any transaction that executed read(Q)
successfully.
These timestamps are updated whenever a new read(Q) or write(Q) instruction is executed.

Timestamp-based protocols manage concurrent execution such that time-stamp order =

serializability order
There are two simple methods for implementing this scheme:
1. Use the value of the system clock as the timestamp; that is, a transaction’s timestamp is equal
to the value of the clock when the transaction enters the system.
2. Use a logical counter that is incremented after a new timestamp has been assigned; that is, a
transaction’s timestamp is equal to the value of the counter when the transaction enters the
system.
The timestamp-ordering protocol ensures conflict serializability.
This is because conflicting operations are processed in timestamp order and the arcs in the
precedence graph are as:

Transaction Transaction
with smaller with larger
timestamp timestamp

The protocol ensures freedom from deadlock, since no transaction ever waits.

DEADLOCK
A system is in a deadlock state if there exists a set of transactions such that every transaction
in the set is waiting for another transaction in the set.
If there exists a set of waiting transactions {T0, T1, . . . , Tn} such that T0 is waiting for a data
item that T1 holds, and T1 is waiting for a data item that T2 holds, and . . . , and Tn−1 is waiting
for a data item that Tn holds, and Tn is waiting for a data item that T0 holds.
None of the transactions can make progress in such a situation.

The only remedy to this undesirable situation is for the system to invoke some drastic action, such
as rolling back some of the transactions involved in the deadlock.
Rollback of a transaction may be partial: that is, a transaction may be rolled back to the point
where it obtained a lock whose release resolves the deadlock.

DEADLOCK HANDLING
There are two principal methods for dealing with the deadlock problem.
• deadlock prevention
• deadlock detection and deadlock recovery

Deadlock Prevention Protocol:

It ensures that the system will never enter a deadlock state.

Deadlock Detection and Deadlock Recovery:

Allows the system to enter a deadlock state, and then try to recover.

Prevention is commonly used if the probability that the system would enter a deadlock state is
relatively high; otherwise, detection and recovery are more efficient.
DEADLOCK PREVENTION

There are two approaches to deadlock prevention.

• One approach ensures that no cyclic waits can occur by ordering the requests for locks, or
requiring all locks to be acquired together.
• Each transaction locks all its data items before it begins execution.

The other approach is to perform transaction rollback whenever the wait could potentially result
in a deadlock.

PREEMPTION AND TRANSACTION ROLLBACK APPROACH

The second approach for preventing deadlocks is to use preemption and transaction rollbacks.

In preemption, when a transaction T2 requests a lock that transaction T1 holds, the lock granted to
T1 may be preempted by rolling back of T1, and granting of the lock to T2.

To control the preemption, we assign a unique timestamp, based on a counter or on the system
clock, to each transaction when it begins. The system uses these timestamps only to decide
whether a transaction should wait or roll back.

If a transaction is rolled back, it retains its old timestamp when restarted.

DEADLOCK PREVENTION SCHEMES

Two different deadlock-prevention schemes using timestamps are:

• wait–die

• wound–wait

• Another approach is lock timeouts.

WAIT–DIE SCHEME

The wait–die scheme is a non-preemptive technique.

• When transaction T1 requests a data item currently held by T2 , T1 is allowed to wait only
if it has a timestamp smaller than that of T2 (that is, T1 is older than T2 ). Otherwise, T1
is rolled back (dies).

Example:

Transactions T1, T2, and T3 have timestamps 5, 10, and 15, respectively.
If T1 requests a data item held by T2, then T1 will wait. (smaller timestamp).

If T3 requests a data item held by T2, then T3 will be rolled back. (larger timestamp).

WOUND–WAIT SCHEME

The wound–wait scheme is a preemptive technique & counterpart to the wait–die scheme.

• When transaction T1 requests a data item currently held by T2 , T1 is allowed to wait only
if it has a timestamp larger than that of T2 (that is, T1 is younger than T2 ). Otherwise, T2
is rolled back (T2 is wounded by T1 ).

Example:

Transactions T1, T2, and T3 have timestamps 5, 10, and 15, respectively.

If T1 requests a data item held by T2, then the data item will be preempted from T2, and T2 will
be rolled back (wound).

If T3 requests a data item held by T2, thenT3 will wait.

The major problem with both of these schemes is that unnecessary rollbacks may occur.

LOCK TIMEOUTS SCHEME

Another simple approach to deadlock prevention is based on lock timeouts.

In this approach, a transaction that has requested a lock waits for at most a specified amount of
time. If the lock has not been granted within that time, the transaction is said to time out, and it
rolls itself back and restarts.

If there was in fact a deadlock, one or more transactions involved in the deadlock will time out
and roll back, allowing the others to proceed.

DEADLOCK DETECTION AND RECOVERY

If a system does not employ some protocol that ensures deadlock freedom, then a detection and
recovery scheme must be used.

An algorithm that examines the state of the system is invoked periodically to determine whether
a deadlock has occurred.

If one has, then the system must attempt to recover from the deadlock.

To recover from the deadlock, the system must:

 • Maintain information about the current allocation of data items to transactions, as well
as any outstanding data item requests.

• Provide an algorithm that uses this information to determine whether the system has
entered a deadlock state.

• Recover from the deadlock when the detection algorithm determines that a deadlock
exists.

DEADLOCK DETECTION

Deadlocks in the system can be represented as directed graph called as wait-for graph.

This graph consists of a pair G = (V, E) where

V is a set of vertices and

E is a set of edges.

The set of vertices consists of all the transactions in the system.

The wait-for graph for transactions T1 and T2 with edge between them can be represented as

DEADLOCK DETECTION WITH WAIT-FOR GRAPH

Each element in the set E of edges is an ordered pair as T1 → T2.

If T1 → T2 is in set E, then there is a directed edge from transaction T1 to T2 , implying that

transaction T1 is waiting for transaction T2 to release a data item that it needs.
Example: wait-for graph
When transaction T1 requests a data item currently being held by transaction T2, then the edge T1
→ T2 is inserted in the wait-for graph and This edge is removed only when transaction T2 is no
longer holding a data item needed by transaction T1.
A deadlock exists in the system if and only if the wait-for graph contains a cycle.
Each transaction involved in the cycle is said to be deadlocked.
To detect deadlocks, the system needs to maintain the wait-for graph, and periodically to invoke
an algorithm that searches for a cycle in the graph.
A deadlock exists in the system if and only if the wait-for graph contains a cycle.
Each transaction involved in the cycle is said to be deadlocked.
To detect deadlocks, the system needs to maintain the wait-for graph, and periodically to invoke
an algorithm that searches for a cycle in the graph.
Consider the wait-for graph with transactions T1, T2, T3 & T4 as

T2 T3

T1

T4

The graph depicts the following situation:

• Transaction T1 is waiting for transactions T2 and T4.
• Transaction T4 is waiting for transaction T2.
• Transaction T2 is waiting for transaction T3.

Since the graph has no cycle, the system is not in a deadlock state.

Suppose now that transaction T3 is requesting an item held by T4. The edge T3 → T4 is added
to the wait-for graph, resulting in the new system state in figure as,

T2 T3

T1

T4

The graph depicts the following situation:

• Transaction T2 is waiting for transactions T3.
• Transaction T3 is waiting for transaction T4.
• Transaction T4 is waiting for transaction T2.

This time, the graph contains the cycle: T2 →T3 →T4 →T2.
Thus, transactions T2, T3, and T4 are all deadlocked.

RECOVERY FROM DEADLOCK

When a detection algorithm determines that a deadlock exists, the system must recover from
the deadlock.

The most common solution is to roll back one or more transactions to break the deadlock. Three
actions need to be taken:

1. Selection of a victim

2. Rollback

3. Starvation

1. SELECTION OF A VICTIM -

Given a set of deadlocked transactions, we must determine which transaction (or transactions) to
roll back to break the deadlock.

We should roll back those transactions that will incur the minimum cost.

Many factors may determine the cost of a rollback, including:

• How long the transaction has computed, and how much longer the transaction will compute
before it completes its designated task.

• How many data items the transaction has used.

• How many more data items the transaction needs for it to complete.

• How many transactions will be involved in the rollback.

2. ROLLBACK-

Once we have decided that a particular transaction must be rolled back, we must determine how
far this transaction should be rolled back.

There are two ways:

• total rollback

• partial rollback

1. Total rollback: It is simplest solution. It aborts the transaction and then restart it.
2. Partial rollback: It rolls back the transaction only as far as necessary to break the deadlock.

Such partial rollback requires the system to maintain additional information about the state of
all the running transactions.

Specifically, the sequence of lock requests/grants and updates performed by the transaction
needs to be recorded.

The deadlock detection mechanism should decide which locks the selected transaction needs to
release in order to break the deadlock.

The selected transaction must be rolled back to the point where it obtained the first of these locks,
undoing all actions it took after that point.

The recovery mechanism must be capable of resuming execution after a partial rollback.

3. STARVATION-

In a system where the selection of victims is based primarily on cost factors, it may happen that
the same transaction is always picked as a victim.

As a result, this transaction never completes its designated task, thus there is starvation.

We must ensure that a transaction can be picked as a victim only a (small) finite number of times.

The most common solution is to include the number of rollbacks in the cost factor.

RECOVERY SYSTEM (FROM FAILURE)

A computer system is subject to failure from a variety of causes:

• disk crash,

• power outage,

• software error,

• any miss-happening in the machine room, or

• any intentional act of disruption.

• In any failure, information may be lost. Therefore, the database system must take actions
in advance to ensure that the atomicity and durability properties of transactions are
preserved.
 • An integral part of a database system is a recovery scheme that can restore the database to
the consistent state that existed before the failure.

• The recovery scheme must also provide high availability; that is, it must minimize the
time for which the database is not usable after a failure.

Failure Classification

Following are the various types of failure that may occur in a system:

1. Transaction failure -

There are two types of errors that may cause a transaction to fail:

• Logical error-

The transaction can no longer continue with its normal execution because of some internal
condition, such as bad input, data not found, overflow, or resource limit exceeded.

• System error-

The system has entered an undesirable state (for example, deadlock), as a result of which a
transaction cannot continue with its normal execution. The transaction, however, can be re-
executed at a later time.

2. System crash-

• There is a hardware malfunction, or a bug in the database software or the operating

system, that causes the loss of the content of volatile storage, and brings transaction processing
to a halt.

The content of nonvolatile storage remains intact, and is not corrupted.

3. Disk failure-

• A disk block loses its content as a result of either a head crash or failure during a data-
transfer operation.

• Copies of the data on other disks, or archival backups on tertiary media, such as DVD or tapes,
are used to recover from the failure.
STORAGE STRUCTURE

The various data items in the database may be stored and accessed in a number of different
storage media.

The different storage media can be distinguished by their relative speed, capacity, and resilience
to failure.

There are three categories of storage:

1. Volatile storage

2. Non-volatile storage

3. Stable storage

Stable storage plays a critical role in recovery algorithms.

Categories of storage media

1. Volatile storage:

• Does not survive system crashes

• Examples: main memory, cache memory

2. Nonvolatile storage:

• Survives system crashes

• Examples: disk, tape, flash memory, non-volatile RAM

• But may still fail, losing data

3. Stable storage:

• A mythical form of storage that survives all failures

• To implement stable storage, we need to replicate the needed information in several

nonvolatile storage media (usually disk) with independent failure modes, and to update the
information in a controlled manner to ensure that failure during data transfer does not damage
the needed information.
RECOVERY ALGORITHMS

• Suppose transaction T1 transfers ₹50 from account A to account B.

• It requires two updates-

• subtract ₹50 from account A and

• add ₹50 to account B.

• Transaction T1 requires updated values of A and B will be the output of database.

• A failure may occur after one of these modifications have been made but before both of
them are made permanent.

• Modifying the database without ensuring that the transaction will commit, may leave the
database in an inconsistent state.

• Not modifying the database may result in lost updates if failure occurs just after
transaction commits.

Recovery algorithm has two parts-

1. Actions taken during normal transaction processing to ensure enough information exists to
recover from failures.

2. Actions taken after a failure to recover the database contents to a state that ensures atomicity,
consistency and durability.

RECOVERY TECHNIQUES

There are two recovery techniques as

• Shadow-paging

• Log based recovery

SHADOW COPY & SHADOW PAGING

Shadow-copy scheme:

In the shadow-copy scheme, a transaction that wants to update the database first creates a
complete copy of the database. All updates are done on the new database copy, leaving the
original copy, the shadow copy, untouched.
If at any point the transaction has to be aborted, the system merely deletes the new copy. The
old copy of the database has not been affected.

The current copy of the database is identified by a pointer, called db-pointer, which is stored on
disk.

If the transaction partially commits (that is, executes its final statement), it is committed as
follows:

• First, the operating system is asked to make sure that all pages of the new copy of the database
have been written out to disk.

• After the operating system has written all the pages to disk, the database system updates the
pointer db-pointer to point to the new copy of the database; the new copy then becomes
the current copy of the database.

• The old copy of the database is then deleted.

• The transaction is said to have been committed at the point where the updated db-pointer is
written to disk.

Shadow copy schemes are commonly used by text editors (saving the file is equivalent to
transaction commit, while quitting without saving the file is equivalent to transaction abort).

Shadow copying can be used for small databases, but copying a large database would be
extremely expensive.

Shadow copy
Shadow Paging

A variant of shadow copying, called shadow-paging, reduces copying as follows:

• The scheme uses a page table containing pointers to all pages; the page table itself and
all updated pages are copied to a new location.

• Any page which is not updated by a transaction is not copied, but instead the new page
table just stores a pointer to the original page.

• When a transaction commits, it atomically updates the pointer to the page table, which
acts as db-pointer, to point to the new copy.

• Shadow paging unfortunately does not work well with concurrent transactions and is not
widely used in databases.

Shadow Paging can be illustrated as

LOG BASED RECOVERY

Log or Log records:

The most widely used structure for recording database modifications is the log.

The log is a sequence of log records, recording all the update activities in the database.

An update log record describes a single database write.

An update log record has following fields:
• Transaction identifier, which is the unique identifier of the transaction that performed
the write operation.
• Data-item identifier, which is the unique identifier of the data item written. Typically,
it is the location on disk of the data item, consisting of the block identifier of the block on
which the data item resides, and an offset within the block.
• Old value, which is the value of the data item prior to the write.
• New value, which is the value that the data item will have after the write.

An update log record is represented as

< Ti, Xj, V1, V2 >

Log record indicates that Transaction Ti has performed a write operation on data item Xj ,
where V1 is the value before the write, and V2 is the value after the write.

Other types of special log records are:

• <Ti start> - Transaction Ti has started.

• <Ti commit> - Transaction Ti has committed.
• <Ti abort> - Transaction Ti has aborted.
Database log corresponding to transactions T0 and T1 can be shown as
Whenever a transaction performs a write, it is essential that the log record for that write be created
and added to the log, before the database is modified.

Once a log record exists, we can output the modification to the database if that is desirable.

RECOVERY AND ATOMICITY

When a DBMS recovers from a crash, it should maintain the following -
• It should check the states of all the transactions, which were being executed.
• A transaction may be in the middle of some operation; the DBMS must ensure the
atomicity of the transaction in this case.
• It should check whether the transaction can be completed now or it needs to be rolled
back.
No transactions would be allowed to leave the DBMS in an inconsistent state.
MAINTAINING ATOMICITY OF TRANSACTION
There are two types of techniques, which can help a DBMS in recovering as well as maintaining
the atomicity of a transaction -
• Maintaining the logs of each transaction, and writing them onto some stable storage
before actually modifying the database.
• Maintaining shadow paging, where the changes are done on a volatile memory, and later,
the actual database is updated.
CHECKPOINTS
When a system crash occurs, we must consult the log to determine those transactions
that need to be redone and those that need to be undone.
In principle, we need to search the entire log to determine this information.
There are two major difficulties with this approach:
1. The search process is time-consuming.
2. Most of the transactions that, according to 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.
To reduce these types of overhead, we introduce checkpoints.

A checkpoint is performed as follows:

1. Output onto stable storage all log records currently residing in main memory.
2. Output to the disk all modified buffer blocks.
3. Output onto stable storage a log record of the form <checkpoint L>,
where L is a list of transactions active at the time of the checkpoint.
Transactions are not allowed to perform any update actions, such as writing to a buffer block
or writing a log record, while a checkpoint is in progress.

RECOVERY WITH CHECKPOINTS

The presence of a <checkpoint L> record in the log allows the system to streamline its recovery
procedure.
Example:
Consider a transaction Ti that completed prior to the checkpoint. For such a transaction, the <Ti
commit>record (or < Ti abort> record) appears in the log before the <checkpoint> record.
Any database modifications made by Ti must have been written to the database either prior to
the checkpoint or as part of the checkpoint itself.
Thus, at recovery time, there is no need to perform a redo operation on Ti .
After a system crash has occurred, the system examines the log to find the last <checkpoint
L> record (this can be done by searching the log backward, from the end of the log, until the first
<checkpoint L> record is found).

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> and <Tn, Commit> or just <Tn,
Commit>, it puts the transaction in the 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.
Example-Recovery with checkpoints

In case of recovery above system behaves in the following manner −

▪ Transaction T1 can be ignored (updates already output to disk due to checkpoint)
▪ Transactions T2 and T3 redone (redo sets data item specified to the new value).
▪ Transaction T4 undone (undo sets data item specified to the old value).

Reference: Database System Concepts, Abraham Silberschatz, Henry F. Korth, S. Sudarshan,

Sixth Edition Mcgraw-Hill Publication