UNIT - IV

TRANSACTION MANAGEMENT
 Transaction Concepts –A Simple Transaction
Model –State diagram of Transaction - Schedules –
Serializability – Concurrency Control– Locking
Protocols – Two Phase Locking Protocol – Deadlock
Handling –Time Stamp Based Protocols - Recovery
System: Failure Classification, Storage, Recovery and
Atomicity, Recovery Algorithm.
Transaction

The term “transaction” refers to a collection of

operations that form a single logical unit of work.

For instance, transfer of money from one account

to another is a transaction consisting of two updates,
one to each account.
 Transaction
“A group of tasks that form a single logical unit”
Example:
 To withdraw 100 from an account

Operations:
 check the account balance

 If sufficient balance is present request for withdrawal.

 Get the money

 Calculate balance = Balance – 100

 Transactions - Process

Read Operation(READ(X))
 To read a database object, it is first brought
into main memory (Local Buffer) from
disk(database), and then its value is copied
into a program variable.
 Transactions - Process

 Read Operation(READ(X))
 Transactions - Process

Write Operation (WRITE(X))

 To write a database object, an in-memory
copy of the object is first modified and then
written to disk (i.e) Transfers the data item x
from the local buffer to the transaction that
executed the write back to the data base.
 Transactions - Process

 Write Operation (WRITE(X))

 ACID Properties
If we want to maintain database consistency, then
certain properties need to be followed in the
transactions known as the ACID
 A – Atomicity
Atomicity means that an entire transaction either takes place
all at once or it doesn’t occur at all. The transactions can never
occur partially.

Every transaction can be considered as a single unit, and they

either run to completion or do not get executed at all.

We have the following two operations here:

—Commit: In case a transaction commits, the changes made are

visible to us. Thus, atomicity is also called the ‘All or nothing
rule’.
—Abort: In case a transaction aborts, the changes made to the
database are not visible to us.
Consider this transaction T that consists of T1 and
T2:

Transferring 100 from account A to account B.

In case the transaction fails when the T1 is completed but the T2 is not
completed (say, after write(A) but before write(B)), then the amount
has been deducted from A but not added to B. This would result in a
database state that is inconsistent.
 C – Consistency
Consistency means that we have to maintain the integrity
constraints so that any given database stays consistent both before
and after a transaction. If we refer to the example discussed above,
then we have to maintain the total amount, both before and after
the transaction.

Total after T occurs = 400 + 300 = 700.

Total before T occurs = 500 + 200 = 700.

Thus, the given database is consistent. Here, an inconsistency

would occur when T1 completes, but then the T2 fails. As a result,
the T would remain incomplete.
I – Isolation
Isolation ensures that multiple transactions can
occur at the same time provided each transaction is
independent and shall not interfere in another
transaction.

Changes in one particular transaction are visible to

any other transaction unless a particular change in
the transaction is written to the memory.
 Let A = 500, B = 500
Let us consider two transactions here- T and T”

Suppose that T has been executed here till Read(B) and then T’’ starts. As a result, the
interleaving of operations would take place. And due to this, T’’ reads the correct value of
A but incorrect value of B.
T’’: (X+B = 50, 000+500=50, 500)
Thus, the sum computed here is not consistent with the sum that is obtained at the end
of the transaction:
T: (A+B = 50, 000 + 450 = 50, 450).
It results in the inconsistency of a database due to the loss of a total of 50 units. The
transactions must, thus, take place in isolation. Also, the changes must only be visible
after we have made them on the main memory.
D – Durability
The durability property states that once the execution
of a transaction is completed, the modifications and
updates on the database gets written on and stored in
the disk.

These persist even after the occurrence of a system

failure. Such updates become permanent and get
stored in non-volatile memory.

Thus, the effects of this transaction are never lost.

Transaction States
Active State
When the instructions of the transaction are running then the
transaction is in active state. If all the ‘read and write’ operations
are performed without any error then it goes to the “partially
committed state”; if any instruction fails, it goes to the “failed
state”.

Partially Committed
After completion of all the read and write operation the changes
are made in main memory or local buffer. If the changes are
made permanent on the DataBase then the state will change to
“committed state” and in case of failure it will go to the “failed
state”.
Failed State
When any instruction of the transaction fails, it goes to the “failed
state” or if failure occurs in making a permanent change of data on
Data Base.

Aborted State
After having any type of failure the transaction goes from “failed
state” to “aborted state” and since in previous states, the
changes are only made to local buffer or main memory and
hence these changes are deleted or rolled-back.
 Committed State
It is the state when the changes are made permanent on the Data
Base and the transaction is complete and therefore terminated in
the “terminated state”.

Terminated State
If there isn’t any roll-back or the transaction comes from the
“committed state”, then the system is consistent and ready for
new transaction and the old transaction is terminated.
 Schedules
 The order in which the operations of multiple transactions appear for execution
is called as a schedule.
Types of Schedules
Serial Schedules
In serial schedules,
All the transactions execute serially one after the other.
When one transaction executes, no other transaction is allowed
to execute.

There are two transactions T1 and

T2 executing serially one after the
other.
Transaction T1 executes first.
After T1 completes its execution,
transaction T2 executes.
So, this schedule is an example of
a Serial Schedule.
There are two transactions T1 and T2
executing serially one after the other.
Transaction T2 executes first.
After T2 completes its execution,
transaction T1 executes.
So, this schedule is an example of
a Serial Schedule.
Non-Serial Schedules
In non-serial schedules,
Multiple transactions execute concurrently.
Operations of all the transactions are inter leaved or mixed with each
other.

There are two transactions T1 and T2

executing concurrently.
The operations of T1 and T2 are
interleaved.
So, this schedule is an example of
a Non-Serial Schedule.
There are two transactions T1 and T2
executing concurrently.
The operations of T1 and T2 are
interleaved.
So, this schedule is an example of
a Non-Serial Schedule.
Recoverable Schedule:

Schedules in which transactions commit only after all

transactions whose changes they read commit are
called recoverable schedules.

In other words, if some transaction Tj is reading value

updated or written by some other transaction Ti, then
the commit of Tj must occur after the commit of Ti.
Example – Consider the following schedule involving
two transactions T1 and T2.
T1 T2 T1 T2

R(X) R(X)
X=X+10 X=X+10
W(X) W(X)
Commit
R(X)
X=X-5 R(X)
W(X) X=X-5
Commit W(X)
Commit

Commit

This is a recoverable schedule since T1 commits before

T2, that makes the value read by T2 correct.
Cascading Schedule:
Also called Avoids cascading aborts/rollbacks (ACA). When there is
a failure in one transaction and this leads to the rolling back or
aborting other dependent transactions, then such scheduling is
referred to as Cascading rollback or cascading abort.
Example:
Cascadeless Schedule:
Strict Schedule
Cascadeless Schedule:
Schedules in which transactions read values only after all
transactions whose changes they are going to read commit are
called cascadeless schedules.

Avoids that a single transaction abort leads to a series of

transaction rollbacks. A strategy to prevent cascading aborts is to
disallow a transaction from reading uncommitted changes from
another transaction in the same schedule.

In other words, if some transaction Tj wants to read value

updated or written by some other transaction Ti, then the
commit of Tj must read it after the commit of Ti.
This schedule is cascadeless. Since the
updated value of A is read by T2 only after
the updating transaction i.e. T1 commits.

It is a recoverable schedule but it does

not avoid cascading aborts. It can be
seen that if T1 aborts, T2 will have to be
aborted too in order to maintain the
correctness of the schedule as T2 has
already read the uncommitted value
written by T1.
Strict Schedule:
A schedule is strict if for any two transactions Ti, Tj, if a write
operation of Ti precedes a conflicting operation of Tj (either read
or write), then the commit or abort event of Ti also precedes
that conflicting operation of Tj.
In other words, Tj can read or write updated or written value of
Ti only after Ti commits/aborts.

This is a strict schedule since T2 reads

and writes A which is written by T1 only
after the commit of T1
Non-Recoverable Schedule:
Example: Consider the following schedule involving two
transactions T1 and T2.

T2 read the value of A written by T1,

and committed. T1 later aborted,
therefore the value read by T2 is
wrong, but since T2 committed, this
schedule is non-recoverable
Note – It can be seen that:
Cascadeless schedules are stricter than recoverable
schedules or are a subset of recoverable schedules.

Strict schedules are stricter than cascadeless

schedules or are a subset of cascadeless schedules.

Serial schedules satisfy constraints of all recoverable,

cascadeless and strict schedules and hence is a subset
of strict schedules.
 Conflict Equivalent Schedule
When either of a conflict operation such as Read-Write or Write-
Read or Write-Write is implemented on the same data item at the
same time within different transactions then the schedule holding
such transactions is said to be a conflict schedule.

The prerequisites for such conflict schedule are:

The conflict operations are to be implemented on the same data

item.
The conflict operations (RW, WR, WW) must take place within
different transactions.
At least one of the conflict operations must be the write
operation.
Two Read operations will not create any conflict.
Two schedules (one being serial schedule and another being non-
serial) are said to be conflict serializable if the conflict operations
in both the schedules are executed in the same order.
Consider 2 schedules, Schedule1 and Schedule2,

Schedule2 (a non-serial schedule) is considered to be conflict serializable

when its conflict operations are the same as that of Shedule1 (a serial
schedule).
 View Equivalent Schedule
Two schedules (one being serial schedule and another being
non-serial) are said to be view serializable if they satisfy the
rules for being view equivalent to one another.

Initial values of the data items involved within a schedule

must be the same.

Final values of the data items involved within a schedule

must be the same.

The number of WR operations performed must be equivalent

for the schedules involved.
 Concurrency Control
Concurrency control refers to the process of managing independent
operations of the database that are simultaneous and considered as
a transaction in DBMS.

Concurrency Control Protocols

Concurrency control protocols are the techniques used to
maintain data consistency, atomicity, Isolation, Durability and
serializability.
Following are some of the concurrency control protocols
1. Lock based
2. Validation based
3. Timestamp based
4. Two-phase protocol
 Lock based Protocols
 Lock based Protocols in simpler terms helps overcome the
issues related to accessing the DBMS concurrently by locking
the current transaction for only one user.
 Lock based protocols when in action, are required to
acquire a lock to access the data items and release the lock
when the trasaction is completed.

Types of Locks in DBMS

The locking and unlocking of data items in Lock based
Protocols in DBMS are implemented in 2 modes:

Shared Lock (lock-S)

Exclusive Lock (lock-X)
 Shared Locks
Often represented as lock-S(),

Shared Locks are basically the locks that grant Read-Only access
to the data items associated with it.

This means when a shared lock is implemented on a database,

it can be READ by multiple users, however, none of the users
reading the data items will be able to update it.

In other words, there is no write access associated with

Shared Lock
Consider a transaction(T1) which requires only to read the data
item value A. The following steps take place when lock protocol is
applied to this traction

T2 will acquire an exclusive lock on the data item A

Read the current value of data item A

Once the transaction is completed, the data item will be unlocked

Exclusive Lock
While Shared Lock allows Read-Only access, Exclusive Locks
allow both Read and Write access on a data item present in the
database.

Often represented as lock-X(),

Exclusive locks provide the privilege of reading and modifying

the data as seen fit by a user.

For the sake of security and consistency of the database, this

process will be exclusive to the user using them and is not
permitted to other users trying to access the same data item.
Consider a transaction(T2) which requires to update the data
item value A. The following steps take place when lock protocol
is applied to this traction
T2 will acquire an exclusive lock on the data item A
Read the current value of data item A
Modify the data item as required. In the example illustrated,
a value of 50 is subtracted from the data item A
Write the updated value of the data item
Once the transaction is completed, the data item will be
unlocked.
Conversion between the locks is possible by the
two methods listed below:

Upgrading: conversion from a read lock to write

lock

Downgrading: conversion from a write lock to

read lock
 Lock Based Protocol
The trivial requirement for a 2PL to exist is that the locking and
unlocking of a transaction take place in either of the 2 phases
i.e. Growing or Shrinking phase

Growing Phase: It is the phase where new locks can be acquired

on the data items.

Shrinking phase: It is the phase where the existing locks on the

data items are released.
The above phases in a DBMS are determined by something
called a ‘Lock Point’. Lock point is the point where a transaction
has achieved its final lock.

It is also the point where the growing phase ends and the
shrinking phase begins.
 Lock Conversion: T1 T2
Lock S(A)
R(A)
Lock S(A)
T1 T2 R (A)
Lock S(B)
R(A) R(A)
R(B)
R(B) R(B) Lock S(B)
R(B)
R(C) Unlock(A)
Unlock(B)

W(A) Lock S(C)

R(C)
Upgrade(A)
W(A)
Types of 2 Phase Locking (PL)
Here are the types of 2 phase locking mention below

1. Conservative 2PL
Conservative or Static 2PL when implied acquires all the locks
before a transaction begins and releases the locks once the
transaction is committed. This kind of 2 PL helps in overcoming
problems related to cascading rollback and deadlocks.

2. Strict 2PL
In this type of 2PL, the exclusive (write) lock is released only after a
transaction is committed, whereas a shared (read) lock can be
released at regular intervals. Though Strict 2PL helps overcome the
cascading rollback issues, it may also cause a bottleneck in some
cases.
3. Strong strict or Rigorous 2PL

In this type of 2PL, both shared and exclusive locks are released
only when the transaction is ended, i.e. when the transaction is
committed or aborted. This kind of 2PL is used in practice today,
promotes serializability and is simpler to implement due to the
strictness involved w.r.t the implementation of the phase endings.
 Timestamp Ordering Protocol
Timestamp is a some numeric value, when a transaction arrives
in a schedule at any time then a timestamp value is assigned to it.

The Timestamp Ordering Protocol is used to order the

transactions based on their Timestamps.

This timestamp value is mostly assign in ascending order.

Example: Suppose there are three transactions T1, T2, T3 and all are executing
parallel on same data say (“A”) as

T1 arrive at time 8:00oC So, assign as timestamp value as 100 called Older

T2 arrive at time 8:10oC So, assign as timestamp value as 200 called Younger

T3 arrive at time 8:15oC So, assign as timestamp value as 300 called Youngest
 The transaction which came first will always execute first. We
can also say the transaction which holds minimum timestamp
value will execute first

Timestamp of any data is denoted by

TS (Ti)

Where TS is timestamp and Ti is transaction number.

Timestamp Types:

Timestamp of any data is of two types

Read timestamp (RTS)
Write timestamp (WTS)
1. Read Timestamp of Data

Timestamp of last (latest) transaction number which performs

the read operation on data (say “A”) successfully is called
Read timestamp.

It is denoted by RTS (“data”) = timestamp-Value.

Example:
RTS (“A”) = 300

As in above diagram T3 is the latest transaction which perform the read

operation. So Read timestamp of data “A” will be the Read timestamp of
least transaction.
2. Write Timestamp of Data

Timestamp of last (latest) transaction number which performs

the write operation on same data successfully is called Write
timestamp.

It is denoted by WTS (Ti) = timestamp-Value

Example: WTS (A) = 200

As in above diagram T2 is the latest transaction which perform the Write

operation on same data “A”. So write timestamp of some data (Say “A)” will
be.
If there are multiple data items in the schedule (i.e. A, B, C…)
then each data item holds its own Read and Write timestamp
as given below

RTS(A) = 300
WTS(A) =200
RTS(B) =100
WTS(B) =100
Timestamp Ordering Protocol Rules

Timestamp follow some rules to perform read or write operation.

The rules are also known as Thomas rules.

Rule No 01 is used when any transaction wants to

perform Read(A) operation
If WTS(A) > TS (Ti), then Ti Rollback
Else (otherwise) execute R(A) operation and SET RTS (A) = MAX
{RTS(A), TS(Ti)}

Rules No.2 is rules is used when a transaction needs to

perform WRITE (A)
If RTS(A) > TS (Ti), then Ti Rollback.
If WTS(A) > TS (Ti), then Ti Rollback.
Else (otherwise) execute W(A) operation and SET WTS (A) = TS(Ti).
Where “A” is some data
 Dead Lock

 Two transactions depend on each other for

something.
A system is in deadlock state if there exists a
set of transactions such that every transaction
in the set is waiting for another transaction.
 Dead Lock

 There are four conditions for a deadlock to

occur
 Mutual exclusive condition
 Hold and wait condition
 No preemption condition
 Circular wait condition
 Dead Lock

 Deadlock Prevention:
 If the resources are allocated in such a way that
deadlock never occur.
 Technique:
 Wait-Die

 Wound-Die
 Dead Lock

 Deadlock Prevention - Wait-Die:

 It allows the older transaction to wait until the
resource is available for execution.
 If T2 holds a lock by some other transaction and T1
is requesting resource held by T2 the following
actions are performed by DBMS.
 Oldest T has highest priority
 Dead Lock

 Deadlock Prevention - Wait-Die:

 Older T wait for newer T (wait)

 Old T1 -> w -> x

 Young T2 -> L -> x

 Younger T rolls back / aborted (Dies)

 Young T1 -> w -> x

 Old T2 -> L -> x

 Dead Lock

 Deadlock Prevention - Wait-Die:

 T1->TS=5, T2->TS=8, T3->TS=10
 T1 needs a resource held by T2
 T3 also needs a resource held by T2.
 T1 is older than T3. Hence T1 is made to wait while
T3 is rolled back.
 Dead Lock
 Deadlock Prevention - Wound-Die:
 Older transaction forces younger one to kill the transaction and
release the resource.
 After some delay, the younger transaction is restarted but with
the same timestamp.
 If the older transaction has held a resource which is requested
by the younger transaction, then the younger transaction is asked
to wait until older releases it.
 Dead Lock

 Deadlock Prevention - Wound-Die:

 T1->TS=5, T2->TS=8, T3->TS=10
 T1 is being older waits and T3 being younger dies.
Wait-Die Wound-wait

Older T needs a data item Older transaction waits Younger transaction dies
held by younger T

Younger T needs a data Younger transaction dies Younger transaction dies

item held by older T
 Dead Lock

 Deadlock Detection:
 An algorithm that examines the state of the system
is invoked periodically to determine whether a
deadlock has occurred or not.
 Deadlock detection is done using wait for graph
method.
 Dead Lock

 Deadlock Detection – Wait For Graph:

 A graph is created based on the transaction and
their lock.
 If the graph has a cycle or closed loop, then there
is a deadlock.
 The graph consists of a pair G=(V,E)
 Dead Lock
 Deadlock Detection – Wait For Graph:

 Rules:
 If T1 has Read operation and then T2 has Write operation then
draw an edge T1->T2
 If T1 has Write operation and then T2 has Read operation then
draw an edge T1->T2
 If T1 has Write operation and then T2 has Write operation then
draw an edge T1->T2
 Dead Lock

 Deadlock Detection – Wait For Graph:

T1 T2
R (A)
R (A)
W (A)
R (B)
W (A)
W (B)
 Dead Lock

 Deadlock Detection – Wait For Graph:

 Step 1: Draw vertices for all the transactions.

T1 T2
 Dead Lock

 Deadlock Detection – Wait For Graph:

 Step 2: Read-Write pair (2)

T1
T2