COMPS321F

Advanced Database and Data Warehousing

Lecture 5
TRANS ACTION MANAGEMENT PART I

Wyman Wang
School of Science and Technology
Content
Importance of Transactions
Properties of Transactions
Concurrency Control
Serializability of Schedule
Recoverable Schedule

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.

Application program is a series of transactions with non-database
processing in between.
Transforms database from one consistent state to another, although
consistency may be violated during transaction.

3
Transaction Support
Can have one of two outcomes:
◦ Success
• Transaction commits and database reaches a new consistent state.
• Committing the transaction causes the database modifications to be permanently written to the database.
• Committed transaction cannot be aborted or rolled back.
◦ Failure
• Transaction aborts, and database must be restored to consistent state before it started.
• Aborting the transaction causes all modifications made to the database during the course of the
transaction discarded.
• Such a transaction is rolled back or undone.
• Aborted transaction that is rolled back can be restarted (re-do) later.

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

5
Need for Concurrency Control
Three examples of potential problems caused by concurrency:
◦ Lost update problem.
◦ Uncommitted dependency problem.
◦ Inconsistent analysis problem.

6
Lost Update Problem
Successfully completed update is overridden by another user.
For example
◦ An account with balx (stored in database), initially £100 (i.e., balx = £100).
◦ T1 withdrawing £10 (i.e., balx = £100 - £10 = £90)
◦ T2 depositing £100 into same account. (i.e., balx = £90 + £100 = £190)
◦ Serially, final balance would be £190.

7
Lost Update Problem
Expected balx (stored in database) = £100 - £10 + £100 = £190
Actual balx (stored in database) = £90 (which is wrong!)

8
Lost Update Problem (Solution)
Loss of T2’s update avoided by preventing T1 from reading balx until
after update.
More details will be discussed in the latter part.

9
Uncommitted Dependency
Problem
Occurs when one transaction can see intermediate results of another
transaction before it has committed.
For example
◦ An account with balx, initially £100 (i.e., balx = £100).
◦ T4 depositing £100 (updates balx to £200) but it aborts
• so balx should be back at original value of £100 (i.e., balx = £100).
◦ T3 withdrawing £10 but has read new value of balx (£200) before T4 aborts.
• T3 uses value as basis of £10 reduction, giving a new balance of £190 (i.e., balx = £200 - £10 = £190)
• The correct version should be £90 (i.e., balx = £100 - £10 = £90)
◦ Serially, final balance would be £90.

10
Uncommitted Dependency
Problem
Expected balx (stored in database) = £100 - £10 = £90
Actual balx (stored in database) = £190 (which is wrong!)

11
Uncommitted Dependency
Problem (Solution)
Problem avoided by preventing T3 from reading balx until after T4
commits or aborts.
More details will be discussed in the latter part.

12
Inconsistent Analysis Problem
Occurs when transaction reads several values but second transaction
updates some of them during execution of first transaction.
Sometimes referred to as dirty read or unrepeatable read.
For example
◦ T6 is totaling balances of account x (£100), account y (£50), and account z (£25).
• The totaling balance is initially £175 (£100 + £50 + £25)
◦ Meantime, T5 has transferred £10 from balx to balz
◦ Serially, final balance would be:
• balx (£90), baly (£50), and balz (£35)
• The totaling balance would also be £175 (£90 + £50 + £35)

13
Inconsistent Analysis Problem
Expected totaling balance = £175 (£90 + £50 + £35)
Actual totaling balance = £185 (which is wrong!)

14
Inconsistent Analysis Problem
Problem avoided by preventing T6 from reading balx and balz until
after T5 completed updates.

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

Non-serial Schedule
◦ Schedule where operations from set of concurrent transactions are interleaved.
◦ If the non-serial schedule is equivalent to serial schedule, it is conflict serializable.
Otherwise, the non-serial schedule is not conflict serializable.

16
Schedule
A transaction (execution from left to right)
consists of Read (R) or Write (W) operations on a
variable (i.e. named as A and B)
◦ E.g. T1 : R(A), W(A)
◦ E.g. T2 : W(B), R(A)

Schedule
◦ A sequence of operations from a set of transactions
{T1, T2, …, Tn}
◦ For the set of transactions {T1, T2}, several schedules
are possible:

17
 Summary of Schedule
In summary, the follows shows the tree structure of different
schedules:

Serial (no errors)

Schedule Conflict serializable (no errors)
Non-serial
Not conflict serializable (may have errors)

18
Non-conflicting Operations
(a) If two operations only read data items, they do not conflict.
(b) If two operations either read or write different data items, they
do not conflict.

19
Non-conflicting Operations
Schedules with non-conflict operations
◦ No error (execution from left to right)
◦ E.g.

Ti: R(X),
Tj: R(X)

Ti: W(X), Ti: R(X), Ti: W (X),

Tj: R(Y) Tj: W(Y) Tj: W(Y)

20
Conflicting Operations
Schedules with conflicting operations may have errors
Two operations are conflicting if
◦ They are operations from different transactions on the same data item
◦ At least one of them is a Write operation
◦ E.g.

Ti: W(X), Ti: R(X), Ti: W (X),

Tj: R(X) Tj: W(X) Tj: W(X)

21
Precedence Graph
Create a Precedence Graph:
◦ Create a node for each transaction
◦ Search for any conflicting operations as shown in previous page and add an
edge for each conflicting pair.

If the precedence graph contains a cycle, it is not conflict serializable.

22
Precedence Graph – Example 1
Consider the schedule S1:

23
Precedence Graph – Example 2
Consider the schedule (execution sequence from left
to right) as:
The precedence graph is:
read(T1, X), write(T2, X), write(T2, X), write(T2, Y),
read(T1, Y), read(T2, Y), read(T1, Y)

Since the graph contains a Cycle, so the

schedule is not conflict serializable

Consider every combination of Read-Write, Write-Read

and Write-Write pairs.
24
Recoverability
Serializability identifies schedules that maintain database
consistency, assuming no transaction fails.
If transaction fails, atomicity requires effects of transaction to be
rolled back (undone).
Durability states that once transaction commits, its changes cannot
be rolled back.

25
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.
◦ For example (execution from left to right)

Wi(x), Rj(x), Ci, Cj

Once a transaction T is committed, it should never be necessary to

rollback.

26
Example 1 – Recoverable
Schedule
This schedule is recoverable:
Since Wi(x), Rj(x), Ci, Cj
Now, W2(x), R1(x), C2, C1

27
NOT Recoverable Schedule
Sometimes a transaction may not execute completely due to a
software issue, system crash or hardware failure. In that case, the
failed transaction has to be rolled back.
But some other transactions may also have used value produced by
the failed transaction. So we also have to rollback those transactions.
However, once a transaction commits, its changes cannot be rolled
back.

28
Example 2 – NOT Recoverable
Schedule
This schedule is NOT recoverable:
Since Wi(x), Rj(x), Ci, Cj
Now, W2(x), R1(x), C1, C2

T1 should also be rolled back at time

t13 because it reads the value written
by T2, but T1 can't be rolled back
because it already committed. So this
schedule is NOT recoverable.
29
More Examples
Sa: r1(X); r2(X); w1(X); r1(Y); w2(X);c2; w1(Y);c1

: recoverable (since there is no Wi(x), Rj(x) pair, no rollback

operations)

Sb: r1(X); w1(X); r2(X); r1(Y); w2(X); c2 ; c1

: not recoverable (T1 should commit before T2, now T2 commits
before T1)

Sc: r1(X); w1(X); r1(Y); r2(X); w2(X); w1(Y);c1;c2

: recoverable (T1 should commit before T2, now satisfied)

30
Reference
Chapter 22 of Connolly, T and Begg, C, Database Systems: A practical
Approach to Design, Implementation, and Management (6th ed.),
Boston: Pearson Education.

31