DATABASE MANAGEMENT SYSTEM KCS

501
[Link] 3rd YEAR

UNIT 5 CONCURRENCY CONTROL TECHNIQUES - Lecture 1

Pallavi Shukla
Assistant Professor
Department of CSE
United College of Engg. and Research, Prayagraj, India
2
AKTU SYLLABUS -
 Concurrency Control Techniques:
 Concurrency Control,
 Locking Techniques for Concurrency Control,
 Time Stamping Protocols for Concurrency Control,
 Validation Based Protocol,
 Multiple Granularity,
 Multi Version Schemes,
 Recovery with Concurrent Transaction,
 Case Study of Oracle.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

3 COURSE OUTCOME -

Design, develop and implement a small database

project using database tools.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

4 LECTURE OUTLINE-
 Concurrency Control
 Concurrent Execution in DBMS.
 Why Concurrency control is needed?
 Lost Update Problem.
 Dirty Read Problem.
 Unrepeatable Read Problem
 Phantom Read Problem
 Lock
 Types of Locks
 Concurrency Control Protocols
• Lock Based Concurrency Control Protocol
• Time Stamp Concurrency Control Protocol
• Validation Based Concurrency Control Protocol

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

5 CONCURRENCY CONTROL -
 It is the management procedure that is required for controlling
concurrent execution of the operations that take place on a
database.
 It is process of managing simultaneous operations (Queries,
updates, inserts , deletes) on the database without having them
interfere with one another.
 It is the working concept that is required for controlling and
managing the concurrent execution of database operations and
thus avoiding the inconsistencies in the database. Thus, for
maintaining the concurrency of the database, we have the
concurrency control protocols.
 It can be performed by the DBMS within various methods such as
Locking methods, Timestamps methods, validation based
techniques & optimistic methods.
DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5
6 CONCURRENCY CONTROL -

is provided in a database to:

(i) enforce isolation among transactions.

(ii) preserve database consistency through consistency
preserving execution of transactions.
(iii) resolve read-write and write-read conflicts.
(iv) ensure serializability.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

7 CONCURRENT EXECUTION IN DBMS -
• In a multi-user system, multiple users can access and use the same
database at one time, which is known as the concurrent execution of the
database. It means that the same database is executed simultaneously on
a multi-user system by different users.
• While working on the database transactions, there occurs the
requirement of using the database by multiple users for performing
different operations, and in that case, concurrent execution of the
database is performed.
• The thing is that the simultaneous execution that is performed should be
done in an interleaved manner, and no operation should affect the other
executing operations, thus maintaining the consistency of the database.
Thus, on making the concurrent execution of the transaction operations,
there occur several challenging problems that need to be solved.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

8 WHY CONCURRENCY CONTROL IS
NEEDED?
 In a database transaction, the two main operations
are READ and WRITE operations. So, there is a need to manage these
two operations in the concurrent execution of the transactions as if
these operations are not performed in an interleaved manner, and the
data may become inconsistent. So, the following problems occur with
the Concurrent Execution of the operations:

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

9 PROBLEMS IN CONCURRENCY CONTROL -

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

10 LOST UPDATE PROBLEM-
The problem occurs when two different database transactions
perform the read/write operations on the same database items
in an interleaved manner (i.e., concurrent execution) that
makes the values of the items incorrect hence making the
database inconsistent.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

  Consider the below diagram where two transactions TX and TY, are
11
performed on the same account A where the balance of account A is Rs.
300.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

12 • At time t1, transaction TX reads the value of account A, i.e., 300 (only
read).
• At time t2, transaction TX deducts 50 from account A that becomes 250
(only deducted and not updated/write).
• Alternately, at time t3, transaction TY reads the value of account A that
will be 300 only because TX didn't update the value yet.
• At time t4, transaction TY adds 100 to account A that becomes 400 (only
added but not updated/write).
• At time t6, transaction TX writes the value of account A that will be
updated as 250 only, as TY didn't update the value yet.
• Similarly, at time t7, transaction TY writes the values of account A, so it will
write as done at time t4 that will be 400. It means the value written by
TX is lost, i.e., 250 is lost.
 Hence data becomes incorrect, and database sets to inconsistent.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

13 DIRTY READ PROBLEM-
The dirty read problem occurs when one transaction updates
an item of the database, and somehow the transaction fails,
and before the data gets rollback, the updated database item
is accessed by another transaction. There comes the Read-
Write Conflict between both transactions.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

 Consider two transactions TX and TY in the below diagram
14
performing read/write operations on account A where the
available balance in account A is Rs. 300.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

15 • At time t1, transaction TX reads the value of account A, i.e., 300.
• At time t2, transaction TX adds 50 to account A that becomes 350.
• At time t3, transaction TX writes the updated value in account A,
i.e., 350.
• Then at time t4, transaction TY reads account A that will be read as
350.
• Then at time t5, transaction TX rollbacks due to server problem, and
the value changes back to 300 (as initially).
• But the value for account A remains 350 for transaction TY as
committed, which is the dirty read and therefore known as the Dirty
Read Problem.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

16 UNREPEATABLE READ PROBLEM -

Also known as Inconsistent Retrievals Problem.

It occurs when in a transaction, two different values are read for
the same database item.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

17 Consider two transactions, TX and TY, performing the read/write
operations on account A, having an available balance = 300. The
diagram is shown below:

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

18 • At time t1, transaction TX reads the value from account A, i.e., 300.
• At time t2, transaction TY reads the value from account A, i.e., 300.
• At time t3, transaction TY updates the value of account A by adding 100 to the
available balance, and then it becomes 400.
• At time t4, transaction TY writes the updated value, i.e., 400.
• After that, at time t5, transaction TX reads the available value of account A, and
that will be read as 400.
• It means that within the same transaction TX, it reads two different values of
account A, i.e., 300 initially, and after updation made by transaction TY, it reads
400. It is an unrepeatable read and is therefore known as the Unrepeatable read
problem.
 Thus, in order to maintain consistency in the database and avoid such problems
that take place in concurrent execution, management is needed, and that is where
the concept of Concurrency Control comes into role.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

19 PHANTOM READ PROBLEM -
The phantom read problem occurs when a transaction reads a
variable once but when it tries to read that same variable
again, an error occurs saying that the variable does not exist.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

20

Example: In the above example, once transaction T2 reads the

variable X, transaction 1 deletes the variable X without
transaction T2 knowledge.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

21 CONCURRENCY CONTROL PROTOCOLS -
The concurrency control protocols ensure the atomicity,
consistency, isolation, durability and serializability of the
concurrent execution of the database transactions. Therefore,
these protocols are categorized as:

• Lock Based Concurrency Control Protocol

• Time Stamp Concurrency Control Protocol
• Validation Based Concurrency Control Protocol

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

22 LOCK -
Lock is a variable associated with a data item that describes
the status of the item with respect to possible operations that
can be applied to it.
There is one lock for each data item in the database.
Locks are used as a means of synchronizing the access by
concurrent transactions to the database item.
In lock based protocol, any transaction cannot read or write
data until it acquires an appropriate lock on it.
23 Types Of Locks -
 There are two types of lock:

 1. Binary Locks
 2. Shared / Exclusive Locks
 3. Two phase Locking
 a) Conservative 2PL
 b) Strict 2PL
 c) Rigorous 2PL

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

24
BINARY LOCKS -
 It can have two states or values: locked or unlocked.
 A distinct lock is associated with each database 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
requested, and the lock value is changed to 1.
 Two operations lock_item and unlock_item, are used with binary
locking.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

25 BINARY LOCKS -

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

26 BINARY LOCKS -
A transaction request access to an item X by first issuing a
Lock_item() operation.
If Lock(X) = 1, the transaction is forced to wait.
If Lock(X) = 0, It is set to 1(the transaction locks the item) , and
the transaction is allowed to access the item.
When transaction is over then, it issues Unlock_item(x)
operation, which set Lock(x) back to 0 so that X may be
accessed by other transactions.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

 lock_item(X);
27
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 transactions are waiting
then wakeup one of the waiting transactions;

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

  Lock_item & Unlock_item operations must be implemented as indivisible
28 units(known as Critical Sections In OS) i.e no interleaving should be
allowed once a lock or unlock operation is started until the operation
terminates or the transaction waits.
 Each Lock can be a record with three fields
<Data_item_name, Lock , Locking_transactions>
plus a queue for transactions that are waiting to access the item.
 The system needs to maintain only these records for the items that are
currently locked in a lock table, which could be organized as a hash file on
the item name.
 Items not in the lock table are considered to be unlocked.
 DBMS has a lock manager subsystem to keep track of and control access
to locks.
DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5
29 RULES FOR ENFORCING BINARY LOCKS-
 Every transaction must follow rules:
 a) A transaction T must issue the operation lock_item(X) before any
read_item(X) or write_item(X) operations are performed in T.
 b) A transaction T must issue the opeartion unlock_item(X) after all
read_item(X) and write_item(X) operations are completed in T.
 c) A transaction T will not issue a lock_item(X) operation if it already holds
the lock on the item X.
 d) A transaction T will not issue an unblock_item(X) operation unless it
already holds the lock on item X.
 These rules can be enforced by the lock manager module of the DBMS.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

30 MERITS OF BINARY LOCKS-

• They are simple to implement since they are effectively

mutually exclusive and establish isolation perfectly.
• Binary Locks demand less from the system since the system
must only keep a record of the locked items. The system is
the lock manager subsystem which is a feature of all DBMSs
today.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

31 DRAWBACKS OF BINARY LOCKS-

• Binary locks are highly restrictive.

• They do not even permit reading of the contents of item X.
• As a result, they are not used commercially.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

32 SHARED/ EXCLUSIVE (Read/Write) LOCKS-
 We should allow several transactions to access the same item x
if they all access X for reading purpose only.
 However , if a transaction is to write an item X, it must have
exclusive access to X.
 For this purpose , a different type of Lock called Multiple_Mode
Lock is used.
 In this scheme called Shared / exclusive (Read/Write ) Locks
there are three locking operations: read_Lock(X), write_Lock(X)
and Unlock(X).

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

33 SHARED/ EXCLUSIVE (Read/Write) LOCKS-
 A Lock associated with an item(x) , Lock(X) now has three
possible states
 a) read_locked / shared locked because other transactions
are called to read the item.
 b) write_locked / Exclusive locked because single transaction
exclusively holds the lock on the item.
 c) unlocked

 One method for implementing preceding operations on a

read/write lock is to keep track of the number of transactions
that hold a shared (read) lock on an item in the LockTable.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

34 SHARED/ EXCLUSIVE (Read/Write) LOCKS-
 Each record in the Lock Table will have four fields
< Data_item_name, LOCK, no_of_records, Locking _transactions>
 To save space, the system needs to maintain lock records only
for locked items in the Lock_table.
 The value(state) of LOCK is either read_locked or write_locked.
 If Lock(X) = write_Locked, the value of locking transactions is a
single transaction that holds the exclusive lock on X.
 If Lock(X) = read_Locked, the value of locking transactions is a
list of one or more transactions that hold the shared Lock on x.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

35 RULES FOR ENFORCING SHARED/EXCLUSIVE
LOCKS-
 a) A Transaction T must issue the operation read_Lock(X) Oor write_Lock(X)
before any read_item(X) operation is performed in T.
 b) A transaction T must issue the operation write_lock(X) before any
write_item (X) operation is performed in T.
 c) A Transaction T must issue the operation unlock(X) after all read_item(x)
& Write_item(x) operations are completed in T.
 d) A transaction T will not issue a read_lock(X) operation if it already holds
a read(shared) Lock or a write (exclusive) lock on item X.
 e) A Transaction T will not issue a write_lock(x) operation if it already holds a
read(shared) lock or write (exclusive) lock on item X.
 f) a Transaction T will not issue an unlock(X) operation unless it already
holds a read(shared) lock or a write (exclusive) lock on item X.
 Read_Lock(X)
36
B: If Loock(X) = “unlocked”
then begin LOCK(X)  “read_Locked”;
no_of_reads(X)  1
end
else if lock(x) =“read_locked”
then no_of_reads(x)  no_of_reads +1
else begin
wait(until Lock(X) = “unlocked”
and the lock manager wakes up the transaction);
goto B
End;

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

37  Write_lock(X) -
B: if Lock(Y) = “unlocked”
then Lock(X)  ‘write_locked’
else begin
wait (until Lock(X) = ‘unblocked”
and the lock manager wakes up the transaction):
goto B;
end

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

38  Unlock(X) :
if LOCK(X) = ‘write_locked’
then begin LOCK(X)  ‘unblocked’
wakeup one of the waiting transactions , if any
end
else if LOCK(X) = ‘read_locked’
then begin
no_of_reads(X)  no_of_reads(X) – 1;
if no_of_reads(X)= 0
then begin LOCK(X) = ‘UNBLOCKED’;
wakeup one of the waiting transactions , if any
end
end;

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

39 Difference between Shared Lock and Exclusive
Lock :
[Link]. Shared Lock Exclusive Lock
1. Lock mode is read only operation. Lock mode is read as well as write operation.

Shared lock can be placed on objects

Exclusive lock can only be placed on objects
2. that do not have an exclusive lock
that do no have any other kind of lock.
already placed on them.
Prevents others from reading or updating the
3. Prevents others from updating the data.
data.

Issued when transaction wants to read Issued when transaction wants to update
4.
item that do not have an exclusive lock. unlocked item.

Any number of transaction can hold Exclusive lock can be hold by only one
5.
shared lock on an item. transaction.
6. S-lock is requested using lock-S instruction. X-lock is requested using lock-X instruction.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

40 TWO PHASE LOCKING -
 A transaction is said to follow the two phase locking protocol if all locking
operations (read_lock, write_lock) precede the first operation in the
transaction.
 Such transaction can be divided into two phases.
 Expanding Phase
 Shrinking phase
EXPANDING PHASE –
 This is first phase in which new locks on items can be acquired but none can be
released.
SHRINKING PHASE –
 This is phase during which existing locks can be released but no new locks can be
acquired.
DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5
41  If lock conversion is allowed , then upgrading of locks from read_locked to
write_locked must be done during the expanding phase.
 Downgrading of locks (from write_locked to read_locked) must be done in
the shrinking phase.

T1 T2
read__Lock(Y); read__Lock(X);
read_item(Y); read_item(X);
unlock(Y); unlock(X);
write_lock(X); write_lock(Y);
read_item(X); read_item(Y);
X =X+Y; Y =X+Y;
write_item(X); write_item(Y);
unlock(X); unlock(Y);
42  T1 and T2 do not follow the Two Phase Locking protocol because the
write_Lock(X) operations follows the unlock(Y) operation in T1 &
write_lock(Y) operations follows the unlock(X) operation in T2.
 After enforcing Two Phase Locking System –
T1 T2
read__Lock(Y); read__Lock(X);
read_item(Y); read_item(X);
Write_Lock(X); Write_lock(Y);
unLock(Y); unLock(X);
write_lock(X); read_item(Y);
read_item(X); Y =X+Y;
X =X+Y; write_item(Y);
write_item(X); unLock(Y);
unLock(X);
43  It can be proved that, if every transaction in a schedule
follows the two phase locking protocol, the schedule is
guaranteed to be serializable, obviating the need to test for
serializability of schedules.

 TYPES OF TWO PHASE LOCKING TECHNIQUES –

Conservative 2PL(Static 2PL)
Strict 2PL
Rigorous 2PL

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

44 Conservative 2PL-
 It requires a transaction to lock all the items it accesses
before the transaction begins execution, by predeclaring its
read_set & write_set.
 Read_set is the set of all items that the transaction reads
 Write_set is the set of all items that it writes.

 If any of the predeclared items need cannot be locked , the

transaction does not lock any item; instead it waits until all
the items are available for Locking.
 Conservative 2PL is a deadlock free protocol.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

45 Strict 2PL -
 It guarantees strict schedules.
 In this variation , a transaction T does not release any of its
exclusive (write) locks until after it commits or aborts.
 Hence, no other transactions can read or write an item that
is written by T unless T has committed , leading to a strict
schedule for recoverability , it is not deadlock free.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

46 Rigorous 2PL -
 It also guarantees strict schedules
 In this variation a transaction T does not release any of its locks (exclusive or
shared) until after it commits or aborts and so it is easier to implement than strict 2
PL.

Difference between Conservative & Regressive 2PL-

 Conservative 2 PL lock all its items before it starts so once the transaction starts it is
in its shrinking phase.
 Regressive 2PL does not unlock any off its items until after it terminates (by
committing or aborting) so the transactions is in its expanding phase until it ends.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

47

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

48

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

49

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

50

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

51

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

52

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

53

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

54 Multiple Granularity -
 Consider the following granularity hierarchy

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

55

 This tree consists of four levels of nodes. The highest level

represents the entire database. Below it are nodes of
type area; the database consists of exactly these areas.
Each area in turn has nodes of type file as its children.
Each area contains exactly those files that are its child
nodes. No file is in more than one area. Finally, each file
has nodes of type record. As before, the file consists of
exactly those records that are its child nodes, and no
record can be present in more than one file.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

56
 This protocol uses the following compatibility matrix to lock the data items.

 There is an intention mode associated with shared mode, and there is one
with exclusive mode. If a node is locked in intention-shared (IS) mode,
explicit locking is being done at a lower level of the tree, but with only
shared-mode locks.
DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5
57  Similarly, if a node is locked in intention-exclusive (IX) mode, then explicit locking is
being done at a lower level, with exclusive-mode or shared-mode locks.
 Finally, if a node is locked in shared and intention-exclusive (SIX) mode, the sub-tree
rooted by that node is locked explicitly in shared mode, and that explicit locking is
being done at a lower level with exclusive-mode locks.
 The multiple-granularity locking protocol, which ensures serializability, is this:
 Each transaction Ti can lock a node Q by following these rules:
 1. It must observe the lock-compatibility function shown in above matrix.
 2. It must lock the root of the tree first, and can lock it in any mode.
 3. It can lock a node Q in S or IS mode only if it currently has the parent of Q locked in
either IX or IS mode.
 4. It can lock a node Q in X, SIX, or IX mode only if it currently has the parent of Q
locked in either IX or SIX mode.
 5. It can lock a node only if it has not previously unlocked any node (that is, Ti is two
phase).
 6. It can unlock
DEVELOPED aSHUKLA,
BY- PALLAVI node UCERQ only if it currently has none ofUNIT
the 5 children of Q locked.
58  Clearly, 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.
 Example: Consider the tree shown in the above figure and these transactions:
 • Suppose that transaction T18 reads record ra2 in file Fa. Then, T18 needs to lock
the database, area A1, and Fa in IS mode (and in that order), and finally to lock
ra2 in S mode.
 • Suppose that transaction T19 modifies record ra9 in file Fa. Then, T19 needs to
lock the database, area A1, and file Fa in IX mode, and finally to lock ra2 in X
mode.
 Suppose that transaction T20 reads all the records in file Fa. Then, T20 needs to
lock the database and area A1 (in that order) in IS mode, and finally to lock Fa in
S mode.
 • Suppose that transaction T21 reads the entire database. It can do so after
locking the database in S mode.
 Clearly, transactions T18, T20, and T21 can access the database concurrently.
Transaction T19 can execute concurrently with T18, but not with either T20 or T21.
DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5
59
 This protocol enhances concurrency and reduces lock overhead. It is
particularly useful in applications that include a mix of
 • Short transactions that access only a few data items
 • Long transactions that produce reports from an entire file or set of files
 Note: Deadlock is possible in this protocol.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

60 MULTIVERSION SCHEMES -
 In multiversion concurrency control schemes, each write(Q) operation creates a
new version of Q. When a transaction issues a read(Q) operation, the
concurrency control manager selects one of the versions of Q to be read. The
concurrency-control scheme must ensure that the version to be read is selected
in a manner that ensures serializability.

MULTIVERSION TIMESTAMP ORDERING-

 With each data item Q, a sequence of versions < Q1, Q2, ..., Qm > is associated.
Each version Qk contains three data fields:
 • Content is the value of version Qk .
 • W-timestamp(Qk ) is the timestamp of the transaction that created version Qk .
 • R-timestamp(Qk ) is the largest timestamp of any transaction that successfully
read version Qk

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

61  A transaction Ti creates a new version Qk of data item Q by issuing a write(Q)
operation. The content field of the version holds the value written by Ti . The system
initializes the W-timestamp and R-timestamp to TS(Ti). It updates the R-timestamp
value of Qk whenever a transaction Tj reads the content of Qk , and R-
timestamp(Qk ) < TS(Tj ).
 The multiversion timestamp-ordering scheme operates as follows. Suppose that
transaction Ti issues a read(Q) or write(Q) operation. Let Qk denote the version of
Q whose write timestamp is the largest write timestamp less than or equal to TS(Ti).
 1. If transaction Ti issues a read(Q), then the value returned is the content of
version Qk .
 2. If transaction Ti issues write(Q), and if TS(Ti)¡R-timestamp(Qk ), then the system
rolls back transaction Ti . On the other hand, if TS(Ti) = W-timestamp(Qk ), the
system overwrites the contents of Qk ; otherwise it creates a new version of Q

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

62  Versions that are no longer needed are removed according to the following rule.
Suppose that there are two versions, Qk and Qj , of a data item, and that both
versions have a W-timestamp less than the timestamp of the oldest transaction in
the system. Then, the older of the two versions Qk and Qj will not be used again,
and can be deleted.

 Note:

 1. The multiversion timestamp-ordering scheme ensures serializability.

 2. The multiversion timestamp-ordering scheme does not ensure recoverability and

cascadeless ness.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

63 DEADLOCK -
 Deadlock occurs when each transaction T in a set of two or
more transactions is waiting for some that is locked by some
other transactions T’ in the set.
 Hence, each transaction in the set is on a waiting Queue ,
waiting for one of the other transactions in the set to release
the lock of an item.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

 T1’ T2’
64
read_lock(Y);
read_item(Y);
read_lock(X);
read_item(X);

write_lock(X);
write_lock(Y);

T1’ T2’

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

65  Here the two transactions T1’ & T2’ are deadlocked in a
partial schedule .
 T1’ is on the waiting queue for X, which is locked by T2’ , while
T2’ is on the waiting queue y, which is locked by T1’.
 Meanwhile ,neither T1’ nor T2’ nor any other transactions can
access items X & Y.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

66 DEADLOCK PREVENTION PROTOCOLS-
 One way to prevent deadlock is to use a Deadlock
preventive Protocol.
 FIRST PROTOCOL–
 This requires that every lock all the item it needs in advance
(which is generally not a practical assumption ) if any of the
items cannot be obtained , none of the items are locked.
 The transaction waits & then tries again to lock all the items it
needs.
 This solution further limits concurrency.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

67  SECOND PROTOCOL –
 A second protocol , which also limits concurrency , involves
ordering all the items in the database & making sure that a
transaction that needs several items will lock them according
to that order.
 This requires that the programmer(or the system) is aware of
the chosen order of the items , which is also not practical in
the database context.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

  WAIT DIE –
68
If Ts(Ti) < Ts(Tj), then (Ti is older than Tj) Ti is allowed to wait otherwise(Ti younger
than Tj) abort Ti (Ti dies) and restart it later with the timestamp.

 WOUND WAIT –
If Ts (Ti) < Ts(Tj) , then (Ti older than Tj) abort Tj(Ti wounds Tj) and restart it later with
the same timestamp otherwise (Ti younger than Tj) Ti is allowed to wait.

In a wait die , an older transaction is allowed to wait on a younger transaction ,

whereas a younger transaction requesting an item held by an older transaction is
aborted and restarted.
The wound wait approach does the opposite : A younger transaction is allowed
to wait or an older one, whereas an older transaction requesting an item held by a
younger transaction preempts the younger transaction by aborting it.
Both scheme end up aborting the younger of the two transaction that may be
involved in a deadlock.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

69 No Waiting Algorithm -
 In the no waiting algorithm , if a transaction is unable to obtain
a lock, it is immediately aborted and then restarted after a
certain time delay without checking a weather a deadlock
will actually occur or not.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

70 Cautious Waiting -
 In the No waiting algorithm transactions abort & restart
needlessly , therefore the cautious waiting algorithm was
proposed to try to reduce the number of needless
aborts /restarts.
 Suppose that transaction Ti tries to lock an item X but is
not able to do so because X is locked by some other
transactions Tj with a conflicting Lock.
 Rules :
 If Tj is not blocked (not waiting for some other item) then
Tj is blocked & allowed to wait ;otherwise abort Tj.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

71 DEADLOCK DETECTION-
 Deadlock Detection where the system checks if a state of deadlock
actually exists.
 This can happen if the transactions are short & each transaction
locks only a few items,or if the transaction load is light.
 Simple way to detect a state of deadlock is for the system to
construct & maintain a wait for graph.
 One node is created in the wait for graph for each transaction that
is currently executing.
 Whenever a transaction Ti is waiting to lock an item X that is
currently locked by a transaction Tj, a directed edge (Ti→ Tj) is
created in the wait for graph.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

72  When Tj releases the lock(s) an the items that Ti was waiting for
, the directed edge is dropped from the wait for graph.
 We have a state of deadlock if and only if the wait for graph
has a cycle.
 The algorithm ensure that for each item accessed by
conflicting operations in the schedule , the order in which the
item is accessed does not violate the serializability order.
 To do this, the algorithm associates with each database item
X two timestamp(Ts) values.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

73 Deadlock Detection -
 To identify the deadlock is present in the system, we use a directed graph
called wait-for-graph.
 In this graph, vertices are corresponding to transactions. When transaction
Ti requests a data item currently being held by transaction Tj , then the
edge Ti → Tj is inserted in the wait-for graph. This edge is removed only
when transaction Tj is no longer holding a data item needed by transaction
Ti .
 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 deadlocked. To
detect deadlocks, the system needs to maintain the wait-for graph, and
periodically to invoke an algorithm that searches for a cycle in the graph.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

74

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

75

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

76  When a detection algorithm determines that a deadlock exists, the system must
recover from the deadlock. The most common solution is to roll back one or more
transactions to break the deadlock. Three actions need to be taken:
 1. Selection of a victim: Given a set of deadlocked transactions, we must
determine which transaction (or transactions) to roll back to break the deadlock.
We should roll back those transactions that will incur the minimum cost.
Unfortunately, the term minimum cost is not a precise one. Many factors may
determine the cost of a rollback, including
 1. How long the transaction has computed, and how much longer the
transaction will compute before it completes its designated task.
 2. How many data items the transaction has used.
 3. How many more data items the transaction needs for it to complete.
 4. How many transactions will be involved in the rollback.
77  2. Rollback: Once we have decided that a particular transaction must be rolled
back, we must determine how far this transaction should be rolled back. The
simplest solution is a total rollback:

 3. Starvation: In a system where the selection of victims is based primarily on cost

factors, it may happen that the same transaction is always picked as a victim. As
a result, this transaction never completes its designated task, thus there is
starvation. We must ensure that transaction can be picked as a victim only a
(small) finite number of times. The most common solution is to include the number
of rollbacks in the cost factor.

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

78 The Phantom Phenomenon -

 Consider transaction T29 that executes the following SQL query on the bank
database:
 select sum(balance) from account where branch-name = ’Perryridge’
 Transaction T29 requires access to all tuples of the account relation
pertaining to the Perryridge branch.
 Let T30 be a transaction that executes the following SQL insertion:
 insert into account values (A-201, ’Perryridge’, 900)

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5

79  Let S be a schedule involving T29 and T30 . We expect there to be potential for a
conflict for the following reason:
 • If T29 uses the tuple newly inserted by T30 in computing sum(balance), then T29
read a value written by T30. Thus, in a serial schedule equivalent to S, T30 must come
before T29.
 • If T29 does not use the tuple newly inserted by T30 in computing sum(balance),
then in a serial schedule equivalent to S, T29 must come before T30.
 The second of these two cases is curious. T29 and T29 do not access any tuple in
common, yet they conflict with each other! In effect, T29 and T29 conflict on a
phantom tuple. If concurrency control is performed at the tuple granularity, this
conflict would go undetected. This problem is called the phantom phenomenon. To
prevent the phantom phenomenon, we allow T29 to prevent other transactions from
creating new tuples in the account relation with branch-name = “Perryridge.”

DEVELOPED BY- PALLAVI SHUKLA, UCER UNIT 5