Concurrency Control

o In the concurrency control, the multiple transactions can be executed

simultaneously.
o It may affect the transaction result. It is highly important to maintain the order of
execution of those transactions.

Problems of concurrency control

Several problems can occur when concurrent transactions are executed in an uncontrolled
manner. Following are the three problems in concurrency control.

1. Lost updates
2. Dirty read
3. Unrepeatable read

a. Lost update problem

o When two transactions that access the same database items contain their
operations in a way that makes the value of some database item incorrect, then the
lost update problem occurs.
o If two transactions T1 and T2 read a record and then update it, then the effect of
updating of the first record will be overwritten by the second update.

Example:

Here,

o At time t2, transaction-X reads A's value.

o At time t3, Transaction-Y reads A's value.
o At time t4, Transactions-X writes A's value on the basis of the value seen at time
t2.
o At time t5, Transactions-Y writes A's value on the basis of the value seen at time
t3.
 o So at time T5, the update of Transaction-X is lost because Transaction y
overwrites it without looking at its current value.
o Such type of problem is known as Lost Update Problem as update made by one
transaction is lost here.

b. Dirty Read

o The dirty read occurs in the case when one transaction updates an item of the
database, and then the transaction fails for some reason. The updated database
item is accessed by another transaction before it is changed back to the original
value.
o A transaction T1 updates a record which is read by T2. If T1 aborts then T2 now
has values which have never formed part of the stable database.

Example:

o At time t2, transaction-Y writes A's value.

o At time t3, Transaction-X reads A's value.
o At time t4, Transactions-Y rollbacks. So, it changes A's value back to that of prior
to t1.
o So, Transaction-X now contains a value which has never become part of the stable
database.
o Such type of problem is known as Dirty Read Problem, as one transaction reads a
dirty value which has not been committed.

c. Inconsistent Retrievals Problem

o Inconsistent Retrievals Problem is also known as unrepeatable read. When a

transaction calculates some summary function over a set of data while the other
transactions are updating the data, then the Inconsistent Retrievals Problem occurs.
o A transaction T1 reads a record and then does some other processing during which
the transaction T2 updates the record. Now when the transaction T1 reads the
record, then the new value will be inconsistent with the previous value.

Example:
Suppose two transactions operate on three accounts.

Transaction X Time Transaction Y

--- t1 ---
Read Balance of Acc-1 t2 ---
Sum=200
Read Balance of Acc-2
Sum=Sum +250=450 t3 ---
--- t4 Read Balance of Acc-3
--- t5 Update Balance of Acc-3 =150-50=100
---- t6 Read Balance of Acc-1
--- t7 Update Balance of Acc-1 =200+50=250
Read Balance of Acc-3 t8 COMMIT
Sum=Sum+100=550 t9 ---

o Transaction-X is doing the sum of all balance while transaction-Y is transferring

an amount 50 from Account-1 to Account-3.
o Here, transaction-X produces the result of 550 which is incorrect. If we write this
produced result in the database, the database will become an inconsistent state
because the actual sum is 600.
o Here, transaction-X has seen an inconsistent state of the database.

Concurrency Control Protocol

Concurrency control protocols ensure atomicity, isolation, and serializability of
concurrent transactions. The concurrency control protocol can be divided into two
categories:

1. Lock based protocol

2. Time-stamp protocol

1. Lock-Based Protocol

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:

o It is also known as a Read-only lock. In a shared lock, the data item can only read
by the transaction.
o 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. LOCK S(A)

2) Exclusive lock:

o In the exclusive lock, the data item can be both read as well as written by the
transaction.
o This lock is exclusive, and in this lock, multiple transactions do not modify the
same data simultaneously. LOCK X(A)

There are four types of lock protocols available:

1. Simplistic lock protocol

It is the simplest way of locking the data while transaction executes. Simplistic lock-
based protocols allow all the transactions to get the lock on the data before insert or
delete or update on it. It will unlock the data item after completing the transaction.

2. Pre-claiming Lock Protocol

o Pre-claiming Lock Protocols evaluate the transaction to list all the data items on
which they need locks.
o Before initiating an execution of the transaction, it requests DBMS for all the lock
on all those data items.
o 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.
o If all the locks are not granted then this protocol allows the transaction to rolls
back and waits until all the locks are granted.
3. Two-phase locking (2PL)

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

There are two phases of 2PL:

 Growing phase: In the growing phase, a new lock on the data item may be acquired
by the transaction, but none can be released.

Shrinking phase: In the shrinking phase, existing lock held by the transaction may
be released, but no new locks can be acquired.

In the below example, if lock conversion is allowed then the following phase can
happen:

1. Upgrading of lock (from S(a) to X (a)) is allowed in growing phase.

2. Downgrading of lock (from X(a) to S(a)) must be done in shrinking phase.

Example:

The following way shows how unlocking and locking work with 2-PL.

Transaction T1:

o Growing phase: from step 1-3

o Shrinking phase: from step 5-7
o Lock point: at 3

Transaction T2:
 o Growing phase: from step 2-6
o Shrinking phase: from step 8-9
o Lock point: at 6

4. Strict Two-phase locking (Strict-2PL)

o The first phase of Strict-2PL is similar to 2PL. In the first phase, after acquiring all
the locks, the transaction continues to execute normally.
o The only difference between 2PL and strict 2PL is that Strict-2PL does not release
a lock after using it.
o Strict-2PL waits until the whole transaction to commit, and then it releases all the
locks at a time.
o Strict-2PL protocol does not have shrinking phase of lock release.

It does not have cascading abort as 2PL does.

2. Timestamp-based or Timestamp Ordering Protocols

The most commonly used concurrency protocol is the timestamp based protocol.
Every transaction has a timestamp associated with it, and the ordering is determined by
the age of the transaction.
o The Timestamp Ordering Protocol is used to order the transactions based on their
Timestamps. The order of transaction is nothing but the ascending order of the
transaction creation.
o The priority of the older transaction is higher that's why it executes first. To
determine the timestamp of the transaction, this protocol uses system time or
logical counter.
o The lock-based protocol is used to manage the order between conflicting pairs
among transactions at the execution time. But Timestamp based protocols start
working as soon as a transaction is created.
o Let's assume there are two transactions T1 and T2. Suppose the transaction T1 has
entered the system at 007 times and transaction T2 has entered the system at 009
times. T1 has the higher priority, so it executes first as it is entered the system first.
o The timestamp ordering protocol also maintains the timestamp of last 'read' and
'write' operation on a data. This lets the system know when the last ‘read and
write’ operation was performed on the data item.

The timestamp-ordering protocol ensures serializability among transactions in their

conflicting read and write 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.

 The timestamp of transaction Ti is denoted as TS(Ti).

 if an old transaction Ti has timestamp TS(Ti), a new transaction Tj is assigned
timestamp TS(Tj) such that TS(Ti) < TS(Tj).
 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).

Basic Timestamp ordering protocol works as follows:

1. Check the following condition whenever a transaction Ti issues a Read (X) operation:

o a )If W-TS(X) >TS(Ti) then the operation is rejected, Rollback Ti.

o b) Otherwise, execute Read(X)and set R-TS(X)= TS(Ti)

2. Check the following condition whenever a transaction Ti issues a Write(X) operation:

o a)If R-TS(X) >TS(Ti) then the operation is rejected, Rollback Ti.

o B) If W-TS(X)> TS(Ti) then then the operation is rejected, Rollback Ti.
o c) otherwise execute Write(X) and set W-TS(X) = TS(Ti)

Where,

TS(TI) denotes the timestamp of the transaction Ti.

R_TS(X) denotes the Read time-stamp of data-item X.

W_TS(X) denotes the Write time-stamp of data-item X.

Example

T1(TS=100)-OLDEST T2(TS=200) T3(TS=300)-Youngest

1. R(A)
2. R(B)
3. W(C)
4. R(B)
5. R(C)
6. W(B)
7. W(A)

Initially,

A B C
R-TS 0 0 0
W-TS 0 0 0

1. T1 (TS=100)… R(A) 0>100? FALSE, execute R(A), update R-TS(A)=100

2. T2(TS=200)… R(B) 0>200? FALSE, excute R(B), update R-TS(B)=200

3. T1(TS=100).. W(C) 0>100? FALSE, 0>100? FALSE, execute W(C), W-TS(C)=100

4. T3 (TS=300)… R(B) 0>300? False, execute R(B), R-TS(B)=300

5. T1 (TS=100)… R(C) 0>100?FALSE, execute R(C), R-TS(C)=100

6. T2(TS=200)… W(B) 300>200?TRUE, T2 is Rollback

7. T3 (TS=300)… W(A) 100>300? FALSE, 0>300?FALSE, execute W(A), UPDATE
W(A)=300

After execution of Timestamp Protocol,

A B C
R-TS 100 300 100
W-TS 300 0 100

Thomas' Write Rule

This rule states if TS(Ti) < W-timestamp(X), then the operation is rejected and T i is
rolled back.

Advantages and Disadvantages of TO protocol:

o TO protocol ensures serializability since the precedence graph is as follows:

o TS protocol ensures freedom from deadlock that means no transaction ever waits.
o But the schedule may not be recoverable and may not even be cascade- free.