DBMS-UNIT-5

Concurrency Control Techniques for elimination of the problem occurred when transactions executes concurrently
Problem : 1. Dirty Read Problem, 2. Unrepeatable Read Problem, 3. Phantom Read Problem, 4. Write-write problem (Lost update problem)
Transaction Techniques (ACID-Atomicity, Consistency, Isolation, Durability Properties must be satisfied)
Time
Concurrency Stamping Validation Based Multi version
Lock Based concurrency control Protocol
Control Concurrency Concurrency control Concurrency
(Isolation and consistency)
Techniques control protocol control techniques
protocol
2Phase Validation This phase is also
Simple known as optimistic Aim to reduce the delay
Locking Conservative
Locking Rigorous 2PL Strict 2 PL concurrency control for read operations.
protocol / 2PL technique. It maintains multiple
Techniques
Basic 2PL Read phase: It is used to read versions of data items.
Transaction Growing Static 2-PL, Improvement All the value of various data Whenever a write
cannot read or Phase: New No growing over 2PL items and stores them in operation is performed,
Exclusive(X)
write data until locks on data phase will be Time Stamp temporary local variables. It the protocol creates a
locks held by
it acquires an items may be completed until All Exclusive
Ordering can perform all the write new version of the
the transaction Protocol:
appropriate lock acquired but the transactions Lock-X (Q) operations on temporary transaction data to
acquire all the be released Used to order the variables without an update ensure conflict-free and
on it. none can be and Shared transactions to the actual database. successful read
released. locks it need on Lock-S (Q )
until after the
based on their Validation phase: In this operations
There are two data item. held by
Transaction
Timestamps. phase, the temporary New Version
Shrinking Commits.
types of lock: transactions A schedule in variable value will be
Phase: Existin If all needed
Information
Shared Lock be released which the validated against the actual
g locks may be locks are not Strict-2PL
Content − This field
(Lock-s()) and until after the transactions data to see if it violates the
released but available then waits until the
contains the data value
Exclusive lock transactions participate is serializability.
no new locks transaction must whole
of that version.
(Lock-X()) commits. then serializable
Description can be release the locks and the Write-timestamp −
transaction to Write phase: If the validation
acquired. acquired so far only equivalent of the transaction is This field contains the
Regorous - commit, and
and wait. serial schedule validated, then the timestamp of the
2PL protocol then it releases
Starvation permitted has temporary results are written transaction that
Problem: is does not have all the locks at the transactions
it is difficult to to the database or system created the new
the situation shrinking a time. in the order of
use in practice otherwise the transaction is version.
phase of lock
when a their Timestamp rolled back. Read-timestamp − This
release. Values. Start (Ti): It contains the time
transaction has Strict-2PL field contains the
to wait for an protocol does when Ti started its execution.
timestamp of the
Validation (Ti): It contains the
indefinite not have transaction that will
time when Ti finishes its read
period of time shrinking read the newly created
phase and starts its validation
to acquire a phase of lock phase. value.
lock. release. Finish(Ti): It contains the time
when Ti finishes its write phase
Conflict
Not sure Yes Yes Yes Yes Yes Conflict may arise Ensures Serializability
serializable
 DBMS-UNIT-5

Ensures View
View Serializable Not sure Yes Yes Yes Yes Yes Not ensures
Serializable
Non Non Non
Ensures Ensures Ensures
recoverable recoverable recoverable
Recoverability Recoverable Recoverable Recoverable Recoverable Recoverable
schedule may schedule may schedule may Schedules
Schedules Schedules
occurs occurs occurs
Cascading Cascading Cascading Cascade-less Cascade-less Cascading
Recovery by --------------------- ------------------
recovery recovery recovery recovery recovery recovery
Suffers from Suffers from Independent of May Suffers Suffers from May suffers from
Deadlock No deadlocks Deadlock free
deadlock deadlock deadlock from deadlock deadlock deadlocks
Efficient (High
Not Much Not Much Not Much Efficient (High level of
Efficiency efficient efficient level of efficient
efficient efficient efficient Concurrency)
Concurrency)

-
 DBMS-UNIT-5

Timestamp Ordering Protocol –

The main idea for this protocol is to order the transactions based on their Timestamps. A schedule in which the transactions participate is then serializable and the only equivalent
serial schedule permitted has the transactions in the order of their Timestamp Values. Stating simply, the schedule is equivalent to the particular Serial Order corresponding to
the order of the Transaction timestamps.
To ensure this, use two Timestamp Values relating to each database item X.

 W-TS(X) is the largest timestamp of any transaction that executed write(X) successfully.
 R-TS(X) is the largest timestamp of any transaction that executed read(X) successfully.

Basic Timestamp Ordering –

Every transaction is issued a timestamp based on when it enters the system. Suppose, if an old transaction T i has timestamp TS (Ti), a new transaction T j is assigned timestamp TS(T j)
such that TS(Ti) < TS(Tj). The protocol manages concurrent execution such that the timestamps determine the serializability order. The timestamp ordering protocol ensures that any
conflicting read and write operations are executed in timestamp order. Whenever some Transaction T tries to issue a R_item(X) or a W_item(X), the Basic TO algorithm compares the
timestamp of T with R-TS(X) & W-TS(X) to ensure that the Timestamp order is not violated. This describes the Basic TO protocol in the following two cases.
1. Whenever a Transaction T issues a W-item(X) operation, check the following conditions:

 If R-TS(X) > TS(T) and if W-TS(X) > TS(T), then abort and rollback T and reject the operation. else,
 Execute W-item(X) operation of T and set W-TS(X) to TS(T). (For stamping to W-item(X) as largest timestamp of T)

2. Whenever a Transaction T issues a R-item(X) operation, check the following conditions:

 If W-TS(X) > TS(T), then abort and reject T and reject the operation, else
 If W-TS(X) <= TS(T), then execute the R-item(X) operation of T and set R-TS(X) to the larger of TS(T) and current R-TS(X).

Points Cases Clock (Time stamping) Transaction (T) (Scenario) Action performed

T issue –Write(X)
If R-TS(X)>TS(T) and W-TS(X) > TS(T) 10 TS(T) [Write(X)] Not Allowed, Abort and Rollback
1 20 R-TS(T) or W-TS(X)
Otherwise 30 R-TS(T) or W-TS(X)
40 TS(T) [Write(X)] Set – TS(T) [Write(X)] = W-TS(X)
T issues a Read(X) 50 TS(T) [Read(X)] Then abort and reject T and rollback
If W-TS(X) > TS(T) 60 W-TS(X)
2
W-TS(X) <= TS(T) 70 W-TS(X) then execute the R-item(X) and
80 TS(T) [Read(X)] set TS(T) [Read(X)]=R-TS(X)
 DBMS-UNIT-5

Milti-Version Concurrency Control Technique

To ensure serializability, the following rules are used:
 If transaction T issues a write-item(X) operation, and version i of X has the highest write-TS(Xi) of all versions of X that is also less than or equal to TS(T), and read-TS(Xi)
> TS(T), then abort and roll back transaction T; otherwise, create a new version Xj of X with read-TS(Xj) = write-TS(Xj) = TS(T).
 If transaction T issues a read-item(X) operation, find the version i of X that has the highest write-TS(Xi) of all versions of X that is also less than or equal to TS(T); then return
the value of Xi to transaction T, and set the value of read-TS(Xi) to the larger of TS(T) and the current read-TS(Xi).

Various Types of MVCC

MVCC Type Description Advantages Disadvantages

Snapshot- Creates a snapshot of the database at the start of a transaction and uses it to provide Easy to implement Significant overhead due to storing
based necessary data for the transaction multiple versions of data

Timestamp- Assigns a unique timestamp to each transaction that creates a new version of a More efficient than snapshot- Requires additional storage to store
based record; used to determine data visibility to transactions based MVCC timestamps

Stores a complete history of all changes made to a record, allowing for easy rollback of Provides highest level of data Most complex of the MVCC
History-based
transactions consistency techniques

Combines two or more MVCC techniques to balance performance and data Provides benefits of multiple More complex to implement than
Hybrid
consistency MVCC techniques individual techniques

Granularity
It is the size of the data item allowed to lock.
Multiple Granularity means hierarchically breaking up the database into blocks that can be locked and can be tracked what needs to lock and in what f ashion. Such a hierarchy
can be represented graphically as a tree.

For example, consider the tree, which consists of four levels of nodes. The highest level represents the entire database. Below it is nodes of type area; the database consists of exactly
these areas. The area has children nodes which are called files. Every area has those files that are its child nodes. No file can span more than one area.
Finally, each file has child nodes called records. As before, the file consists of exactly those records that are its child n odes, and no record can be present in more than one file. Hence,
the levels starting from the top level are:
 Database
 Area
 File
 Record
 DBMS-UNIT-5

Consider the above diagram for the example given; each node in the tree can be locked individually. As in
the 2-phase locking protocol, it shall use shared and exclusive lock modes. When a transaction locks a node,
in either shared or exclusive mode, the transaction also implicitly locks all the descendants of that node in
the same lock mode.
For example, if transaction Ti gets an explicit lock on file Fc in exclusive mode, then it has an implicit lock in
exclusive mode on all the records belonging to that file. It does not need to lock the individual records of
Fc explicitly. This is the main difference between Tree-Based Locking and Hierarchical locking for multiple
granularities.
Now, with locks on files and records made simple, how does the system determine if the root node can be
locked? One possibility is for it to search the entire tree but the solution nullifies the w hole purpose of the
multiple-granularity locking scheme. A more efficient way to gain this knowledge is to introduce a new lock
mode, called Intention lock mode.

Intention Mode Lock

In addition to S and X lock modes, there are three additional lock modes with multiple granularities:
 Intention-Shared (IS): explicit locking at a lower level of the tree but only with shared locks.
 Intention-Exclusive (IX): explicit locking at a lower level with exclusive or shared locks.
 Shared & Intention-Exclusive (SIX): the subtree rooted by that node is locked explicitly in shared
mode and explicit locking is being done at a lower level with exclusive mode locks.
The compatibility matrix for these lock modes are described below:

Multi Granularity tree Hierarchy

The multiple-granularity locking protocol uses the intention lock modes to ensure serializability. It
requires that a transaction Ti that attempts to lock a node must follow these protocols:
 Transaction Ti must follow the lock-compatibility matrix.
 Transaction Ti must lock the root of the tree first, and it can lock it in any mode.
 Transaction Ti can lock a node in S or IS mode only if Ti currently has the parent of the node-locked in either IX or IS mode.
 Transaction Ti can lock a node in X, SIX, or IX mode only if Ti currently has the parent of the node-locked in either IX or SIX modes.
 Transaction Ti can lock a node only if Ti has not previously unlocked any node (i.e., Ti is two-phase).
 Transaction Ti can unlock a node only if Ti currently has none of the children of the node-locked.

Observe that the multiple-granularity protocol requires that locks be acquired in top-down (root-to-leaf) order, whereas locks must be released in bottom-up (leaf to-root) order.
 DBMS-UNIT-5

As an illustration of the protocol, consider the tree given above and the transactions:
 Say transaction T1 reads record Ra2 in file Fa. Then, T1 needs to lock the database, area A1, and Fa in IS mode (and in that order), and finally to lock Ra2 in S mode.
 Say transaction T2 modifies record Ra9 in file Fa . Then, T2 needs to lock the database, area A1, and file Fa (and in that order) in IX mode, and at last to lock Ra9 in X mode.
 Say transaction T3 reads all the records in file Fa. Then, T3 needs to lock the database and area A1 (and in that order) in IS mode, and at last to lock Fa in S mode.
 Say transaction T4 reads the entire database. It can do so after locking the database in S mode.
Note that transactions T1, T3, and T4 can access the database concurrently. Transaction T2 can execute concurrently with T1, but not with either T3 or T4.
This protocol enhances concurrency and reduces lock overhead. Deadlock is still possible in the multiple -granularity protocol, as it is in the two-phase locking protocol. These can be
eliminated by using certain deadlock elimination techniques.

OLS NEW
IX/IS S/IS