Unit 5

Transaction Processing and Concurrency control and Recovery

Introduction to Transaction Processing:
• It is a logical unit of database processing that includes one or more
access operations. (read-retrieval, write-insert or update). It is a unit
of program execution that accesses and if required updates various
data items.
A transaction is a set of operations that can either be embedded
within an application program or can be specified interactively via a
high-quality language such as SQL.
Transaction Concepts:
• A transaction is a unit of program execution that accesses and
possibly updates various data items.A transaction includes one or
more database access operations these can include insertion
,deletion, modification, or retrieval operations. Usually, a transaction
is initiated by a user program written in a high level data manipulation
language(SQL) or programming language(C++,Java), with embedded
database accesses in ODBC(Open Database Connectivity) or
JDBC(java database connectivity).The transaction consists of all
operations executed between the begin transaction and end
transaction. If the database operations in transaction do not update
the database but only retrieve data, the transaction is called a read
only transaction, otherwise it is known as a read write transaction.
System Concepts
• Transaction processing system are systems with large databases and
hundreds of concurrent users executing database transactions.
Examples of such system include airline reservations, banking, credit
card processing, online retail purchasing, stock markets . These
systems the concept of a transaction, which is used to represent a
logical unit of database processing that must be completed in its
entirety to ensure correctness.
Desirable Properties of Transactions:
• The transaction refers to a small unit of any given program that consists of various low-level tasks. Every transaction in
DBMS must maintain ACID – A (Atomicity), C (Consistency), I (Isolation), D (Durability). One must maintain ACID so as
to ensure completeness, accuracy, and integrity of data.
• 1. Atomicity:The property of atomicity states that we must treat any given transaction as an atomic unit. It
means that either all or none of its operations need to be executed. One must ensure that there is no state in the
database in which a transaction happens to be left partially completed. One must either define the states
before or after the execution/failure/abortion of the transaction.
• 2. Consistency:The property of consistency states that the database must always remain in a consistent state
after any transaction. Thus, a transaction must never have any damaging effect on the data and information
that resides in the database. In case, before the execution of a transaction, the database happens to be in a
consistent state, then it has to remain consistent even after the transaction gets executed.
• 3. Durability:The property of durability states that any given database must be durable enough to all of its
latest updates, and it must happen even if the system suddenly restarts or fails. The database would hold the
modified data in case a transaction updates and commits some chunk of information in the database. In case a
transaction commits and yet the system fails before we write the data on the disk, then the information would
be actually updated after the system springs back into action.
• 4. Isolation:The property of isolation states that when multiple transactions are being simultaneously
executed and in parallel in a database system, then the carrying out and execution of the transaction would
occur as if it is the only transaction that exists in the system. None of the transactions would affect any other
transaction’s existence.
Serializable Schedule:
• When several concurrent transactions are trying to access the same
data item, the instructions within these concurrent transactions must
be ordered in some way so as there are no problem in accessing and
releasing the shared data items. We can ensure consistency of the
database under concurrent execution by making sure that any
schedule that is executed has the same effect as a schedule that could
have occurred without any concurrent execution. That concurrent
schedule which is equivalent to a serial schedules is called serializable
schedule.
Types of Serializability
1)Conflict Serializability
2)View Serializability.
1)Conflict Serializability
• It does not contains loop and cycle while in precedence graphs.
• Two instructions of two different transactions may want to access the
same data item in order to perform a read/write operation.Conflict
Serializability deals with detecting whether the instructions are
conflicting in any way, and specifying the order in which these two
instructions will be executed in case there is any conflict.A conflict
arises if at least one of the instructions is a write operation.The
following rules are important in conflict serializability.
• Conflict pairs condtions:
W-W
R-W
W-R
• A) If two instructions of the two concurrent transactions are both for read
operation, then they are not in conflict, and can be allowed to take place in
any order.
• B)If one of the instructions wants to perform a read operation and the
other instruction wants to perform a write operation, then they are in
conflict, hence their ordering is important. If the read instruction is
performed first, then it reads the old value of the data item and after the
reading is over, the new value of the data item is written. If the write
instruction is performed first, then updates the data item with the new
value and the read instruction reads the newly updated value.
• C) If both the transactions are for write operation, then they are in conflict
but can be allowed to take place in any order, because the transaction do
not read the value updated by each other. However, the value that persists
in the data item after the schedule is over is the one written by the
instruction that performed the last write.
2)View Serializability.
• A schedule is said to be view serializable, if it has an equivalent view
equivalent schedule.
• There are several other types of serializability that offer less stringent
definitions of schedule equivalence than that that offered by conflict
serializability. One less restrictive definition is called view serializability.
Two schedules S and S’ consisting of the same operations from n
transactions T1,T2,…..Tn are view equivalent if the following three
conditions hold:
a) For each data item X, if transaction 𝑇𝑖 reads the initial values of X in
schedule S, if the value read by 𝑇𝑖 must also read the initial value of X in
schedule S’.
b) For each read operation on data item X by transaction 𝑇𝑖 in schedule S, if
the value read by 𝑇𝑖 has been written by transaction 𝑇𝑗 , then transaction
𝑇𝑖 must also read the value of X produced by transaction 𝑇𝑗 in schedule
S’.
C) For each data item X, if the last write operation on X was performed
by transaction 𝑇𝑖 in schedule S, the same transaction must perform the
final write on data item X in schedule S’.
Except in these three cases any alteration can be possible while
creating S’ by modifying S.
Two-Phase Locking Concurrency Control
Techniques:
• The use of locks has helped us to create neat and clean concurrent
schedule. The two Phase Locking protocol defines the rules of how to
acquire the locks on a data item and how to release the locks to ensure the
serializability. The Two Phase Locking Protocol assumes that a transaction
can only be in one of two phases: an expanding or growing phase and a
shrinking phase.
a) Growing Phase: In this phase the transaction can only acquire locks, but
cannot release any lock. The transaction enters the growing phase as soon as
it acquires the first lock it wants. From now on it has no option but to keep
acquiring all the locks it would need. It cannot release any lock at this phase
even if it has finished working with a locked data item.Ultimately the
transaction reaches a point where all the lock it may need has been
acquired. This point is called Lock Point.
b) Shrinking Phase:
• After Lock Point has been reached, the transaction enters the
shrinking phase. In this phase the transaction can only release locks,
but cannot acquire any new lock. The transaction enters the shrinking
phase as soon as it releases the first lock after crossing the Lock Point.
From now on it has no option but to keep releasing all the acquired
locks.
• Initially, a transaction is in the growing phase. The transaction
acquires locks as needed. Once the transaction releases a lock, it
enters the shrinking phase, and it can issue no more lock requests.
Thus two phase locking protocol ensures conflict serializability. If lock
conversion is allowed, then upgrading of locks must be done during
the growing phase, and downgrading of locks must be done in the
shrinking phase.
Timestamp Ordering Concurrency Control
Techniques
• Timestamp is a unique identifier created by the DBMS that indicates
the relative starting time of a transaction.
• The timestamp ordering protocol ensures that any conflicting read
and write operations are executed in timestamp order. The order of
transaction is nothing but the ascending order of the transaction
creation. The priority of the older transaction is higher that’s why it
executes first. Concurrency control techniques based on timestamp
ordering do not use locks, hence, deadlocks cannot occur.
 A)Basic Timestamp Ordering:
• Whenever some transaction T tries to issue a read(X) operation, the basic TO
algorithm compares the timestamp of T with R_TS(X) and W_TS(X) to ensure that
the timestamp order of transaction execution is not violated. If this order is
violated, then transaction T is aborted and resubmitted to the system as a new
transaction with a new timestamp.
1) Check the following condition whenever a transaction 𝑇𝑖 issues a read(X)
operation:
 If W_TS(X) > TS(𝑇𝑖 ) then the operation is rejected.

2)Check the following condition whenever a transaction 𝑇𝑖 issues a

write(X)operation:
• If TS(𝑇𝑖 )< R_TS(X) then the operation is rejected.
• If TS(𝑇𝑖 )< W_TS(X) then the operation is rejected and 𝑇𝑖 is rolled back otherwise
the operation is executed.
B) Strict Timestamp Ordering: A variation of basic TO called strict To ensure that
the schedules are both strict(easy to recoverability) and serializable.

1) Transaction T issues a write(X) operation:

• If TS(T)> R_TS(X), then delay T until the transaction T that wrote or
read X has terminated.

2)Transction T issues a read(X) operation:

• If TS(T)> W_TS(X), then delay T until the transaction T that wrote or
read X has terminated.
Deadlock: Deadlock refers to a specific situation where two or more processes
are waiting for each other to release a resource or more than two processes
are waiting for the resource in a circular chain.
Starvation: It is the situation when a transaction needs to wait for an
indefinite period to acquire a lock.