Chapter 22

Transaction Management

Pearson Education © 2014

Chapter 22 - Objectives
• Function and importance of transactions.
• Properties of transactions.
• Concurrency Control
• Meaning of serializability.
• How locking can ensure serializability.
• Deadlock and how it can be resolved.
• How timestamping can ensure serializability.
• Optimistic concurrency control.
• Granularity of locking.
• Recovery Control
• Some causes of database failure.
• Purpose of transaction log file.
• Purpose of checkpointing.
• How to recover following database failure.
• Alternative models for long duration transactions.

Pearson Education © 2014 2

Transaction Support
•Transaction
Action, or series of actions, carried out by user or
application, which reads or updates contents of database.
•Logical unit of work on the database.
• An entire program, a part of a program, or a single statement (for
example, the SQL- statement INSERT or UPDATE), and it may involve
any number of operations
•Application program is series of transactions with non-
database processing in between.
•Transforms database from one consistent state to another,
although consistency may be violated during transaction.

Pearson Education © 2014 3

 Example Transaction
• Staff (staffNo, fName, IName, position, sex, DOB, salary, branchNo)
• PropertyForRent (propertvNo, street, city, postcode, type, rooms, rent, ownerNo,
staffNo, branchNo)

Pearson Education © 2014 4

Transaction Support
• Can have one of two outcomes:
• Success - transaction commits and database reaches a new consistent
state.

• Failure - transaction aborts, and database must be restored to consistent

state before it started.
• Such a transaction is rolled back or undone.

• Committed transaction cannot be aborted.

• Aborted transaction that is rolled back can be restarted later.

Pearson Education © 2014 5

State Transition Diagram for Transaction

Pearson Education © 2014 6

Properties of Transactions
Four basic (ACID) properties that define a transaction
are:
Atomicity ‘All or nothing’ property.
Consistency Must transform database from one
consistent state to another.
Isolation Partial effects of incomplete transactions
should not be visible to other transactions.
Durability Effects of a committed transaction are
permanent and must not be lost because of later
failure.

Pearson Education © 2014 7

DBMS Transaction Subsystem

Pearson Education © 2014 8

Concurrency Control
▪ Concurrency Control is the process of managing simultaneous
operations on the database without having them interfere
with one another.
•Prevents interference when two or more users are accessing
database simultaneously and at least one is updating data.

•Although two transactions may be correct in themselves,

interleaving of operations may produce an incorrect result.

Three potential problems caused by concurrency:

1. Lost update problem.
2. Uncommitted dependency problem.
3. Inconsistent analysis problem.

Pearson Education © 2014 9

Need for Concurrency Control- Lost update problem

10
Need for Concurrency Control-
Uncommitted dependency problem

11
Need for Concurrency Control
Inconsistent analysis problem

12
Concurrency Control Techniques
• Two basic concurrency control techniques:
• Locking,
• Timestamping.
• Both are conservative approaches: delay transactions in case they
conflict with other transactions.
• Optimistic methods assume conflict is rare and only check for
conflicts at commit.

Pearson Education © 2014 13

Locking
Transaction uses locks to deny access to other transactions and so prevent
incorrect updates.
• Most widely used approach to ensure serializability.
• Generally, a transaction must claim a shared (read) or exclusive (write) lock on
a data item before read or write.
• Lock prevents another transaction from modifying item or even reading it, in
the case of a write lock.

Locking - Basic Rules

• If transaction has shared lock on item, can read but not update item.
• If transaction has exclusive lock on item, can both read and update item.
• Reads cannot conflict, so more than one transaction can hold shared locks
simultaneously on same item.
• Exclusive lock gives transaction exclusive access to that item.
• Some systems allow transaction to upgrade read lock to an exclusive lock,
or downgrade exclusive lock to a shared lock.
Pearson Education © 2014 14
 Two-Phase Locking (2PL)
Transaction follows 2PL protocol if all locking operations precede
first unlock operation in the transaction.
• Two phases for transaction:
• Growing phase - acquires all locks but cannot release any locks.
• Shrinking phase - releases locks but cannot acquire any new locks.
• A transaction must acquire a lock on an item before operating on the item. The
lock may be read or write, depending on the type of access needed.
• Once the transaction releases a lock, it can never acquire any new locks.

Pearson Education © 2014 15

Cascading Rollback
• If every transaction in a schedule follows 2PL, schedule is serializable.
• Serializable: A schedule where the operations of each transaction are
executed consecutively without any interleaved operations from other
transactions.
• However, problems can occur with interpretation of when locks can
be released.

Pearson Education © 2014 16

Cascading Rollback
• Transactions conform to 2PL.
• T14 aborts.
• Since T15 is dependent on T14, T15 must also be rolled back. Since T16 is
dependent on T15, it too must be rolled back.
• This is called cascading rollback.
• To prevent this with 2PL, leave release of all locks until end of
transaction (COMMIT).

Pearson Education © 2014 17

Deadlock
An impasse that may result when two (or more) transactions are each
waiting for locks held by the other to be released.

Pearson Education © 2014 18

Deadlock
• Only one way to break deadlock: abort one or more of the
transactions.
• Deadlock should be transparent to user, so DBMS should
restart transaction(s).
• However, in practice DBMS cannot restart aborted
transaction since it is unaware of transaction logic even if it
was aware of the transaction history unless there is no user
input in the transaction or the input is not a function of the
database state.

Pearson Education © 2014 19

Deadlock
• Three general techniques for handling deadlock:
• Timeouts.
• Deadlock prevention.
• Deadlock detection and recovery.

Timeouts
• Transaction that requests lock will only wait for a system-defined period of
time.
• If lock has not been granted within this period, lock request times out.
• In this case, DBMS assumes transaction may be deadlocked, even though it may
not be, and it aborts and automatically restarts the transaction.

Deadlock Prevention
DBMS looks ahead to see if transaction would cause deadlock and never allows
deadlock to occur.
Ordering transactions using transaction timestamps, two protocols are
available for ordering.

Pearson Education © 2014 20

 Deadlock Prevention
• Wait-Die - only an older transaction can wait for younger one, otherwise transaction is
aborted (dies) and restarted with same timestamp.
• Timestamp(Tn) < Timestamp(Tk) − that is Tn, which is requesting a conflicting lock, is older than
Tk − then Tn is allowed to "wait" until the data-item is available.
• Timestamp(Tn) > Timestamp(Tk) − that is Tn is younger than Tk − then Tn is killed ("dies"). Tn is
restarted later with a random delay but with the same timestamp(n).

• Suppose that transaction T5, T10, T15 have time-stamps 5, 10 and 15 respectively.
• If T5 requests a data item held by T10 then T5 will "wait".
• If T15 requests a data item held by T10, then T15 will be killed ("die").

• Wound-Wait - only a younger transaction can wait for an older one. If older transaction
requests lock held by younger one, younger one is aborted (wounded).
• Timestamp(Tn) < Timestamp(Tk) - then Tn forces Tk to be killed − that is Tn "wounds" Tk. Tk is
restarted later with a random delay but with the same timestamp(k).
• Timestamp(Tn) > Timestamp(Tk) - then Tn is forced to "wait" until the resource is available.

• Transactions T5, T10, T15 have time-stamps 5, 10 and 15 respectively.

• If T5 requests a data item held by T10, then data item will be preempted from T10 and T10 will be suspended.
• If T15 requests a data item held by T10, then T15 will "wait".
21
Deadlock Detection and Recovery
• DBMS allows deadlock to occur but recognizes it and breaks it.
• Usually handled by construction of wait-for graph (WFG) showing
transaction dependencies:
• Create a node for each transaction.
• Create edge Ti -> Tj, if Ti waiting to lock item locked by Tj.
• Deadlock exists if and only if WFG contains cycle.
• WFG is created at regular intervals.

Recovery from Deadlock Detection

• Several issues:
• Choice of deadlock victim;
• Which Transaction should be terminated to recover from deadlock
• How far to roll a transaction back;
• It may be possible to resolve the deadlock by rolling back only part of the transaction.
• Avoiding starvation
• Avoid selecting same Transaction as victim repeatedly

Pearson Education © 2014 22

Timestamping
• Transactions ordered globally so that older transactions, transactions
with smaller timestamps, get priority in the event of conflict.
• Conflict is resolved by rolling back and restarting transaction.
• No locks so no deadlock.

Pearson Education © 2014 23

Timestamping
Timestamp
A unique identifier created by DBMS that indicates
relative starting time of a transaction.
• Can be generated by using system clock at time transaction started,
or by incrementing a logical counter every time a new transaction
starts.
• Read/write proceeds only if last update on that data item was carried
out by an older transaction.
• Otherwise, transaction requesting read/write is restarted and given a
new timestamp.
• Also timestamps for data items:
• read-timestamp - timestamp of last transaction to read item;
• write-timestamp - timestamp of last transaction to write item.

Pearson Education © 2014 24

Timestamping - Read(x)
• Consider a transaction <T> with timestamp ts(T) and a resource (x):

ts(T) < write_timestamp(x)

• <T> is trying to read (x) and (x) is already updated/write by younger (later)
transaction.
• Transaction <T> must be aborted and restarted with a new timestamp.
ts(T) < read_timestamp(x)
• (x) already read by younger transaction and <T> is trying to update (write) on
(x).
• A later transaction is already using the current value of the item and it would be an error to
update it now
• Roll back transaction and restart it using a later timestamp.

Pearson Education © 2014 25

Timestamping - Write(x)
ts(T) < write_timestamp(x)
• (x) already written by younger transaction.
• Write can safely be ignored - ignore obsolete write rule.

• Otherwise, operation is accepted and executed.

Pearson Education © 2014 26