Unit – 3 Transaction Management and Concurrency

What is transaction? List and explain ACID property of

transaction with example.
Transaction
 A transaction is a part of program execution that accesses and updates various data
items.
 A transaction can be defined as a group of tasks in which a single task is the minimum
processing unit of work, which cannot be divided further.
 A transaction is a logical unit of work that contains one or more SQL statements.
 A transaction is an atomic unit (transaction either complete 0% or 100%).
 A database transaction must be atomic, meaning that it must be either entirely
completed or aborted.
ACID property
Atomicity
 Either all operations of the transaction are properly reflected in the database or none
are.
 Means either all the operations of a transaction are executed or not a single operation
is executed.
 For example consider below transaction to transfer Rs. 50 from account A to account B:
1. read(A)
2. A := A – 50
3. write(A)
4. read(B)
5. B := B + 50
6. write(B)
 In above transaction if Rs. 50 is deducted from account A then it must be added to
account B.
Consistency
 Execution of a transaction in isolation preserves the consistency of the database.
 Means our database must remain in consistent state after execution of any transaction.
 In above example total of A and B must remain same before and after the execution of
transaction.
Isolation
 Although multiple transactions may execute concurrently, each transaction must be
unaware of other concurrently executing transactions.
 Intermediate transaction results must be hidden from other concurrently executed
transactions.
 In above example once your transaction start from step one its result should not be
access by any other transaction until last step (step 6) is completed.
1
Durability
 After a transaction completes successfully, the changes it has made to the database
persist, even if there are system failures.
 Once your transaction completed up to step 6 its result must be stored permanently. It
should not be removed if system fails.
Explain different states in transaction processing in database.
OR
Explain State Transition Diagram (Transaction State Diagram).
 Because failure of transaction may occur, transaction is broken up into states to
handle various situations.
 Following are the different states in transaction processing in database
 Active
 Partial committed
 Failed
 Aborted
 Committed

Partial Committed
committed

Active

Failed Aborted

Fig. State Transition Diagram

Active
 This is the initial state. The transaction stays in this state while it is executing.
Partially Committed
 This is the state after the final statement of the transaction is executed.
 At this point failure is still possible since changes may have been only done in main
memory, a hardware failure could still occur.
 The DBMS needs to write out enough information to disk so that, in case of a failure, the
system could re-create the updates performed by the transaction once the system is
brought back up.
 After it has written out all the necessary information, it is committed.

2
Failed
 After the discovery that normal execution can no longer proceed.
 Once a transaction cannot be completed, any changes that it made must be undone
rolling it back. 
Aborted
 The state after the transaction has been rolled back and the database has been restored
to its state prior to the start of the transaction.
Committed
 The transaction enters in this state after successful completion of the transaction.
 We cannot abort or rollback a committed transaction.
Explain following terms.
Schedule
 A schedule is the chronological (sequential) order in which instructions are executed in a
system.
 A schedule for a set of transaction must consist of all the instruction of those
transactions and must preserve the order in which the instructions appear in each
individual transaction.
 Example of schedule (Schedule 1)
T1 T2

read(A)
A:=A-50
write(A)
read(B)
B:= B+ 50
write(B)

read(A)
temp: A * 0.1
A: A-temp
write (A)
read(B)
B:=B +temp
write(B)
Serial schedule
 Schedule that does not interleave the actions of different transactions.
 In schedule 1 the all the instructions of T1 are grouped and run together. Then all the
instructions of T2 are grouped and run together.
 Means schedule 2 will not start until all the instructions of schedule 1 are complete. This
type of schedules is called serial schedule.

3
 In the given (a) figure, Schedule A shows the serial schedule where T1 followed by T2.
 In the given (b) figure, Schedule B shows the serial schedule where T2 followed by T1.

4
Non-serial Schedule
 If interleaving of operations is allowed, then there will be non-serial schedule.
 It contains many possible orders in which the system can execute the individual operations
of the transactions.
 In the given figure (c) and (d), Schedule C and Schedule D are the non-serial schedules. It
has interleaving of operations.

5
Serializable schedule
 The serializability of schedules is used to find non-serial schedules that allow the
transaction to execute concurrently without interfering with one another.
 It identifies which schedules are correct when executions of the transaction have
interleaving of their operations.
 A non-serial schedule will be serializable if its result is equal to the result of its transactions
executed serially.

Explain both the forms of serializability with example. OR

Explain conflict serializability and view serializability with
example.

Serializability:
 Serializability is a concurrency scheme where the concurrent transaction is equivalent to
one that executes the transactions serially.
 A schedule is a list of transactions.
 Serial schedule defines each transaction is executed consecutively without any
interference from other transactions.
 Non-serial schedule defines the operations from a group of concurrent transactions that
are interleaved.
 In non-serial schedule, if the schedule is not proper, then the problems can arise like
multiple update, uncommitted dependency and incorrect analysis.
 The main objective of serializability is to find non-serial schedules that allow
transactions to execute concurrently without interference and produce a database
state that could be produced by a serial execution.

Conflict serializability
 Conflict serializability defines two instructions of two different transactions accessing the
same data item to perform a read/write operation.
 It deals with detecting the instructions that are conflicting in any way and specifying the
order in which the instructions should execute in case there is any conflict.
 A conflict serializability arises when one of the instruction is a write operation.
 The following rules are important in Conflict Serializability,
1. If two transactions are both read operation, then they are not in conflict.
2. If one transaction wants to perform a read operation and other transaction wants to
perform a write operation, then they are in conflict and cannot be swapped.
3. If both the transactions are for write operation, then they are in conflict, but can be
allowed to take place in any order, because the transactions do not read the value updated
by each other.
Lets take example:

6
Lets swap non-conflicting operations:
After swapping R(A) of T1 and R(A) of T2 we get:

After swapping R(A) of T1 and R(B) of T2 we get:

After swapping R(A) of T1 and W(B) of T2 we get:

7
 We finally got a serial schedule after swapping all the non-conflicting operations so we can
say that the given schedule is Conflict Serializable.
View serializability
View serializability is the another type of serializability.
It can be derived by creating another schedule out of an existing schedule and involves the
same set of transactions.
The rules it follows are as follows −
 T1 is reading the initial value of A, then T2 also reads the initial value of A.

 T1 is the reading value written by T2, then T2 also reads the value written by T1.

 T1 is writing the final value, and then T2 also has the write operation as the final
value.

Given Schedule:
Schedule S
T3 T4 T6
read(Q)
write(Q)
write(Q)
write(Q)

 Above schedule is view serializable but not conflict serializable because all the
transactions can use same data item (Q) and all the operations are conflict with each
other due to one operation is write on data item (Q) and that’s why we cannot
interchange any non conflict operation of any transaction. 
 Serial Schedule of the above given schedule:
 As we know that in Serial schedule a transaction only starts when the current running
transaction is finished. So the serial schedule of the above given schedule would look
like this:

8
 Schedule S
T3 T4 T6
read(Q)
write(Q)
write(Q)
write(Q)

 If we can prove that the given schedule is View Equivalent to its serial schedule then the
given schedule is called view Serializable.

What is concurrency? What are the methods to control

concurrency?
Concurrency
 Concurrency is the ability of a database to allow multiple (more than one) users to
access data at the same time.
Methods to control concurrency (Mechanisms)

Optimistic - An Optimistic approach is an approach of concurrency control algorithms that are

based on assumption that conflicts of operations on a database are rare. It is advisable to run these
transactions to completion and to check for conflicts only before they commit also here there’s no
checking to be done while the execution of transactions. This approach does not need any locking
or time-stamping method. In an optimistic approach, a transaction is executed without any
problems of restriction until transaction is committed. The optimistic approach allows the
transactions to proceed in an unsynchronized way and also allows conflict checking at the end.
This approach is also known as validation or certification approach.

During optimistic execution, we do only read and compute operations without validation and
validate the transaction just before the right operation.

Read -> Compute -> Validate -> Write

Pessimistic - A Pessimistic approach is an approach of concurrency control algorithms in which

the transaction is delayed if there is a conflict with each other at some point of time in the future. It
locks the database’s record for update access and other users can only access record as read-only
or have to wait for a record to be ‘unlocked’. Programming an app with a pessimistic concurrency
approach can be more complicated and complex in managing because of deadlocks’ risk.

In the execution of pessimistic approach, the validate operation is performed first and if there’s a
validation consistent with the compatibility of the lock then only read, compute, and write
operations are performed i.e.,

Validate -> Read -> Compute -> Write

9
What are the three problems due to concurrency? How the
problems can be avoided.
Three problems due to concurrency
1. The lost update problem: This problem indicate that if two transactions T1 and T2
both read the same data and update it then effect of first update will be overwritten
by the second update.

T1 Time T2
--- T0 ---
Read X T1 ---
--- T2 Read X
Update X T3 ---
--- T4 Update X
--- T5 ---
How to avoid: In above example a transaction T2 must not update the data item (X)
until the transaction T1 can commit data item (X).
2. The dirty read problem: The dirty read arises when one transaction update some
item and then fails due to some reason. This updated item is retrieved by another
transaction before it is changed back to the original value.
T1 Time T2
--- T0 ---
--- T1 Update X
Read X T2 ---
--- T3 Rollback
--- T5 ---
How to avoid: In above example a transaction T1 must not read the data item (X)
until the transaction T2 can commit data item (X).
3. The incorrect retrieval problem: The inconsistent retrieval problem arises when one
transaction retrieves data to use in some operation but before it can use this data
another transaction updates that data and commits. Through this change will be
hidden from first transaction and it will continue to use previous retrieved data. This
problem is also known as inconsistent analysis problem.

10
 Balance (A=200 B=250 C=150)
T1 Time T2
--- T0 ---
Read (A) T1 ---
Sum  200
Read (B) T2 ---
Sum  Sum + 250 = 450
--- T3 Read (C)
--- T4 Update (C)
150  150 – 50 = 100
--- T5 Read (A)
--- T6 Update (A)
200  200 + 50 = 250
--- T7 COMMIT
Read (C) T8 ---
Sum Sum + 100 = 550

How to avoid: In above example a transaction T2 must not read or update data item
(X) Until the transaction T1 can commit data item (X).
What is concurrency control? Why Concurrency control is
needed?
Concurrency control
 The technique is used to protect data when multiple users are accessing (using) same
data concurrently (at same time) is called concurrency control.
Concurrency control needed
 If transactions are executed serially, i.e., sequentially with no overlap in time, no
transaction concurrency exists. However, if concurrent transactions with interleaving
operations are allowed in an uncontrolled manner, some unexpected, undesirable result
may occur. Here are some typical examples:
1. The lost update problem: This problem indicates that if two transactions T1 and T2
both read the same data and update it then effect of first update will be overwritten
by the second update.
2. The dirty read problem: The dirty read arises when one transaction updates some
item and then fails due to some reason. This updated item is retrieved by another
transaction before it is changed back to the original value.
3. The incorrect retrieval problem: The inconsistent retrieval problem arises when one
transaction retrieves data to use in some operation but before it can use this data
another transaction update that data and commits. Through this change will be
hidden from first transaction and it will continue to use previous retrieved data. This

11
 Problem is also known as inconsistent analysis problem.
 Most high-performance transactional systems need to run transactions concurrently to
meet their performance requirements. Thus, without concurrency control such systems
can neither provide correct results nor maintain their databases consistent.
Define lock. Define locking. Explain lock based protocol.
Lock
 A lock is a variable associated with data item to control concurrent access to that data
item.
 Lock requests are made to concurrency-control manager.
 Transaction can proceed only after request is granted.
Locking
 One major problem in databases is concurrency.
 Concurrency problems arise when multiple users try to update or insert data into a
database table at the same time. Such concurrent updates can cause data to become
corrupt or inconsistent.
 Locking is a strategy that is used to prevent such concurrent updates to data.
Lock based protocol
 A lock is a mechanism to control concurrent access to a data item
 Data items can be locked in two modes :
 Data items can be locked in two modes :
1. Exclusive (X) mode. Data item can be both read as well as written. X-lock is
requested using lock-X instruction.
2. Shared (S) mode. Data item can only be read. S-lock is requested using lock-S
instruction.
 Lock requests are made to concurrency-control manager.
 Transaction can proceed only after request is granted.
 Lock-compatibility matrix
S X
S TRUE FALSE
X FALSE FALSE

 A transaction may be granted a lock on an item if the requested lock is compatible with
locks already held on the item by other transactions
 Any number of transactions can hold shared locks on an item, but if any transaction
holds an exclusive on the item no other transaction may hold any lock on the item.
 If a lock cannot be granted, the requesting transaction is made to wait till all
incompatible locks held by other transactions have been released. The lock is then
granted.

12
 T1 T2 Concurrency Control Manager
Lock-X(B)
Grant-X(B,T1)
Read(B)
B=B-50
Write(B)
Unlock(B)
Lock-S(A)
Grant-S(A,T2)
Read(A)
Unlock(A)
Lock-S(B)
Grant-S(B,T2)
Read(B)
Unlock(B)
Lock-X(A)
Grant-X(A,T1)
Read(A)
A=A+50
Write(A)
Unlock(A)

 This locking protocol divides transaction execution phase into three parts.
1. In the first part, when transaction starts executing, transaction seeks grant for locks
it needs as it executes.
2. Second part is where the transaction acquires all locks and no other lock is required.
Transaction keeps executing its operation.
3. As soon as the transaction releases its first lock, the third phase starts. In this phase
a transaction cannot demand for any lock but only releases the acquired locks.

Lock acquisition Lock releasing

phase phase

Time
T begin T end

13
Explain two phase locking protocol.

Two-Phase Locking Protocol

 The use of locks has helped us to create neat and clean concurrent schedule.
 The Two Phase Locking Protocol defines the rules of how to acquire the locks on a data
item and how to release the locks.
 Two phase locking (2PL) is a concurrency control method that guarantees serializability.
 The protocol utilizes locks, applied by a transaction on data, which may block (stop)
other transactions from accessing the same data during the transaction's life.
 The Two Phase Locking Protocol assumes that a transaction can only be in one of two
phases.
Phase 1 - Growing Phase
 In this phase the transaction can only acquire locks, but cannot release any lock.
 The transaction enters the growing phase as soon as it acquires the first lock it
wants.
 From now on it has no option but to keep acquiring all the locks it would need.
 It cannot release any lock at this phase even if it has finished working with a
locked data item.
 Ultimately the transaction reaches a point where all the lock it may need has
been acquired. This point is called Lock Point.
Phase 2 - Shrinking Phase
 After Lock Point has been reached, the transaction enters the shrinking phase.
 In this phase the transaction can only release locks, but cannot acquire any new
lock.
 The transaction enters the shrinking phase as soon as it releases the first lock
after crossing the Lock Point.
 From now on it has no option but to keep releasing all the acquired locks.
 Initially the transaction is in growing phase, that is the transaction acquires locks as
needed.
 Once the transaction releases lock, it enters the shrinking phase and no more lock
request may be issued.
 Upgrading of lock is not possible in shrinking phase, but it is possible in growing phase.
 The two phase locking protocol ensures serializability.
 There are two different versions of the Two Phase Locking Protocol.
1) Strict Two Phase Locking Protocol
2) Rigorous Two Phase Locking Protocol.

14
Explain time stamp based protocol.
Time stamp based protocol
 This protocol uses either system time or logical counter to be used as a time-stamp.
 Every transaction has a time-stamp associated with it and the ordering is determined by
the age of the transaction.
 A transaction created at 0002 clock time would be older than all other transaction,
which come after it.
 For example, any transaction 'y' entering the system at 0004 is two seconds younger
and priority may be given to the older one.
 In addition, every data item is given the latest read and write-timestamp. This lets the
system know, when last read was and write operation made on the data item.
Time stamp ordering protocol
 The timestamp-ordering protocol ensures serializability among transaction in their
conflicting read and writes operations.
 This is the responsibility of the protocol system that the conflicting pair of tasks should
be executed according to the timestamp values of the transactions.
 Time-stamp of Transaction Ti is denoted as TS(Ti).
 Read time-stamp of data-item X is denoted by R-timestamp(X).
 Write time-stamp of data-item X is denoted by W-timestamp(X).
 Timestamp ordering protocol works as follows:
 If a transaction Ti issues read(X) operation:
 If TS(Ti) < W-timestamp(X)
 Operation rejected.
 If TS(Ti) >= W-timestamp(X)
 Operation executed.
 All data-item Timestamps updated.

 If a transaction Ti issues write(X) operation:

 If TS(Ti) < R-timestamp(X)
 Operation rejected.
 If TS(Ti) < W-timestamp(X)
 Operation rejected and Ti rolled back.
 Otherwise, operation executed.

15