CHAPTER - 5

CONCURRENCY CONTROL

5.1 CONCURRENCY CONTROL

The system must control the interaction among the concurrent transactions. This
control is achieve through one of concurrency control schemes. The concurrency control
schemes are based on the serializability property.

Different types of protocols/schemes used to control concurrent execution of

transactions.

5.2 LOCK BASED PROTOCOLS

Locking is a protocol used to control access to data when one transaction is accessing
the database, a lock may deny access to other transactions to prevent incorrect results.
Locking is one of the most widely used mechanisms to ensure serializability.

To ensure serializability, it is required that data items should be accessed in mutual

exclusive manner; if one transaction is accessing a data item, no other transaction can modify
that data item. A transaction is allowed to access a data item only if it is currently holding a
lock on that item.

5.2.1 Types of Locks

Several types of locks can be used in concurrency control. Among them two types are
important.
1. Binary locks.
2. Shared and Exclusive locks.
[Link] Binary Locks
 A binary lock can have two states or values locked and unlocked (0 and 1, for
simplicity).
 A distinct lock is associated with each data base item X.
 If the value of the lock on X is 1, item X cannot be accessed by a database
operation that requests the item.
 If the value of the lock on X is 0, the item can be accessed when
 Concurrency Control 5.2

requested. We refer to the value of the lock associated with item X as Lock(X).
 Two operations, lock_item and unlock_item must be included in the
transactions when binary locking is used.
 A transaction requests access to an item X by issuing a lock_item(X)
operation.
 If lock(X) = 1, the transaction is forced to wait otherwise, the transaction
sets lock(X) : = 1 (locks the item) and is allowed access
 When the transaction is through using the item, it issues an unlock_item (X)
operation, which sets lock (X) : = 0 (unlocks the item) so that X may be accessed by
other transactions.
Hence a binary lock enforces mutual exclusion on the data item.
A description of the lock_item (X) and unlock-item (X) operations is shown below:
lock_item(X):
B : if lock(X) = 0 (* item is unlocked *)
then lock(X) 1 (*lock the item *)
else begin
wait (until lock(X) = 0 and the lock manager wakes up the transaction);
go to B;
end;
unlock_item(X):
lock(X) 0 (* unlock the item *)
if any transaction are waiting then wakeup one of the waiting transactions.
Lock and unlock operation for binary locks

The lock_item and unlock_item operations must be implemented as indivisible units;

that is no interleaving should be allowed once a lock or unlock operation is started until the
operation terminates or the transaction waits.

In above algorithm, the wait command within the lock_item(X) operation is usually
implemented by putting the transaction on a waiting queue for the item X until X is unlocked
and the transaction is granted access to it. Other transactions that also want to access X are
placed on the same queue.
5.3 Database Management Systems

Hence, the wait command is considered to be outside the lock-item operation. The
DBMS has a lock manager subsystem to keep track of and control access to locks.

When the binary locking scheme is used, every transaction must obey the following
rules:

1. A transaction T must issue the operation lock_item(X) before any

read_item(X) or write_item(X) operations are performed in T.
2. A transaction T must issue the operation unlock_item (X) after all
read_item(X) and write_item(X) operations are completed in T.
3. A transaction T will not issue a lock_item(X) operation if it already holds
the lock on item X.
4. A transaction T will not issue an unlock_item(X) operation unless it already
holds the lock on item X.
These rules can be enforced by a module of the DBMS. Between the lock_item(X) and
unlock_item(X) operations in transaction T, T is said to hold the lock on item X. At most one
transaction can hold the lock on a particular item. No two transactions can access the same
item concurrently.
Each lock can be record with two fields, <Data item name, Lock> plus a queue for
waiting transactions. The system only needs to maintain these records for locked items in a
lock table.

[Link] Shared and Exclusive Lock

(i) Shared Mode Lock

If a transaction Ti has obtained a shared mode lock on item Q, then Ti can
read, but cannot write Q. It is denoted by S.
(ii) Exclusive Mode Lock
If a transaction Ti has obtained an exclusive lock on item Q, then Ti can read
and also write Q. It is denoted by X.
A transaction requests a shared lock on data item Q by executing the lock-S(Q)
instruction. Similarly, a transaction requests an exclusive lock through the lock-X(Q)
instruction. A transaction can unlock a data item Q by the unlock (Q) instruction.
Given a set of lock modes, we can define a compatibility function on them as follows.
Let A and B represent arbitary lock modes. Suppose that a transaction Ti requests a lock of
mode A on item Q on which transaction Tj (Ti  Tj) currently hold a lock of mode B. If
transaction Ti can be granted a lock of Q immediately, in spite of the presence of the mode B
 Concurrency Control 5.4

lock, then we say mode A is compatible with mode B such a function is represented by a
matrix. The matrix is shown in Fig. 5.1.

S S
S true false
X false false

Fig 5.1 Lock-compatibility matrix ‘comp’

To access a data item, transaction Ti must first lock that item. If the data item is
already locked by another transaction in an incompatible mode, the concurrency
control manager will not grant the lock until all incompatible locks held by other transactions
have released. Thus, Ti is made to wait until all incompatible locks held by other transactions
have been released.

Example: Let A and B be two accounts that are accessed by transactions T1 and T2. Transaction
T1 transfers $50 from account B to account A. It is shown in Fig. [Link] T2 displays
the total amount of money in accounts A and B. It is shown in Fig. 6.4.

T1: lock - X(B); T2 : lock - S(A);

read (B); read (A);
B : = B - 50; unlock (A);
write (B); lock - S(B);
unlock (B); read (B);
lock - X(A); unlock (B);
read (A); display (A + B);
A : = A + 50;
write (A); Fig. 5.3 Transaction T2
unlock (A);

Fig 5.2 Transaction T1

Suppose that the values of accounts A and B are $100 and $200, respectively.
If these two transactions are executed serially, either in the order T1, T2 or the order T2, T1, then
transaction T2 will display the value $300.

If, however, these transactions are executed concurrently, then schedule 1, in

5.5 Database Management Systems

Fig. 5.3 is possible.

In this case, transaction T2 displays $250, which is incorrect. The reason for this
mistake is that the transaction T1 unlocked data item B too early, as a result of which T2 saw an
inconsistent state.

Locking can lead to an undesirable situation. Consider the schedule 2 of Fig. 6.6. Here
T3 is holding an exclusive-mode lock on B and T4 is requesting a shared mode lock on B, T4 is
waiting for T3 to unlock B. Similarly, T4 is holding a shared mode lock on A and T3 is
requesting an exclusive-mode lock on A, T3 is wating for T4 to unlock A.

Thus, in this situation neither of transactions can proceed with normal execution. This
situation is called deadlock. When deadlock occurs, the system must rollback one of the two
transactions. Once a transaction has been rolled back, the data items that were locked by that
transaction are unlocked. These data items are then available to the other transaction, which
can continue with its execution.

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)

read(B) grant – S(B, T2)

unlock(B)
display(A+B)
lock-X(A)
grant – X(A, T2)
read(A)
A: = A+50
write(A)
unlock(A)

Fig. 5.4 Schedule 1

 Concurrency Control 5.6

T3 T3

lock-X(B)
read (B)
B: = B-50
write(B)
lock-S(A)
read (A)
lock-S(B)
lock-X(A)

Fig. 5.5 Schedule 2

5.3 LOCKING PROTOCOLS

Each transaction in the system should follow a set of rules, called locking protocol,
indicating when a transaction may lock and unlock each of the data items. Locking protocol
restricts the number of possible schedules. The set of all such schedules is a proper subset of
all possible serializable schedules.

5.3.1 Granting of Locks

When a transaction requests a lock on the data item in a particular mode and no other
transaction has a lock on the same data item in a conflicting mode, the lock can be granted.
However, care must be taken while granting the locks.

For example, consider a transaction T2 has a shared mode lock on data item Q, and
another transaction T1 requests an exclusive-mode lock on the same data item. In this case, T1
has to wait for T2 to release the shared - mode lock. Mean while, another transaction T3
requests the shared mode lock on Q. The lock request is compatible with the lock granted to
T2, so T3 may be granted the shared-mode lock.
At this point, T2 may releases the lock, but still T1 has to wait for T3 to release the lock.
Thus it is possible that sequence of transactions that each requests a shared-mode lock on Q,
and each transaction releases the lock a short while after it is granted, but T1 may never gets
the exclusive mode lock on the data item. The transaction T1 may never make progress 1 and
is said to be starved.
Starvation of transaction can be avoided by granting locks in the following manner.
When a transaction Ti requests a lock on a data item Q in a particular mode M, the
concurrency control manager grants the lock provided that
5.7 Database Management Systems

1. There is no other transaction holding a lock on Q in a mode that conflicts

with M.
2. There is no other transaction that is waiting for a lock on Q, and that made
its lock request before Ti.
5.3.2 Two-phase Locking Protocol
This protocol requires that each transaction issue lock and unlock requests in two
phases.
1. Growing phase: A transaction may obtain locks, but may not release any lock.
2. Shrinking phase: A transaction may release locks, but may not obtain any new
locks.
Initially, a transaction is in the growing phase. The transaction aquires locks as needed.
Once a transaction releases a lock, it enters in the shrinking phase, and it cannot issue more
lock requests.
For example, transactions T3 is two phase. But transactions T1 and T2 are not two phase.
Note that the unlock instructions do not need appear at the end of the transaction.

T3: lock-X (B);

read (B);
B: = B-50;
write (B);
lock-X (A);
read (A);
A: = A=50;
write (A);
unlock (B);
unlock (A);

Fig. 5.6 Transaction T3

Advantages
The two-phase locking protocol ensures conflict serializability.
Consider any transaction, the point in the schedule where the transaction has obtained
its final lock is called the lock-point of the transaction. Now, the transactions can be ordered
according to their lock points. This ordering is the serializability ordering for the transactions.
Disadvantages
1. It does not ensure freedom from deadlock.
2. Cascading rollbacks may occur under two-phase locking.
 Concurrency Control 5.8

Consider schedule 2 shown in Fig. 6.8.

T5 T6 T5

lock-X(A)
read(A)
lock-S(B)
read(B)
write(A)
unlock(A)
lock-X(A)
read(A)
write(A)
unlock(A)
lock-S(A)
read(B)

Fig.5.7 Partial schedule under two-phase locking

Here, the transactions T5, T6 and T7 are two phase, but failure of T5 after the read (A)
instruction of T7 leads to cascading rollback of T6 and T7.
Cascading rollbacks can be avoided by a modification of two-phase locking-called the
strict two-phase locking protocol.
Types:
1. Strict two phase locking protocol
This protocol requires that locking should be two phase, and all exclusive-mode locks
taken by a transaction should be held until the transaction. This requirement prevents any
transaction from reading the data written by any uncommitted transaction under exclusive
mode until the transaction commits, preventing any other transaction from reading the data.
2. Rigorous two phase locking protocol
This protocol requires that all locks be held until the transaction commits. We can easily
verify that, with rigorous two-phase locking, transactions can be serialized in the order in
which they [Link] database systems implement either strict or rigorous two-phase
locking.
Two-phase locking protocol allows lock conversions. There is a mechanism for
upgrading a shared lock to an exclusive lock, downgrading an exclusive lock to a shared lock.
We donote the conversion from shared to exclusive modes by upgrade, and from exclusive to
shared by downgrade. Lock conversion cannot be allowed arbitrarily.
5.9 Database Management Systems

Strict two-phase locking and rigorous two-phase locking (with lock conversions) are
used extensively in commercial database systems.
A simple but widely used scheme automatically generates the appropriate lock and
unlock instructions for a transaction, on the basis of read and write requests from the
transaction:

 When a transaction Ti issues a read (Q) operation, the system issues a lock-
S(Q) instruction followed by the read (Q) instruction.

 When Ti issues a write (Q) operation, the system checks to see whether Ti
already holds a shared lock on Q. If it does, then the system issues an upgrade
(Q) instruction, followed by the write (Q) instruction. Otherwise, the system
issues a lock - X(Q) instruction, followed by the write (Q) instruction.

 All locks obtained by a transaction are unlocked after that transaction commits or
aborts.

5.4 TIMESTAMP BASED PROTOCOLS

Time stamp based protocol ensures serializability, it selects on ordering among

transactions in advance using time stamps.
5.4.1 Time Stamps
 With each transaction Ti in the system, a unique fixed timestamp is
associated it is denoted by TS( Ti ).
 This timestamp is assigned by the database system before the transaction Tj
starts execution.
 If a transaction Ti has been assigned timestamp TS( Ti ) and new transaction
Tj enters the system, then TS( Ti ) < TS( Tj )
There are two simple methods for implementing this scheme:
1. Use the value of the system clock as the timestamp, that is transaction
timestamp is equal to the value of the clock when the transaction enters the
system.
2. Use a logical counter, that is a transaction timestamp is equal to the value
of the counter when the transaction enters the system.
 Concurrency Control 5.10

The timestamps of the transactions determine the serializability order. Thus, if TS(Ti)
< TS(Tj), then the system must ensure that the produced schedule is equivalent to a serial
schedule in which transaction Ti appears before transaction Tj.

To implement this scheme, two timestamps associated with each data item Q.
(i) W-timestamp (Q) denotes the largest timestamp of any transaction that
executed write (Q) successfully.
(ii) R-timestamp (Q) denotes the largest timestamp of any transaction that
executed read (Q) successfully.
These time stamps are updated whenever a new read(Q) or write(Q) instruction is
executed.
5.4.2 Timestamp Ordering Protocol

The timestamp ordering protocol ensures that any conflicting read and write operations
are executed in timestamp order. This protocol operates as follows:

1. Suppose that transaction Ti issues read (Q).

(a) If TS(Ti) < W-timestamp (Q), then Ti needs to read a value of Q that was
already overwritten. Hence the read operation is rejected, and Ti is rolled back.

(b) If TS(Ti) W-timestamp (Q), then the read operation is executed, and R-
timestamp (Q) is set to the maximum of R-timestamp (Q) and TS(Ti).

2. Suppose the transaction Ti issues write (Q).

(a) If TS(Ti) < R-timestamp (Q), then the value of Q that Ti is producing was
needed previously, and the system assumed that the value would never be
produced. Hence, the system rejects the write operation and rolls Ti back.

(b) If TS(Ti) < W-timestamp (Q), then Ti is attempting to write an obsolete

value of Q. Hence, the system rejects this write operation and rolls Ti back.

(c) Otherwise, the system executes the write operation and sets W-timestamp
(Q) to TS( Ti ).

If a transaction Ti is rolled back by the concurrency-control scheme the system assigns

it a new timestamp and restarts it.

Example: Consider two transactions T14 and T15. Transaction T14 displays the sum of
acocunts A and B, and transaction T15 transfers $50 from account B to account A and displays
the sum of both.
5.11 Database Management Systems

T14 : read (B);

read (A);
display (A + B).
T15 : read (B);
B:=B 50;
write (B);
read (A);
A : = A + 50;
write (A);
display (A + B).

Fig. 5.8 shows a concurrent schedule for these two transactions.

T14 T15

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

Fig. 5.9 Schedule 3

As shown in Fig. 6.10, in schedule 3, TS(T14) < TS(T15) and the schedule is possible
under timestamp protocol.
Advantages
1. The timestamp ordering protocol ensures conflict serializability. This is
because conflicting operations are processed in timestamp order.

2. The protocol ensures freedom from deadlock, since no transaction ever

waits.

Disadvantages

1. There is a possibility of starvation of long transactions if a sequence of

conflicting short transactions causes repeated restarting of the long transaction.
 Concurrency Control 5.12

If a transaction is found to be getting restarted repeatedly, conflicting

transaction need to be temporarily blocked to enable the transaction to finish.

2. The protcol can generate schedules that are not recoverable.

5.4.3 Thomas’ Write Rule

Thomas’ write rule is a modified version of timestamp ordering protocol.

Consider schedule 4 given in Fig. 11.11.

T16 T17

read (Q)
write (Q)
write (Q)

Fig.5.10 Schedule 4

Here T16 starts before T17, therefore TS(T16) < TS(T17). The read (Q) operation of
T16 succeeds, similarly the write (Q) operation of T17. When T16 attempts its write (Q)
operation, we find TS(T16) < W-timestamp (Q), since W-timestamp (Q) = TS(T17). Thus, the
write (Q) is rejected by the system and T16 is rolled back.

The rollback T16 is required by the timestamp-ordering protocol, it is unnecessary.

Since T17 has already written Q, the value that T16 is attempting to write is one that will
never need to be read.

Any transaction Ti with TS(Ti) < TS(T17) that attempts a read (Q) will be rolled back,
since TS(Ti) < W-timestamp (Q).

The modification to the timestamp-ordering protocol, called Thomas’ write rule.

Definition is as follows:

Suppose that transaction Ti issues write (Q).

1. If TS(Ti) < R-timestamp (Q), then the value of Q that Ti is producing

was previously needed, and it had been assumed that the value would never be
produced. Hence, the system rejects the write operation and rolls Ti back.

2. If TS(Ti) < W-timestamp (Q), then Ti is attempting to write an obsolete

value of Q. Hence, this write operation can be ignored.

3. Otherwise, the system executes the write operation and sets W-timestamp
(Q) to TS(Ti).
5.13 Database Management Systems

The difference between timestamp ordering process and Thomas’ write rule lies in the
second rule. The timestamp-ordering protocol requires that Ti be rolled back if Ti issues write
(Q) and TS(Ti) < W-timestamp (Q). However, here, in those cases where
TS(Ti) R-timestamp (Q), we ignore the obsolete write. This modification to the
timestamp-ordering protocol is called Thomas write rule.

5.5 DEADLOCK

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

In other words, there exists a set of waiting transactions such that T0 is waiting for a
data item that T1 holds and T1 is waiting for a data item that T2 holds and ..., and Tn-1 is
waiting for a data item that Tn holds, and Tn is waiting for a data item that T0 holds. In such a
situation, none of the transactions can make progress.

There are two principal methods for dealing with the deadlock problem.
(i) Deadlock prevention: This approach ensures that system will never enter in
deadlock state.
(ii) Deadlock detection and recovery: This approach tries to recover from
deadlock if system enters in deadlock state.
5.5.1 Deadlock Prevention
There are two approaches for deadlock prevention:
(a) One approach ensures that no cyclic waits can occur by ordering the requests
for locks, or requiring all locks to be acquired together. This approach
requires that each transaction locks all data items before it begins execution. It is
required that, either all data items should be locked in one step, or none should be
locked.
Disadvantages of this approach are
1. It is hard to predict before the transaction begins, what data items need to be
locked.
2. Data-item utilization may be very low, since many of the data items may be
locked but unused for long time.
(b) The second approach for deadlock prevention is to use pre-emption and
transaction rollbacks. In pre-emption when a transaction T2 requests a lock
that transaction T1 holds, the lock granted to T1 may be pre-empted by rolling
 Concurrency Control 5.14

back of T1, and granting of the lock to T2.

To control pre-emption, a unique timestamp is assigned to each transaction. The
system uses timestamp to decide whether a transaction should wait or roll back.
Two different deadlock prevention schemes using timestamp are:
(i) Wait-die
The wait-die scheme is non-pre-emption technique. In this, when transaction Ti
requests a data item held by Tj, Ti is allowed to wait only if it has a timestamp
smaller than Tj. (That is Ti is older than Tj). Otherwise, Ti is rolled back (dies).
For example, suppose that transactions T22, T23, and T24 have timestamps 5, 10
and 15 respectively. If T22 requests a data item held by T23, then T22 will wait. If
T24 requests a data item held by T23, then T24 will be rolled back.
(ii) Wound-wait
The wound-wait is pre-emptive technique. In this, when transaction Ti requests
data item-held by Tj, Ti is allowed to wait, only if it has timestamp greater than
Tj (that is Ti is younger than Tj). Otherwise Tj is rolled back.

Returning to same example, if T1 requests a data item hold by T2, then the data
item will be preempted by T2, and T2 will be rolled back. If T3 requests a data
item held by T2 then T3 will wait.
Differences between two schemes
 In the wait-die scheme, an older transaction must wait for a younger one to release
its data item. Thus, the older the transaction gets, the more it tends to wait. By
contrast, in the wound-wait scheme, an older transaction never waits for a younger
transaction.
 In the wait-die scheme, if a transaction Ti dies and is rolled back because it
requested a data item held by transaction Tj , then Ti may re-issue the same
sequence of requests when it is restarted. If the data item is still held by Tj, then Ti
will die again.
Thus Ti may die several times before acquiring the needed data item. Contrast this
series of events with what happens in the wound-wait scheme Transaction Ti is wounded and
rolled back because Tj requested a data item that it holds. When Ti is restarted and requests the
data item now being held by Tj, Ti waits. Thus, there may be fewer rollbacks in the wound-
wait scheme.
5.15 Database Management Systems

The major problem with both of these schemes is that unnecessary rollbacks may
occur.
5.5.2 Timeout-Based Schemes
This approach for deadlock handling is based on lock timeouts. In this approach, a
transaction that has requested a lock waits for at most a specified amount of time. If the lock
has not been granted within that time, the transaction is said to be time out, and it rolls back
itself and restarts. Thus, if there was a deadlock one or more transactions involved in the
deadlock will time out and roll back, allowing the others to proceed.
Advantages
1. This scheme is easy to implement.
2. It works well if transactions are short, and if long, waits are likely to be due to
deadlocks.
Disadvantages
1. It is hard to decide how long a transaction should wait. Too long waits results
in unnecessary delays once a deadlock has occurred, and too short a wait results
in transaction rollbacks even when there is no deadlock.
2. Starvation is also possible with this scheme.
5.5.4 Deadlock Detection and Recovery
This approach uses an algorithm that examines the state of the system periodically to
determine whether a deadlock has occurred. If one has occurred, then the system attempts to
recover from the deadlock.
[Link] Deadlock Detection
Deadlocks can be described in terms of directed graphs called a wait-for graph. This
graph consists of a pair G = (V, E), where
V-set of vertices consists of all transactions in the system.
E-set of edges.

If Ti  Tj is in E, then there is a directed edge from transaction Ti to Tj. When

transaction Ti requests a data item currently held by transaction Tj, then the edge Ti  Tj is
inserted in the wait for graph. A deadlock exists in the system if and only if the wait for graph
contains a cycle. Each transaction involved in the cycle is said to be dead locked.
Example: Consider the wait for graph shown in Fig. 6.12 (a).
 Concurrency Control 5.16

T26 T28

T25

T27

Fig. 5.11 (a) Wait for graph with no cycle

The graph depicts the following situation:
 Transaction T25 is waiting for transaction T26 and T27
 Transaction T27 is waiting for transaction T26
 Transaction T26 is waiting for transaction T28.
This graph has no cycle, therefore the system is not in a deadlock state.
Consider the graph shown in Fig. 6.12 (b).

T26 T28

T25

T27

Fig.5.11 (b) Wait for graph with a cycle

The above graph contains the cycle
T26 T28 T27 T26
implying that transactions T26, T27, T28 are all deadlocked.
If deadlocks occur frequently, then the detection algorithm should be invoked more
frequently than usual. Data items allocated to deadlocked transactions will be unavailable to
other transactions until the deadlock can be broken.

[Link] Recovery from Deadlock

When a deadlock detection algorithm determines that a deadlock exists, the system
must recover from the deadlock. The most common solution is to rollback one or more
transactions to break the deadlock.

Three actions need to be taken:

5.17 Database Management Systems

1. Selection of a victim

Given a set of deadlocked transactions, we must determine which transaction should be

rolled back to break the deadlock. Roll back those transactions that will incur minimum
cost. Unfortunately the term minimum cost is not a precise one. Many factors may
determine the cost of a rollback

(i) How long the transaction has computed, and how much longer the
transaction will compute before it completes its designated task ?
(ii) How many data items the transaction has used ?
(iii) How many more data items the transaction needs for it to complete ?
(iv) How many transactions will be involved in the rollback?
2. Rollback

Once we have decided to roll back particular transaction, we must determine how for this
transaction should be rolled back. The solutions are:

(i) Total rollback: Abort the transaction and then restarts it.

(ii) Partial rollback: It is more effective to roll back the transaction only as far as necessary
to break the deadlock. It requires the system to maintain additional information about the
state of all the running transactions. Specifically, the sequence of lock requests/grants and
updates performed by the transaction needs to be recorded.

3. Starvation

It is possible that, same transaction will be rolled back number of times to break the
deadlock. As a result, this transaction never completes its designated task, thus there is
starvation. To avoid this, we must ensure that transactions can be picked as a victim only
a small number of times.

5.6 TRANSACTION RECOVERY

 Protocols that obey this are referred to as non-blocking protocols. In the following
two sections, we consider two common commit protocols suitable for distributed
DBMSs: two-phase commit (2PC) and three-phase commit (3PC), a non-blocking
protocol.
 Assume that every global transaction has one site that acts as coordinator (or
transaction manager) for that transaction, which is generally the site at which the
transaction was initiated. Sites at which the global transaction has agents are called
participants (or resource managers).
 Concurrency Control 5.18

 Assume that the coordinator knows the identity of all participants and that each
participant knows the identity of the coordinator but not necessarily of the other
participants.

5.6.1 Two-Phase Commit (2PC)

 2PC operates in two phases: a voting phase and a decision phase.

 The basic idea is that the coordinator asks all participants whether they are prepared to
commit the transaction. If one participant votes to abort, or fails to respond within a
timeout period, then the coordinator instructs all participants to abort the transaction.
 If all vote to commit, then the coordinator instructs all participants to commit the
transaction. The global decision must be adopted by all participants.
 If a participant votes to abort, then it is free to abort the transaction immediately; in
fact, any site is free to abort a transaction at any time up until it votes to commit. This
type of abort is known as a unilateral abort.
 If a participant votes to commit, then it must wait for the coordinator to broadcast
either the global commit or global abort message.
 This protocol assumes that each site has its own local log, and can therefore rollback
or commit the transaction reliably. Two-phase commit involves processes waiting for
messages from other sites. To avoid processes being blocked unnecessarily, a system
of timeouts is used. The procedure for the coordinator at commit is as follows:
Phase 1
(1) Write a begin_commit record to the log file and force-write it to stable storage.
 Send a PREPARE message to all participants.
 Wait for participants to respond within a timeout period.
Phase 2
(2) If a participant returns an ABORT vote,
 Write an abort record to the log file and forcewrite it to stable storage.
 Send a GLOBAL_ABORT message to all participants.
 Wait for participants to acknowledge within a timeout period.
(3) If a participant returns a READY_COMMIT vote,
 Write a commit record to the log file and force-write it to stable storage.
 Send a GLOBAL_COMMIT message to all participants.
 Wait for participants to acknowledge within a timeout period.
(4) Once all acknowledgements have been received,
 Write an end_transaction message to the log file.
5.19 Database Management Systems

[Link] 2PC Protocol for voting Commit:

Fig 5.12 2 PC Protocol for voting Commit

[Link] 2PC Protocol for voting Abort:

Fig. 5.13 2PC Protocol for voting Abort

 Concurrency Control 5.20

[Link] Termination protocols for 2PC

A termination protocol is invoked whenever a coordinator or participant fails to
receive an expected message and times out. The action to be taken depends on whether the
coordinator or participant has timed out and on when the timeout occurred.
(i) Coordinator
The coordinator can be in one of four states during the commit process:
 INITIAL
 WAITING
 DECIDED
 COMPLETED
as shown in the state transition diagram in Figure, but can time out only in the middle two
states. The actions to be taken are as follows:
Timeout in the WAITING state -The coordinator is waiting for all participants to
acknowledge whether they wish to commit or abort the transaction. In this case, the
coordinator cannot commit the transaction because it has not received all votes. However, it
can decide to globally abort the transaction.
Timeout in the DECIDED state -The coordinator is waiting for all participants to
acknowledge whether they have successfully aborted or committed the transaction. In this
case, the coordinator simply sends the global decision again to sites that have not
acknowledged.

Fig.5.14 Termination protocols for 2PC

5.21 Database Management Systems

(ii) Participant
A participant can be in one of four states during the commit process:
 INITIAL
 PREPARED
 ABORTED
 COMMITTED
as shown in the state transition diagram in Figure. However, a participant may time out only
in the first two states as follows:
Timeout in the INITIAL state-The participant is waiting for a PREPARE message
from the coordinator, which implies that the coordinator must have failed while in the
INITIAL state. In this case, the participant can unilaterally abort the transaction. If it
subsequently receives a PREPARE message, it can either ignore it, in which case the
coordinator times out and aborts the global transaction, or it can send an ABORT message to
the coordinator.
Timeout in the PREPARED state-The participant is waiting for an instruction to
globally commit or abort the transaction. The participant must have voted to commit the
transaction, so it cannot change its vote and abort the transaction. Equally well, it cannot go
ahead and commit the transaction, as the global decision may be to abort.

[Link] Recovery protocols for 2PC

(i) Coordinator failure
Consider three different stages for failure of the coordinator:
 Failure in INITIAL state-The coordinator has not yet started the commit
procedure. Recovery in this case starts the commit procedure.
 Failure in WAITING state-The coordinator has sent the PREPARE
message and although it has not received all responses, it has not received an
abort response. In this case, recovery restarts the commit procedure.
 Failure in DECIDED state-The coordinator has instructed the participants
to globally abort or commit the transaction. On restart, if the coordinator has
received all acknowledgements, it can complete successfully.
(ii) Participant failure
Consider three different stages for failure of a participant:
 Failure in INITIAL state-The participant has not yet voted on the
transaction. Therefore, on recovery it can unilaterally abort the transaction,
as it would have been impossible for the coordinator to have reached a
global commit decision without this participant’s vote.
 Failure in PREPARED state-The participant has sent its vote to the
coordinator. In this case, recovery is via the termination protocol discussed
above.
 Concurrency Control 5.22

 Failure in ABORTED/COMMITTED states-The participant has completed

the transaction. Therefore, on restart, no further action is necessary.

5.4 SAVE POINTS

A SAVEPOINT is a point in a transaction when you can roll the transaction back to a
certain point without rolling back the entire transaction.
The syntax for a SAVEPOINT command is as shown below.
SAVEPOINT SAVEPOINT_NAME;
This command serves only in the creation of a SAVEPOINT among all the
transactional statements. The ROLLBACK command is used to undo a group of transactions.
The syntax for rolling back to a SAVEPOINT is as shown below.
ROLLBACK TO SAVEPOINT_NAME;
Following is an example where you plan to delete the three different records from the
CUSTOMERS table. You want to create a SAVEPOINT before each delete, so that you can
ROLLBACK to any SAVEPOINT at any time to return the appropriate data to its original
state.
Example
Consider the CUSTOMERS table having the following records.
ID NAME AGE ADDRESS SALARY
1 Suresh 23 Chennai 5400
2 Mano 22 Cochin 6500
3 Subhiksha 23 Newyork 4500
4 Malar 24 Bangalore 4300
5 Sarath 22 Trichy 7500
6 Krishna 32 Coimbatore 6600
7 Ranchana 21 Hyderabad 5500

The following code block contains the series of operations.

SQL> SAVEPOINT SP1;
Savepoint created.
SQL> DELETE FROM CUSTOMERS WHERE ID=1;
1 row deleted.
5.23 Database Management Systems

SQL> SAVEPOINT SP2;

Savepoint created.
SQL> DELETE FROM CUSTOMERS WHERE ID=2;
1 row deleted.
SQL> SAVEPOINT SP3;
Savepoint created.
SQL> DELETE FROM CUSTOMERS WHERE ID=3;
1 row deleted.
Now that the three deletions have taken place, let us assume that you have changed your
mind and decided to ROLLBACK to the SAVEPOINT that you identified as SP2. Because
SP2 was created after the first deletion, the last two deletions are undone −
SQL> ROLLBACK TO SP2;
Rollback complete.
Notice that only the first deletion took place since you rolled back to SP2.
ID NAME AGE ADDRESS SALARY
2 Mano 22 Cochin 6500
3 Subhiksha 23 Newyork 4500
4 Malar 24 Bangalore 4300
5 Sarath 22 Trichy 7500
6 Krishna 32 Coimbatore 6600
7 Ranchana 21 Hyderabad 5500
6 rows selected

RELEASE SAVEPOINT Command

RELEASE SAVEPOINT command is used to remove a SAVEPOINT that you have
created.
The syntax for a RELEASE SAVEPOINT command is as follows.
RELEASE SAVEPOINT SAVEPOINT_NAME;
Once a SAVEPOINT has been released, you can no longer use the ROLLBACK command to
undo transactions performed since the last SAVEPOINT.
 Concurrency Control 5.24

5.5 ISOLATION LEVELS

Isolation levels determine the type of phenomena that can occur during the execution
of concurrent transactions. eDeveloper sets this property only for the following databases:
MSSQL, Informix and DB2.
Three phenomena define SQL Isolation levels for a transaction:
Dirty Reads returns different results within a single transaction when an SQL operation an
uncommitted or modified record created by another transaction. Dirty Reads increases
concurrency, but reduces consistency.
Non-Repeatable Reads returns different results within a single transaction when an SQL
operation reads the same row in a table twice. Non-Repeatable Reads can occur when another
transaction modifies and commits a change to the row between transaction reads. Non-
repeatable reads increases consistency, but reduces concurrency.
Phantoms returns different results within a single transaction when an SQL operation
retrieves a range of data values twice. Phantoms can occur if another transaction inserted a
new record and committed the insertion between executions of the range retrieval.
Each Isolation level differs in the phenomena it allows:

Transaction isolation Dirty Nonrepeatable Phantoms

level reads reads

Read uncommitted X X X

Read committed -- X X

Repeatable read -- -- X

Serializable -- -- --

 Read Uncommitted – Read Uncommitted is the lowest isolation level. In this level, one
transaction may read not yet commited changes made by other transaction, thereby
allowing dirty reads. In this level, transactions are not isolated from each other.
5.25 Database Management Systems

 Read Committed – This isolation level guarantees that any data read is committed at the
moment it is read. Thus it does not allows dirty read. The transaction hold a read or write
lock on the current row, and thus prevent other rows from reading, updating or deleting it.

 Repeatable Read – This is the most restrictive isolation level. The transaction holds read
locks on all rows it references and write locks on all rows it inserts, updates, or deletes.
Since other transaction cannot read, update or delete these rows, consequently it avoids
non repeatable read.

 Serializable – This is the Highest isolation level. A serializable execution is guaranteed to

be serializable. Serializable execution is defined to be an execution of operations in which
concurrently executing transactions appears to be serially executing.

5.6 SQL FACILITIES FOR CONCURRENCY AND RECOVERY

5.6.1 Crash Recovery

DBMS is a highly complex system with hundreds of transactions being executed
every second. The durability and robustness of a DBMS depends on its complex architecture
and its underlying hardware and system software. If it fails or crashes amid transactions, it is
expected that the system would follow some sort of algorithm or techniques to recover lost
data.

5.6.2 Failure Classification

To see where the problem has occurred, we generalize a failure into various
categories, as follows −
[Link] Transaction failure
A transaction has to abort when it fails to execute or when it reaches a point from
where it can’t go any further. This is called transaction failure where only a few transactions
or processes are hurt.
Reasons for a transaction failure could be −
 Logical errors − Where a transaction cannot complete because it has some code error
or any internal error condition.
 System errors − Where the database system itself terminates an active transaction
because the DBMS is not able to execute it, or it has to stop because of some system
condition. For example, in case of deadlock or resource unavailability, the system
aborts an active transaction.
 Concurrency Control 5.26

5.6.3 System Crash

There are problems − external to the system − that may cause the system to stop
abruptly and cause the system to crash. For example, interruptions in power supply may
cause the failure of underlying hardware or software failure.
Examples may include operating system errors.
5.6.4 Disk Failure
In early days of technology evolution, it was a common problem where hard-disk
drives or storage drives used to fail frequently. Disk failures include formation of bad sectors,
unreachability to the disk, disk head crash or any other failure, which destroys all or a part of
disk storage.
5.6.5 Storage Structure
We have already described the storage system. In brief, the storage structure can be divided
into two categories −
 Volatile storage − As the name suggests, a volatile storage cannot survive system
crashes. Volatile storage devices are placed very close to the CPU; normally they are
embedded onto the chipset itself. For example, main memory and cache memory are
examples of volatile storage. They are fast but can store only a small amount of
information.
 Non-volatile storage − These memories are made to survive system crashes. They
are huge in data storage capacity, but slower in accessibility. Examples may include
hard-disks, magnetic tapes, flash memory, and non-volatile (battery backed up) RAM.
5.6.6 Recovery and Atomicity
When a system crashes, it may have several transactions being executed and various
files opened for them to modify the data items. Transactions are made of various operations,
which are atomic in nature. But according to ACID properties of DBMS, atomicity of
transactions as a whole must be maintained, that is, either all the operations are executed or
none.
When a DBMS recovers from a crash, it should maintain the following −
 It should check the states of all the transactions, which were being executed.
 A transaction may be in the middle of some operation; the DBMS must ensure the
atomicity of the transaction in this case.
 It should check whether the transaction can be completed now or it needs to be rolled
back.
 No transactions would be allowed to leave the DBMS in an inconsistent state.
5.27 Database Management Systems

There are two types of techniques, which can help a DBMS in recovering as well as
maintaining the atomicity of a transaction −
 Maintaining the logs of each transaction, and writing them onto some stable storage
before actually modifying the database.
 Maintaining shadow paging, where the changes are done on a volatile memory, and
later, the actual database is updated.
5.6.7 Log-based Recovery
Log is a sequence of records, which maintains the records of actions performed by a
transaction. It is important that the logs are written prior to the actual modification and stored
on a stable storage media, which is failsafe.
Log-based recovery works as follows −
 The log file is kept on a stable storage media.
 When a transaction enters the system and starts execution, it writes a log about it.
 <Tn, Start>
 When the transaction modifies an item X, it write logs as follows −
 <Tn, X, V1, V2>
 It reads Tn has changed the value of X, from V1 to V2.
 When the transaction finishes, it logs −
 <Tn, commit>

The database can be modified using two approaches −

 Deferred database modification − All logs are written on to the stable storage and
the database is updated when a transaction commits.
 Immediate database modification − Each log follows an actual database
modification. That is, the database is modified immediately after every operation.
5.6.8 Recovery with Concurrent Transactions
When more than one transaction are being executed in parallel, the logs are
interleaved. At the time of recovery, it would become hard for the recovery system to
backtrack all logs, and then start recovering. To ease this situation, most modern DBMS use
the concept of 'checkpoints'.
[Link] Checkpoint
Keeping and maintaining logs in real time and in real environment may fill out all the
memory space available in the system. As time passes, the log file may grow too big to be
handled at all. Checkpoint is a mechanism where all the previous logs are removed from the
 Concurrency Control 5.28

system and stored permanently in a storage disk. Checkpoint declares a point before which
the DBMS was in consistent state, and all the transactions were committed.
[Link] Recovery
When a system with concurrent transactions crashes and recovers, it behaves in the
following manner −

Fig 5.15 Checkpoint versus Failure

 The recovery system reads the logs backwards from the end to the last checkpoint.

 It maintains two lists, an undo-list and a redo-list.

 If the recovery system sees a log with <Tn, Start> and <Tn, Commit> or just <Tn,
Commit>, it puts the transaction in the redo-list.
 If the recovery system sees a log with <Tn, Start> but no commit or abort log found, it
puts the transaction in undo-list.
All the transactions in the undo-list are then undone and their logs are removed. All the
transactions in the redo-list and their previous logs are removed and then redone before
saving their logs.
5.29 Database Management Systems

IMPORTANT QUESTIONS AND ANSWERS

PART – A

1. What are two pitfalls (problem) of lock-based protocols?

Shared Lock: If a Transaction Ti has obtained a shared mode lock on data item Q,
then Ti can read, but cannot write Q.
Exclusive Lock: If the transaction Ti has obtained a shared mode Lock on item Q,
then Ti can read and also write Q.

2. What is recovery management component?

Ensuring durability is the responsibility of a software component of the base
system called the recovery management component.
3. Give the reasons for allowing concurrency?
The reasons for allowing concurrency is if the transactions run serially, a
short transaction may have to wait for a preceding long transaction to complete,
which can lead to unpredictable delays in running a transaction. So concurrent
execution reduces the unpredictable delays in running transactions.
4. Define lock?
Lock is the most common used to implement the requirement is to allow a
transaction to access a data item only if it is currently holding a lock on that item.

5. What are the different modes of lock?

The modes of lock are:
 Shared Lock
 Exclusive Lock

6. Define deadlock?

Deadlock which defined as Neither of the transaction can ever proceed with its
normal execution.
7. Define the phases of two phase locking protocol
Growing phase: a transaction may obtain locks but not release any lock.
Shrinking phase: a transaction may release locks but may not obtain any new locks.

8. What are the time stamps associated with each data item?
 Concurrency Control 5.30

 W-timestamp (Q) denotes the largest time stamp if any transaction that
executed WRITE (Q) successfully.
 R-timestamp (Q) denotes the largest time stamp if any transaction that
executed READ (Q) successfully.

9. What are the three types of intent Lock?

 Intent Shared(IS)
 Intent Exclusive (IX)
 Shared Intent Exclusive(SIX)
10. Write about Time-stamp based protocol.
 Timestamp based protocol ensures Serializability. It selects an ordering
among transactions in advance using time stamps.

 With each Transaction in the system, a unique fixed timestamp is

associated. It is denoted by TS(Ti). This timestamp is assigned by the
database system before the transaction Ti status execution. If a transaction
Ti has been assigned timestamp TS(Ti) and new transaction Tj enters the
system, then TS(Ti)<TS(Tj).
11. Write short note on Two phase commit protocol.
The commit process proceeds as follows:
Phase 1
Each participating resource manager coordinates local operations and forces all log
records out:
(i)If successful, respond "OK"
(ii)If unsuccessful, either allow a time-out or respond "OOPS"
Phase 2
If all participants respond "OK":
(i)Coordinator instructs participating resource managers to "COMMIT"
(ii)Participants complete operation writing the log record for the commit
Otherwise:
(i)Coordinator instructs participating resource managers to "ROLLBACK"
(ii)Participants complete their respective local undos

12. Difference between Deadlock Prevention and Deadlock Avoidance

Deadlock Prevention:

 Preventing deadlocks by constraining how requests for resources can be

5.31 Database Management Systems

made in the system and how they are handled (system design).
 The goal is to ensure that at least one of the necessary conditions for
deadlock can never hold.

Deadlock Avoidance:

 The system dynamically considers every request and decides whether it is

safe to grant it at this point,
 The system requires additional apriori information regarding the overall
potential use of each resource for each process.
 Allows more concurrency.
13. What is Concurrency Control?

Process of managing simultaneous execution of transactions in a shared database,

to ensure the Serializability of transactions, is known as concurrency control.
14. What is meant by deadlock?
A system is in a deadlock state if there exists a set of transaction such that every
transaction in the set is waiting for another transaction in the set.

PART – B

1. How concurrency is performed. Explain the protocol which used in concurrency

concept.
2. Discuss in detail about two phase commit protocol.
3. Explain the concepts of Concurrency control mechanism.
4. Describe briefly about deadlock handling.
5. Discuss in detail about Lock based Protocol and Time Stamp based protocol.
6. Discuss about two phase locking techniques for concurrency control.
7. Explain Two Phase- Locking protocol. What benefit does strict two-phase
locking protocol provides? Discuss its disadvantages.
8. How the use of 2PL would prevent interference between two transactions.
9. Why concurrency control is needed? Explain the problems that would arise
when concurrency control is not provided by the database system.