Database Transaction

Management
Guest Lecture by Prof. Nitin M Shivale (Asst. Prof)

Venu : Ajeenkya D Y Patil School of Engineering Lohegaon Pune

Introduction to Database Transaction, Transaction states, ACID properties,

Concept of Schedule, Serial Schedule. Serializability: Conflict and View,
Cascaded Aborts, Recoverable and Non Recoverable Schedules. Concurrency
Control: Lock-based, Time-stamp based Deadlock handling. Recovery methods:
Shadow-Paging and Log-Based Recovery, Checkpoints. Log-Based Recovery:
Deferred Database Modifications and Immediate Database Modifications.
Introduction to Database Transaction:
❖ Db Transaction : Fundamental concept representing a set of logically related
operations executed as a Single unit.
❖ . To access data from
the db various
❖ . operation performed
User on db
❖ .
made a
❖ . request Database

❖ .
❖ .
❖ Why do we required Transactions?
❖ Transactions are essential for handling user requests to access and modify
database contents, ensuring the database remains consistent and reliable
despite various operations and potential interruptions.
Operation of Transactions:
DB
1. Read(X):
Computer
Operation
User Main Memory
Request (buffer) Bal =10
bal = 10 Read(bal)

Bal = 110
2. Write(X): bal = bal + 100; Write(bal)

3. Commit: Changes made by transaction permanently to the database.

4. Rollback: Performed to bring the database to the last saved state when any
transaction is interrupted in between due to any power, hardware, or software
failure.
Transaction Schedule:
Q. Why there is a need of transaction schedule?

→ When multiple transaction requests are made at the same time,

we need to decide their order of execution. Thus, a transaction
schedule can be defined as a chronological order of execution of
multiple transactions.
Two types of transactions schedule:
1. Serial Schedule:
2. Non -Serial Schedule:
Types of Schedule:
SCHEDULE
.

SERIAL PARALLEL / NON-SERIAL

SERIALIZABLE NON - SERIALIZABLE

CONFLICT VIEW NON

SERIALIZABLE RECOVERABLE
SERIALIZABLE RECOVERABLE

Cascading Cascadeless
Strict Schedule
Schedule Schedule
Serial Schedule:
Q. what is serial schedule?
Ans: When more than one transactions are to be executed, they are executed serially, i.e. at one time
only one transaction is executed while others wait for the execution of the current transaction to be
completed. This ensures consistency in the database as transactions do not execute simultaneously.
Serial Schedule: Schedule 1
Example:
Let’s Say in Schedule 1 there are two transactions T1 and T2. T1→T2 read as T1
followed by T2 means once T1 transaction complete then only T2 transaction start
executing.
Now let T1 transfer Rs. 100 from
account A to account B.

T2 transfer 20% of the balance

from account A to account B.

Write down the serial schedule

for above transactions.
Non-Serial Schedule:
Q. what is Non-Serial schedule?
Ans:To reduce the waiting time of transactions in the waiting queue and improve the
system efficiency, we use nonserial schedules which allow multiple transactions to
start before a transaction is completely executed. This may sometimes result in
inconsistency and errors in database operation.
● So, these errors are handled with specific
algorithms to maintain the consistency of the
database and improve processor throughput
as well.
● There are many possible orders or schedules.
● Transactions are executed in interleaved
manner
Transaction States:
. Permanent
Store
Partially Committed
Read/ Write committed State State
Operation

Failure Terminated
Active State State

Failure Rollback
Aborted
Failed State State
Transaction States:
1. Active State: First stage of transaction, Data is in buffer
2. Partially Committed State: Without error / With error
3. Committed State: T successfully executed with commit operation
4. Failed State: if error in Active and Partially committed state.
5. Aborted State: if the error is not resolved in failed state.
6. Terminated State: Last state of transaction.
ACID Properties:
As transactions deal with accessing and modifying the contents of the
database, they must have some basic properties which help maintain the
consistency and integrity of the database before and after the
transaction. Transactions follow 4 properties, namely, Atomicity,
Consistency, Isolation, and Durability.

1. Atomicity: Considering each transaction as a single unit (atomic

unit). Transaction all operations either executed completely or not at
all. It is achieved through commit or rollback operation.
ACID Properties:
2. Consistency: This property of a transaction maintain the database
consistent before and after a transaction is completed. After applying a
logical operation on database it must be in consistent state.

3. Isolation: This property states that two transactions must not

interfere or mixed with each other, i.e. if some data is used by a
transaction for its execution, then any other transaction can not
concurrently access that data until the first transaction has completed.
ACID Properties:
4. Durability: This property of a transaction ensures that all changes
in the database made by a committed transaction are permanent.

How are the ACID Properties achieved.

1. Atomicity: achieved through Recovery System.

2. Consistency: achieved through Programmer + DBMS
3. Isolation: achieved through Concurrency Control.
4. Durability: achieved through Recovery System.
Serializable:
● Serializability in DBMS is the property of a non serial schedule that determines
whether it would maintain the database consistency or not.
● The non serial schedule which ensures that the database would be consistent after
the transactions are executed in the order determined by that schedule is said to be
Serializable Schedules.
● The serial schedules always maintain database consistency as a transaction starts
only when the execution of the other transaction has been completed under it.
● Thus, serial schedules are always serializable.
● In case of parallel schedules to make it serializable we have to find clone of it which is
serial. For eg: if there are 3 Transactions there is 3! Possibilities to make it serial.
Serializable:
. T1 T2 T3 To check either this non serial schedule is
serializable or not we have to go with 3!
R(A)
Possibilities to check equivalent serial schedule.
R(B)
1. T1→T2→T3
R(B)
2. T1→T3→T2
W(B) 3. T2→T1→T3
W(A) 4. T2→T3→T1
5. T3→T1→T2
W(A) 6. T3→T2→T1
R(A)
Once we find conflict serializability and its
W(A)
precedence graph we are able to find serial
sequence schedule.
Conflict and Non Conflict operation pairs:
Q. We have given a non serial schedule now
.No Conflict Pairs Conflict Pairs you have to find out conflict equivalent
T1 T2 T1 T2 schedule S = S’.
or
R(A) R(A) R(A) W(A)
We have given schedules and you told that you
W(B) R(A) W(A) R(A) have to check either given schedule is conflict
equivalent or not.
R(B) R(A) W(A) W(A)
T1 T2
T1 T2
R(B) W(A)
R(A)
Steps: R(A)
W(A) W(B) 1. Compare W(A)
W(A)
adjacent pair if not
R(B)
conflict swap. Else R(A)
dont swap. W(A)
R(A)
2. Will get conflict
W(A)
equivalent (y/n) ans R(B)
Serializable:
.
Conflict Serializability:
A schedule is called conflict serializable if after swapping
of non-conflict operations, it can transform into serial
schedule. The schedule will be a conflict serializable if it is
conflict equivalent to a serial schedule.
T1 T2 T1 T2 T1 T2 T1 T2

R(A) R(A) R(A) Conflict equivalent to a R(A)

Serial schedule.
W(A) W(A) W(A) W(A)

R(A) R(A) R(B) Conflict Operation: R(B)

R–W
W(A) R(B) R(A) R(A)
W–R
R(B) W(A) W(A) W–W W(A)
Conflict Serializability:
Example: Find out following schedule S is conflict serializable or not.
T1 T2 T3 3 1. Check conflict pairs in other
T1 T2 transactions & draw lines. [
R(X) (R-W)/(W-R)/(W-W) ]
2. If there is no conflict operation
R(Y) 1 2
T3 simply strike that operation and move
R(X) next.
3. If line is present already then do
R(Y)
not overwrite(draw)it again.
R(Z) 4. If loop is present in graph then S is
T1 T2 not CS. if no loop then S is CS then it
W(Y) also serial schedule.
5. Find the serial schedule sequence.
W(Z)
(choose the node whose indegree is
T3
R(Z) zero. Discard that node from graph
with edges and do the same till no
W(X) T2→T3→T1 node)
View Serializability:
View Serializability:
View Serializability:
View Serializability:
View Serializability:
View Serializability:
View Serializability: Example

T1 T2 T3
R(A) —-- —--
— R(A) —
R(B) —-- —--
—- R(B) —--
— —--- R(B)
W(A) —- —-
—-- W(B) —-
View Serializability: Example
View Serializability: Example2
View Serializability: Example
View Serializability: Example
Check following schedule is view equivalent
.
Cascaded Aborts: Recoverable & Non Recoverable Schedules
Non-Serializable Schedules-
● A non-serial schedule which is not serializable is called as a
non-serializable schedule.
● A non-serializable schedule is not guaranteed to produce the the same
effect as produced by some serial schedule on any consistent database.
Characteristics:
Non-serializable schedules-
● may or may not be consistent
● may or may not be recoverable
Cascaded Aborts: Recoverable & Non Recoverable Schedules
Irrecoverable Schedules-
If in a schedule,

● A transaction performs a dirty read operation from an uncommitted transaction

● And commits before the transaction from which it has read the value then such a schedule is known as an
Irrecoverable Schedule.

Example: Here,
● T2 performs a dirty read operation.
● T2 commits before T1.
● T1 fails later and roll backs.
● The value that T2 read now stands
to be incorrect.
● T2 can not recover since it has
already committed.
Cascaded Aborts: Recoverable & Non Recoverable Schedules
Recoverable Schedules-
If in a schedule,

● A transaction performs a dirty read operation from an uncommitted transaction

● And its commit operation is delayed till the uncommitted transaction either commits or roll backs then such a schedule is
known as a Recoverable Schedule.

Ex: Here,
● T2 performs a dirty read operation.
● The commit operation of T2 is delayed
till T1 commits or roll backs.
● T1 commits later.
● T2 is now allowed to commit.
● In case, T1 would have failed, T2 has a
chance to recover by rolling back.
Cascading Schedule:
● If in a schedule, failure of one transaction causes several other dependent transactions
to rollback or abort, then such a schedule is called as a Cascading Schedule or Cascading
Rollback or Cascading Abort.
● It simply leads to the wastage of CPU time.
Ex:
Here, In this schedule,

● Transaction T2 ● The failure of transaction T1 causes

depends on transaction the transaction T2 to rollback.
T1. ● The rollback of transaction T2
● Transaction T3 causes the transaction T3 to
rollback.
depends on transaction
● The rollback of transaction T3
T2.
causes the transaction T4 to
● Transaction T4
rollback.
depends on transaction
T3. Such a rollback is called as a Cascading
Rollback.
Cascadeless Schedule:
If in a schedule, a transaction is not allowed to read a data item until the last transaction that has
written it is committed or aborted, then such a schedule is called as a Cascadeless Schedule.

● Cascadeless schedule allows only committed read operations.

● Therefore, it avoids cascading rollback and thus saves CPU time. However, it allows
● Uncommitted
● write operations.
Strict Schedule:
If in a schedule, a transaction is neither allowed to read nor write a data item until the last transaction
that has written it is committed or aborted, then such a schedule is called as a Strict Schedule.

In other words,

● Strict schedule allows only committed read and write operations.

● Clearly, strict schedule implements more restrictions than cascadeless schedule.

Recoverable Schedules

Cascadeless Schedules

Strict Schedule
Concurrency Control:
Concurrency Control is provided in a database to:
● (i) enforce isolation among transactions.
● (ii) preserve database consistency through consistency preserving execution of
transactions.
● (iii) resolve read-write and write-read conflicts.

Various concurrency control techniques are:

1. Two-phase locking Protocol
2. Timestamp ordering Protocol
3. Multi version concurrency control
4. Validation concurrency control

These methods prevent problems such as deadlocks, dirty reads, and lost updates.
Lock-based Protocol: Shared-Exclusive Lock

In this type of protocol, any transaction cannot read or write data until it acquires an appropriate
lock on it. There are two types of lock:

1. Shared lock:

○ It is also known as a Read-only lock. In a shared lock, the data item can only read by the
transaction.
○ It can be shared between the transactions because when the transaction holds a lock, then
it can't update the data on the data item.

2. Exclusive lock:

○ In the exclusive lock, the data item can be both reads as well as written by the transaction.
○ This lock is exclusive, and in this lock, multiple transactions do not modify the same data
simultaneously.
Lock-based Protocol: Pre Claimed Locking Protocol

○ Pre-claiming Lock Protocols evaluate the transaction to list all the

data items on which they need locks.
○ Before initiating an execution of the transaction, it requests DBMS
for all the lock on all those data items.
○ If all the locks are granted then this protocol allows the
transaction to begin. When the transaction is completed then it
releases all the lock.
○ If all the locks are not granted then this protocol allows the
transaction to rolls back and waits until all the locks are granted.

Lock is attained Lock is released

Lock-based Protocol: 2 Phase Locking Protocol

○ The two-phase locking protocol divides the execution phase of

the transaction into three parts.
○ In the first part, when the execution of the transaction starts, it
seeks permission for the lock it requires.
○ In the second part, the transaction acquires all the locks. The
third phase is started as soon as the transaction releases its
first lock.
○ In the third phase, the transaction cannot demand any new
locks. It only releases the acquired locks.

Growing Phase Shrinking Phase

Time Stamping Protocol:
Basic Idea of Time stamping is to decide the order between the
transactions before they enters into the system. So that in case of
conflict during execution, we can resolve the conflict using ordering.
The reason we call time stamp not stamp because for stamping we use
value of system clock. ( as it will always be unique can never repeat
itself)
For ex. There are two transaction T1 and T2. so T1 enters the system at
10:01am and T2 enters the system at 10:20am
Ts(T1) = 10:01am
Ts(T2) = 12:04pm
Time Stamping Protocol:
Two ideas of Time Stamping:
1. Time Stamping with Transaction:
-> With each transaction Ti, we associated a time stamp denoted by
Ts(Ti).
-> It is the value of the system clock, when a transaction enters into the
system Ts(T1)=10:01 am, if a new transaction enters a system
Ts(T2)=10:20am, then Ts(T1)<Ts(T2) always unique & fixed through the
execution time.
-> also determine serializability order if Ts(T1)<Ts(T2)then system
ensure that in the resultant conflict serializability schedule. T1 will
execute first before T2.
Time Stamping Protocol:
Two ideas of Time Stamping:
2. Time Stamping with data item:
-> For each data item Q protocol maintains two time stamp. Initially
WTs(Q) = Nil and RTs(Q) = Nil

Write time Stamp(Q): It is the largest timestamp of any transaction that

executed Write(Q) successfully.

Read time Stamp(Q): It is the largest timestamp of any transaction that

executed Read(Q) successfully.
Time Stamping Protocol: junior is allowed Senior not allowed
Ti request for Read(Q):
-> if Ts(Ti) < WTs(Q) means Ti needs to read a value of Q that was already
overwritten. Hence request must be rejected or rollback.

Ts(Ti)=5:00 Ts(Tj)=10:00
WTs(Q)

T1 T2

W(Q)

R(Q)

Rollback
Time Stamping Protocol: junior is allowed Senior not allowed
Ti request for Read(Q):
-> if Ts(Ti) >= WTs(Q) Operation can be allowed and
RTs(Q) = Max(RTs(Q),Ts(Ti))

Ts(Ti)=10:00am Ts(Tj)=5:00am Ts(Ti)=10:00am Ts(Tj)=10:00am

WTs(Q) WTs(Q)

T1 T2 T1 T2

W(Q) W(Q)

R(Q) R(Q)
Time Stamping Protocol: junior is allowed Senior not allowed
Ti request for Write(Q):
-> if Ts(Ti) < RTs(Q) means value of Q that Ti is producing was needed
previously and the system assumed that the value would never be produced
hence rejected and rollback. Ts(Ti)=05:00 am Ts(Tj)=10:00 am
RTs(Q)

T1 T2

R(Q)

W(Q)

Rollback & come up

with new timestamp
Time Stamping Protocol: junior is allowed Senior not allowed
Ti request for Write(Q):
-> if Ts(Ti) < WTs(Q) means Ti is attempting to write an absolute value of Q.
reject and rollback.
Ts(Ti)=05:00 am Ts(Tj)=10:00 am
WTs(Q)

T1 T2

W(Q)

W(Q)

Rollback & come up

with new timestamp
Time Stamping Protocol: junior is allowed Senior not allowed
Ti request for Write(Q):
-> if Ts(Ti) >= WTs(Q) and Ts(Ti) >= RTs(Q) Operation can be allowed and
WTs(Q) = Max(WTs(Q),Ts(Ti))

Ts(Ti)=10:00am Ts(Tj)=5:00am Ts(Ti)=10:00am Ts(Tj)=10:00 am

WTs(Q) RTs(Q)

T1 T2 T1 T2

W(Q) R(Q)

W(Q) W(Q)
Properties of Time Stamping Protocol:
1. It ensures Conflict Serializability.
2. It ensures View Serializability.
3. Possibility of dirty read, no restriction on commit hence Irrecoverable
schedules and cascading rollback are possible.
4. Deadlock Handling.
Deadlock occurs when each transaction T in a schedule of two or more

transactions waiting for some item locked by some other

transaction T‘ in the set. Thus, both end up in a deadlock situation,

waiting for the other to release the lock on the item.

Time Stamp based Deadlock Handling:
Time Stamp based Deadlock Handling: Preemptive
Ref: Simplified Computer Science Concepts Prof. Rutuja Kadam
Time Stamp based Deadlock Handling: Non-Preemptive
Ref: Distributed Deadlock Prevention Algorithms : Wait and die algorithm and wound and wait algorithm ([Link])