Chapter 22

Transaction Management

Pearson Education © 2009 1

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

2
Pearson Education © 2009
Example Transaction

3
Pearson Education © 2009
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.

4
Pearson Education © 2009
State Transition Diagram for Transaction

5
Pearson Education © 2009
Properties of Transactions
Four basic (ACID) properties of 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.

6
Pearson Education © 2009
DBMS Transaction Subsystem

7
Pearson Education © 2009
Concurrency Control
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.

8
Pearson Education © 2009
Need for Concurrency Control
 Three examples of potential problems caused by
concurrency:
– Lost update problem.
– Uncommitted dependency problem.
– Inconsistent analysis problem.

9
Pearson Education © 2009
Lost Update Problem
 Successfully completed update is overridden by
another user.
 T1 withdrawing £10 from an account with balx,
initially £100.
 T2 depositing £100 into same account.
 Serially, final balance would be £190.

10
Pearson Education © 2009
Lost Update Problem

 Loss of T2’s update avoided by preventing T1

from reading bal until after update.
PearsonxEducation © 2009
11
Uncommitted Dependency Problem
 Occurs when one transaction can see
intermediate results of another transaction
before it has committed.
 T4 updates balx to £200 but it aborts, so balx
should be back at original value of £100.
 T3 has read new value of balx (£200) and uses
value as basis of £10 reduction, giving a new
balance of £190, instead of £90.

12
Pearson Education © 2009
Uncommitted Dependency Problem

 Problem avoided by preventing T3 from

reading balx until after T4 commits or aborts. 13
Pearson Education © 2009
Inconsistent Analysis Problem
 Occurs when transaction reads several values
but second transaction updates some of them
during execution of first.
 Sometimes referred to as dirty read or
unrepeatable read.
 T6 is totaling balances of accounts:
x (£100), y (£50), and z (£25).
 Meantime, T5 has transferred £10 from balx to
balz, so T6 now has wrong result (£10 too high).

14
Pearson Education © 2009
Inconsistent Analysis Problem

 Problem avoided by preventing T6 from reading

balx and balz until after T5 completed updates. 15
Pearson Education © 2009
Serializability
 Objective of a concurrency control protocol is to
schedule transactions in such a way as to avoid
any interference.
 Could run transactions serially, but this limits
degree of concurrency or parallelism in system.
 Serializability identifies those executions of
transactions guaranteed to ensure consistency.

16
Pearson Education © 2009
Serializability
Schedule
Sequence of reads/writes by set of concurrent
transactions.
Serial Schedule
Schedule where operations of each transaction
are executed consecutively without any
interleaved operations from other
transactions.
 No guarantee that results of all serial executions
of a given set of transactions will be identical.
17
Pearson Education © 2009
Nonserial Schedule
 Schedule where operations from set of
concurrent transactions are interleaved.
 Objective of serializability is to find nonserial
schedules that allow transactions to execute
concurrently without interfering with one
another.
 In other words, want to find nonserial schedules
that are equivalent to some serial schedule. Such
a schedule is called serializable.

18
Pearson Education © 2009
Serializability
 In serializability, ordering of read/writes is
important:
(a) If two transactions only read a data item, they
do not conflict and order is not important.
(b) If two transactions either read or write
completely separate data items, they do not
conflict and order is not important.
(c) If one transaction writes a data item and
another reads or writes same data item, order
of execution is important.

19
Pearson Education © 2009
Example of Conflict Serializability

20
Pearson Education © 2009
Example of Conflict Serializability

21
Serializability
 Conflict serializable schedule orders any
conflicting operations in same way as some serial
execution.
 Under constrained write rule where:
– A transaction updates data item based on its
old value, which is first read.
 Use precedence graph to test for serializability.

22
Pearson Education © 2009
Precedence Graph
 Create:
– node for each transaction;
– a directed edge Ti  Tj, if Tj reads the value of
an item written by Ti;
– a directed edge Ti  Tj, if Tj writes a value into
an item after it has been read by Ti.
– a directed edge Ti → Tj, if Tj writes a value
into an item after it has been written by Ti.
 If precedence graph contains a cycle, schedule is
not conflict serializable.
23
Pearson Education © 2009
Example - Non-conflict serializable schedule
 T9 is transferring £100 from one account with
balance balx to another account with balance
baly.

 T10 is increasing balance of these two accounts by

10%.

 Precedence graph has a cycle and so is not

serializable.

24
Pearson Education © 2009
Example - Non-conflict serializable schedule

25
Pearson Education © 2009
Recoverability
 Serializabilityidentifies schedules that maintain
database consistency, assuming no transaction
fails.
 Could also examine recoverability of
transactions within schedule.
 If transaction fails, atomicity requires effects of
transaction to be undone.
 Durability states that once transaction commits,
its changes cannot be undone (without running
another, compensating, transaction).

26
Pearson Education © 2009
Recoverable Schedule
A schedule where, for each pair of transactions
Ti and Tj, if Tj reads a data item previously
written by Ti, then the commit operation of Ti
precedes the commit operation of Tj.

27
Pearson Education © 2009
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.

28
Pearson Education © 2009
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.
29
Pearson Education © 2009
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.

30
Pearson Education © 2009
Locking - Basic Rules
 Some systems allow transaction to upgrade read
lock to an exclusive lock, or downgrade exclusive
lock to a shared lock.

31
Pearson Education © 2009
Example - Incorrect Locking Schedule
 For these two transactions, a valid
schedule using these rules is: S = {
T09- write_lock(balx), read(balx),
write(balx), unlock(balx).
T10- write_lock(balx), read(balx),
write(balx), unlock(balx).
T10- write_lock(baly), read(baly),
write( baly), unlock(baly),
commit(T10)
T09- write_lock(baly), read(baly),
write(baly), unlock(baly),
commit(T9)}
Pearson Education © 2009
32
Example - Incorrect Locking Schedule
 If at start, balx = 100, baly = 400, result should be:

– balx = 220, baly = 330, if T9 executes before T10,

or
– balx = 210, baly = 340, if T10 executes before T9.

 However, result gives balx = 220 and baly = 340.

S is not a serializable schedule.

33
Pearson Education © 2009
Example - Incorrect Locking Schedule
 Problem is that transactions release locks too
soon, resulting in loss of total isolation and
atomicity.
 To guarantee serializability, need an additional
protocol concerning the positioning of lock and
unlock operations in every transaction.

34
Pearson Education © 2009
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.

35
Pearson Education © 2009
Preventing Lost Update Problem using 2PL

36
Pearson Education © 2009
Preventing Uncommitted Dependency Problem
using 2PL

37
Pearson Education © 2009
Preventing Inconsistent Analysis Problem using
2PL

38
Pearson Education © 2009
Cascading Rollback
 If every transaction in a schedule follows 2PL,
schedule is serializable.
 However, problems can occur with
interpretation of when locks can be released.

39
Pearson Education © 2009
Cascading Rollback

40
Pearson Education © 2009
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.

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

42
Pearson Education © 2009
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).
 Three general techniques for handling deadlock:
– Timeouts.
– Deadlock prevention.
– Deadlock detection and recovery.

43
Pearson Education © 2009