Saritha D, Asst.

Professor, CSE, BGSIT, BG Nagar DBMS (22CS52)

Module 4
Transaction Processing Concepts

4.1 Introduction to Transaction Processing

Single-User versus Multiuser Systems
Transactions, Database Items, Read and Write Operations
Why Concurrency Control Is Needed
Why Recovery Is Needed
4.2 Transaction and System Concepts
Transaction States and Additional Operations
The System Log
Commit Point of a Transaction:
4.3 Desirable Properties of Transactions
4.4 Characterizing Schedules Based on Recoverability
4.5 Characterizing Schedules Based on Serializability
4.5.1 Testing conflict serializability of a Schedule S
4.6 Introduction to Concurrency Control
Two-Phase Locking Techniques for Concurrency Control
Types of Locks and System Lock Tables
Guaranteeing Serializability by Two-Phase Locking
Variations of Two-Phase Locking
Characterizing Schedules Based on Recoverability
schedule (or history): the order of execution of operations from all the various
transactions
Schedules (Histories) of Transactions: A schedule S of n transactions T1, T2 n

is a sequential ordering of the operations of the n transactions.

The transactions are interleaved
Two operations in a schedule are said to conflict if they satisfy all three of the following
conditions:
(1) they belong to different transactions;
(2) they access the same item X; and
(3) at least one of the operations is a write_item(X)
Conflicting operations:
r1(X) conflicts with w2(X) Read write
conflict r2(X) conflicts
with w1(X)
w1(X) conflicts with w2(X) Write
conflict r1(X) do not
conflicts with r2(X)
Schedules classified on recoverability:
Recoverable schedule:
One where no transaction needs to be rolled back.
A schedule S is recoverable if no transaction T in S commits until all transactions

Example:
Sc: r1(X); w1(X); r2(X); r1(Y); w2(X); c2; a1;
Sd: r1(X); w1(X); r2(X); r1(Y); w2(X); w1(Y); c1; c2;
Cascadeless schedule:
One where every transaction reads only the items that are written by committed
transactions.
Schedules requiring cascaded rollback:
A schedule in which uncommitted transactions that read an item from a failed
transaction must be rolled back.
Strict Schedules:
A schedule in which a transaction can neither read or write an item X until the
last transaction that wrote X has committed.
 [21CS53]

Characterizing Schedules Based on Serializability

schedules that are always considered to be correct when concurrent transactions are
executing are known as serializable schedules
Suppose that two users for example, two airline reservations agents submit to the
DBMS transactions T1 and T2 at approximately the same time. If no interleaving of
operations is permitted, there are only two possible outcomes:
1. Execute all the operations of transaction T1 (in sequence) followed by all the
operations of transaction T2 (in sequence).

2. Execute all the operations of transaction T2 (in sequence) followed by all the
operations of transaction T1 (in sequence).

Saritha D, Asst. Professor, CSE, BGSIT, BG Nagar

 [21CS53]

Serial schedule:
A schedule S is serial if, for every transaction T participating in the schedule, all
the operations of T are executed consecutively in the schedule.
Otherwise, the schedule is called nonserial schedule.
Serializable schedule:
A schedule S is serializable if it is equivalent to some serial schedule of the same
n transactions.
Result equivalent:
Two schedules are called result equivalent if they produce the same final state of
the database.
Conflict equivalent:
Two schedules are said to be conflict equivalent if the order of any two conflicting
operations is the same in both schedules.
Conflict serializable:
A schedule S is said to be conflict serializable if it is conflict equivalent to some

Being serializable is not the same as being serial

Being serializable implies that the schedule is a correct schedule.
It will leave the database in a consistent state.
The interleaving is appropriate and will result in a state as if the transactions
were serially executed, yet will achieve efficiency due to concurrent execution.

Testing conflict serializability of a Schedule S

For each transaction Ti participating in schedule S,create a node labeled Ti in the
precedence graph.
For each case in S where Tj executes a read_item(X) after Ti executes a write_item(X),
create an edge (Ti Tj) in the precedence graph.
For each case in S where Tj executes a write_item(X) after Ti executes a read_item (X)
,create an edge (Ti Tj) in the precedence graph.
For each case in S where Tj executes a write_item(X) after Ti executes a write_item(X),
create an edge (Ti Tj) in the precedence graph.
The schedule S is serializable if and only if the precedence graph has no cycles.

Saritha D , Asst. Professor, CSE, BGSIT, BG Nagar

 [21CS53]

[21CS53]

Fig: Constructing the precedence graphs for schedules A and D to test for conflict serializability.
(a) Precedence graph for serial schedule A.
(b) Precedence graph for serial schedule B.
(c) Precedence graph for schedule C (not serializable).
(d) Precedence graph for schedule D (serializable, equivalent to schedule A).

Saritha D, Asst. Professor, CSE, BGSIT, BG Nagar

 [21CS53]

Introduction to Concurrency Control

Purpose of Concurrency Control

To enforce Isolation (through mutual exclusion) among conflicting transactions.

To preserve database consistency through consistency preserving execution of
transactions.
To resolve read-write and write-write conflicts.

Example:
In concurrent execution environment if T1 conflicts with T2 over a data item A, then
the existing concurrency control decides if T1 or T2 should get the A and if the other
transaction is rolled-back or waits.

Two-Phase Locking Techniques for Concurrency Control

The concept of locking data items is one of the main techniques used for controlling the
concurrent execution of transactions.
A lock is a variable associated with a data item in the database. Generally, there is a lock
for each data item in the database.
A lock describes the status of the data item with respect to possible operations that can be
applied to that item.
 It is used for synchronizing the access by concurrent transactions to the database items.
 A transaction locks an object before using it.
When an object is locked by another transaction, the requesting transaction must wait.

Types of Locks and System Lock Tables

1. Binary Locks
A binary lock can have two states or values: locked and unlocked (or 1 and 0).
If the value of the lock on X is 1, item X cannot be accessed by a database operation that
requests the item

Saritha D, Asst. Professor, CSE, BGSIT, BG Nagar

 [21CS53]

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
We refer to the current value (or state) of the lock associated with item X as lock(X).
Two operations, lock_item and unlock_item, are used with binary locking.
A transaction requests access to an item X by first issuing a lock_item(X)
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 item X
When the transaction is through using the item, it issues an unlock_item(X) operation,
which sets LOCK(X) back to 0 (unlocks the item) so that X may be accessed by other
transactions
Hence, a binary lock enforces mutual exclusion on the data item.

lock_item(X):
B: if LOCK(X) = 0 (* item is unlocked *)
then LOCK(X)
else
begin
wait (until LOCK(X) = 0
and the lock manager wakes up the transaction); go
to B
end;
unlock_item(X):
LOCK(X
if any transactions are waiting
then wakeup one of the waiting transactions

Lock and unlock operations for binary locks.

Saritha D, Asst. Professor, CSE, BGSIT, BG Nagar

 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
The wait command within the lock_item(X) operation is usually implemented by putting
the transaction in a waiting queue for item X until X is unlocked and the transaction can
be granted access to it
Other transactions that also want to access X are placed in the same [Link], the
wait command is considered to be outside the lock_item operation.
It is quite simple to implement a binary lock; all that is needed is a binary-valued
variable, LOCK, associated with each data item X in the database
In its simplest form, each lock can be a record with three fields: <Data_item_name,
LOCK, Locking_transaction> plus a queue for transactions that are waiting to access the
item
If the simple binary locking scheme described here 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.

2. Shared/Exclusive (or Read/Write) Locks

binary locking scheme is too restrictive for database items because at most, one
transaction can hold a lock on a given item
should allow several transactions to access the same item X if they all access X for
reading purposes only
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 a multiple-mode lock is used

Saritha D, Asst. Professor, CSE, BGSIT, BG Nagar

 In this scheme called shared/exclusive or read/write locks there are three locking
operations: read_lock(X), write_lock(X), and unlock(X).

A read-locked item is also called share-locked because other transactions are allowed to
read the item, whereas a write-locked item is called exclusive-locked because a single
transaction exclusively holds the lock on the item
Method to implement read/write lock is to
- keep track of the number of transactions that hold a shared (read) lock
on an item in the lock table
- Each record in the lock table will have four fields:
<Data_item_name, LOCK, No_of_reads, Locking_transaction(s)>.
If LOCK(X)=write-locked, the value of locking_transaction(s) is a single transaction that
holds the exclusive (write) lock on X
If LOCK(X)=read-locked, the value of locking transaction(s) is a list of one or
more transactions that hold the shared (read) lock on X.

Saritha D, Asst. Professor, CSE, BGSIT, BG Nagar

 [21CS53]

When we use the shared/exclusive locking scheme, the system must enforce the following
rules:

1. A transaction T must issue the operation read_lock(X) or write_lock(X) before any

read_item(X) operation is performed in T.
2. A transaction T must issue the operation write_lock(X) before any
write_item(X) operation is performed in T.

3 A transaction T must issue the operation unlock(X) after all read_item(X) and
write_item(X) operations are completed in T.3

4. 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.

Conversion of Locks

A transaction that already holds a lock on item X is allowed under certain conditions to
convert the lock from one locked state to another
For example, it is possible for a transaction T to issue a read_lock(X) and then later to
upgrade the lock by issuing a write_lock(X) operation
- If T is the only transaction holding a read lock on X at the time it issues
the write_lock(X) operation, the lock can be upgraded;otherwise, the
transaction must wait

Saritha D, Asst. Professor, CSE, BGSIT, BG Nagar

 [21CS53]

Guaranteeing Serializability by 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 unlock operation in the transaction
Such a transaction can be divided into two phases:
Expanding or growing (first) phase, during which new locks on items can be
acquired but none can be released
Shrinking (second) phase, during which existing locks can be released but no
new locks can be acquired
If lock conversion is allowed, then upgrading of locks (from read-locked to write-
locked) must be done during the expanding phase, and downgrading of locks (from
write-locked to read-locked) must be done in the shrinking phase.
Transactions T1 and T2 in Figure (a) do not follow the two-phase locking protocol
because the write_lock(X) operation follows the unlock(Y) operation in T1, and similarly
the write_lock(Y) operation follows the unlock(X) operation in T2.

Transactions that do not obey two-phase locking (a) Two transactions T1 and T2 (b) Results of possible serial
schedules of T1 and T2 (c) A no serializable schedule S that uses locks

Saritha D, Asst. Professor, CSE, BGSIT, BG Nagar

 [21CS53]

If we enforce two-phase locking, the transactions can be rewritten as T T .

Now, the schedule shown in Figure (c) is not permitted for T1_ and T2_ (with their modified
order of locking and unlocking operations) under the rules of locking because T1_ will issue
its write_lock(X) before it unlocks item Y; consequently, when T2_ issues its read_lock(X),
it is forced to wait until T1_ releases the lock by issuing an unlock (X) in the schedule.

If every transaction in a schedule follows the two-phase locking protocol, schedule

guaranteed to be serializable
Two-phase locking may limit the amount of concurrency that can occur in a schedule
Some serializable schedules will be prohibited by two-phase locking protocol

Variations of Two-Phase Locking

Basic 2PL
Technique described previously
Conservative (static) 2PL
Requires a transaction to lock all the items it accesses before the transaction
begins execution by predeclaring read-set and write-set
Its Deadlock-free protocol

Saritha D, Asst. Professor, CSE, BGSIT, BG Nagar

 [21CS53]

Strict 2PL
guarantees strict schedules
Transaction does not release exclusive locks until after it commits or aborts
no other transaction can read or write an item that is written by T unless T
has committed, leading to a strict schedule for recoverability
Strict 2PL is not deadlock-free

Rigorous 2PL
guarantees strict schedules
Transaction does not release any locks until after it commits or aborts
easier to implement than strict 2PL

Saritha D, Asst. Professor, CSE, BGSIT, BG Nagar