CSI2004 - Advanced Database

Management Systems
Transaction Processing
 Transaction Concept

 A transaction is a unit of program execution that

accesses and possibly updates various data items.
 Collection of operations that form a single logical
unit of work
 A transaction must see a consistent database.
 During transaction execution the database may be
inconsistent.
 When the transaction is committed, the database
must be consistent.
 Transaction Concept

 A transaction is initiated by a user program written

in a high-level data manipulation language or
programming language,where it is delimited by
statements of the form begin transaction and end
transaction.
 The transaction consists of all operations executed
between the begin transaction and end transaction.
 Two main issues to deal with:
 Failures of various kinds, such as hardware
failures and system crashes
 Concurrent execution of multiple transactions
 Transaction Concept

 Transaction manager
 Transaction processing monitor
 TP monitor
Commit
Rollback
 Transaction Concept
BEGIN TRANSACTION;
UPDATE ACC 123 { BAL:=BAL-$100 };
IF any arror occurred THEN
GO TO UNDO;
END IF;
UPDATE ACC 456 { BAL:=BAL+$100 };
IF any error occurred THEN
GO TO UNDO;
END IF;
COMMIT;
GO TO FINISH;
UNDO:
ROLLBACK;
FINISH:
RETURN;
ACID Properties
 ACID Properties
To preserve integrity of data, the database system must ensure:
 Atomicity. Either all operations of the transaction are
properly reflected in the database or none are.
 Consistency. Execution of a transaction in isolation
preserves the consistency of the database.
 Isolation. Although multiple transactions may execute
concurrently, each transaction must be unaware of other
concurrently executing transactions. Intermediate
transaction results must be hidden from other concurrently
executed transactions.
 That is, for every pair of transactions Ti and Tj, it
appears to Ti that either Tj, finished execution before
Ti started, or Tj started execution after Ti finished.
 Durability. After a transaction completes successfully,
the changes it has made to the database persist, even if
there are system failures.
 Example of Fund Transfer
 Transaction to transfer $50 from account A to account
B:
1. read(A)
2. A := A – 50
3. write(A)
4. read(B)
5. B := B + 50
6. write(B)
 Atomicity requirement — if the transaction fails after
step 3 and before step 6, the system should ensure that its
updates are not reflected in the database, else an
inconsistency will result.
 Consistency requirement – the sum of A and B is
unchanged by the execution of the transaction.
 Example of Fund Transfer
 Isolation requirement — if between steps 3 and 6,
another transaction is allowed to access the partially
updated database, it will see an inconsistent database
(the sum A + B will be less than it should be).
Can be ensured trivially by running transactions serially,
that is one after the other. However, executing multiple
transactions concurrently has significant benefits.
 Durability requirement — once the user has been
notified that the transaction has completed (i.e., the
transfer of the $50 has taken place), the updates to the
database by the transaction must persist despite failures.
Transaction States
Transaction States
 Transaction States
 Active, the initial state; the transaction stays in this state
while it is executing
 Partially committed, after the final statement has been
executed.
 Failed, after the discovery that normal execution can no
longer proceed.
 Aborted, after the transaction has been rolled back and
the database restored to its state prior to the start of the
transaction. Two options after it has been aborted:
 restart the transaction – only if no internal
logical error
 kill the transaction
 Committed, after successful completion.
Transaction Processing - Problems
 Transaction Processing Systems
 Transaction processing systems are systems with
large databases and hundreds of concurrent users
executing database transactions.

 Examples of such systems include airline

reservations, banking, credit card processing,
online retail purchasing, stock markets,
supermarket checkouts, and many other
applications.
 Advantages of Concurrent Execution

 Waiting time of transactions is reduced

 Response time increases
 Resources are used effectively
 Concurrency control

 Many transaction access the same database at the same

time
 Some more problems
1. Lost update problem
2. Temporary update or dirty read or uncommitted
dependency problem
3. The inconsistent analysis or incorrect Summary
problem
 Lost Update Problem

 This problem occurs when two transactions that

access the same database items have their
operations interleaved in a way that makes the
value of some database items incorrect.

 T2 reads the value of A before T1 changes it in

the database, and hence the updated value
resulting from T1 is lost
 The lost update problem

TRANSACTION A TIME TRANSACTION B

-- --
RETRIEVE t t1 --
--- t2 RETRIEVE t
UPDATE t t3 ---
--- t4 UPDATE t

 A losses its update

19
 The Temporary Update (or Dirty Read) Problem

Uncommitted dependency (dirty read) problem

 This problem occurs when one transaction
updates a database item and then the
transaction fails for some reason.

 Meanwhile, the updated item is accessed

(read) by another transaction before it is
changed back to its original value.
 Uncommitted dependency or Temporary
Update Dirty Read problem

TRANSACTION A TIME TRANSACTION B

--- --
---- t1 UPDATE t
RETRIEVE t t2 ----
----- t3 ROLLBACK
--- t4 ------

 A retrieves incorrect data

 Inconsistent Analysis or Incorrect
Summary problem

TRANSACTION A TIME TRANSACTION B

--- --
---- t1 UPDATE t
UPDATE t t2 ----
----- t3 ROLLBACK
--- t4 ------

 A losses its update

Inconsistent Analysis or Incorrect Summary
Problem

If one transaction is calculating an aggregate

summary function on a number of database
items while other transactions are updating
some of these items, the aggregate function
may calculate some values before they are
updated and others after they are updated.
 Inconsistent Analysis or Incorrect Summary
problem
acc1=40 acc2=50 acc3=30

TRANSACTION A TIME TRANSACTION B

RETRIEVE acc1 : sum=40 t1 --------
RETRIEVE acc2 : sum=90 t2 ----
----- t3 RETRIEVE acc3
--- t4 UPDATE acc3: 3020
------------- t5 RETRIEVE acc1
---------------- t6 UPDATE acc1 : 4050
--------------------- t7 commit
RETRIEVE acc3 : sum=110 t8
 Concurrency control

Four possibilities
 RR  noproblem
 RW  nonrepeatable read
 inconsistent analysis problem
 WR dirty read
 uncommitted dependency problem
 WW dirty write
The lost update problem
Schedules
 Schedules
 Schedule – a sequence of instructions that specify the
chronological order in which instructions of concurrent
transactions are executed
 A schedule for a set of transactions must consist of
all instructions of those transactions
 Must preserve the order in which the instructions
appear in each individual transaction.
 A transaction that successfully completes its execution
will have a commit instructions as the last statement
 by default transaction assumed to execute commit
instruction as its last step
 A transaction that fails to successfully complete its
execution will have an abort instruction as the last
statement
 Schedule 1
 T1 transfer $50 from A to B
 T2 transfer 10% of the balance from A to B.
 A serial schedule in which T1 is followed by T2 :

Let A=$1000
B=$2000

Before transaction
A+B=$3000

A=$855
B=$2145

After transaction
A+B=$3000
 Schedule 2

• A serial schedule where T2 is followed by T1

Let A=$1000 A=$850

B=$2000 B=$2150

Before transaction
A+B=$3000
After transaction
A+B=$3000
 Schedule 3
 Let T1 and T2 be the transactions defined previously. The
following schedule is not a serial schedule, but it is
equivalent to Schedule 1.

A=$855
B=$2145
Before transaction
A+B=$3000
After transaction
A+B=$3000

In Schedules 1, 2 and 3, the sum A + B is preserved.

 Schedule 4

 The following concurrent schedule does not preserve

the value of (A + B ).

A=$950
B=$2100
Before transaction
A+B=$3000
After transaction
A+B=$3050
Schedules based on Serializability
 Serializable Schedule
 Schedule:
 Set of instructions
 Serial schedule Executing the transactions one
at a time with no interleaving
 Interleaved schedule Non serial schedule
 Equivalent schedule Two schedules are
equivalent if and only if, no matter what the initial
state of the database, they are guaranteed to
produce the same result as each other
 Serializable:
 A given execution of a given set of transactions is
serializable, if and only if it is equivalent to
some serial execution of the same transaction
 Serializable Schedule

 Basic Assumption – Each transaction preserves

database consistency.
 Thus serial execution of a set of transactions
preserves database consistency.
 A (possibly concurrent) schedule is serializable if
it is equivalent to a serial schedule.
1. Conflict serializability
2. View serializability
 Serializable Schedule

 We ignore operations other than read and write

instructions
 We assume that transactions may perform
arbitrary computations on data in local buffers
in between reads and writes.
 Our simplified schedules consist of only read
and write instructions.
 Serializable Schedule

If li and lj refer different data items, then we can

swap li and lj without affecting the results of any

instruction in the schedule.

 If li and lj refer same data item (Q), then the order

of two steps may matter

 Conflicting Instructions
Instructions li and lj of transactions Ti and Tj respectively,
conflict if and only if there exists some item Q accessed
by both li and lj, and at least one of these instructions
wrote Q:
Ti Tj

Instruction li Instruction lj Result

read(Q) read(Q) No conflict
read(Q) write(Q) Conflict
write(Q) read(Q) Conflict
write(Q) write(Q) Conflict
 Conflict Serializability

 If a schedule S can be transformed into a

schedule S´ by a series of swaps of non-
conflicting instructions, we say that S and
S´ are conflict equivalent.

 We say that a schedule S is conflict

serializable if it is conflict equivalent to a
serial schedule
 Testing for Serializability

 Consider some schedule of a set of transactions

T1, T2, ..., Tn
 Precedence graph — a directed graph where
 the vertices are the transactions (names).
 we draw an arc from Ti to Tj if the two
transactions conflict
 Testing for Serializability

 The set of edges consists of all edges Ti  Tj for which

one of three conditions holds
 Ti Executes write(Q) before Tj executes read(Q)
 Ti Executes read(Q) before Tj executes write(Q)
 Ti Executes write(Q) before Tj executes writeQ)
 If an edge Ti  Tj exists in the precedence graph, then in
any serial schedule S’ equivalent to S, Ti must appear
before Tj
 Testing for Serializability
 Ex:

T1 T2

 All instructions of T1 are executed before the first

instruction of T2 is executed

T2 T1

 All instructions of T2 are executed before the first

instruction of T1 is executed
 Test for Conflict Serializability

 A schedule is conflict serializable if and only if

its precedence graph is acyclic.
Schedule 3
 Conflict Serializability
 Schedule 3 can be transformed into Schedule 6, a serial
schedule where T2 follows T1, by series of swaps of non-
conflicting instructions. Therefore Schedule 3 is conflict
serializable.

Schedule 3 Schedule 6
 Conflict Serializability
 Example of a schedule that is not conflict serializable:

 We are unable to swap instructions in the above

schedule to obtain either the serial schedule < T3, T4 >,
or the serial schedule < T4, T3 >.
 Serializability
 Example (Schedule 4)

T1T2 : T1 executes read(A)

before t2 executes write(A)

T2T1 : T2 executes read(B)

before T1 executes write(B)
 Serializability order

 If precedence graph is acyclic, the

serializability order can be obtained by
a topological sorting of the graph.
 This is a linear order consistent with
the partial order of the graph.
For example, a serializability order
1) TiTjTkTm
2) TiTkTjTm
Example Problems
 EXAMPLE
Check whether the given schedule S is conflict
serializable or not?

S : R1(A) , R2(A) , R1(B) , R2(B) , R3(B) ,

W1(A) , W2(B)
 EXAMPLE

S : R1(A) , R2(A) , R1(B) , R2(B) , R3(B) ,

W1(A) , W2(B)

T1 T2 T3
R1(A)
R2(A)
R1(B)
R2(B)
R3(B)
W1(A)
W2(B)
 EXAMPLE

Steps:

1. List all the conflicting operations

2. Determine the dependency between the
transactions
3. Draw the precedence graph
 EXAMPLE

Check whether the given schedule S is conflict serializable

or not?
S : R1(A) , R2(A) , R1(B) , R2(B) , R3(B) , W1(A) , W2(B)
Solution
1. List all the conflicting operations
R2(A) , W1(A)
R1(B) , W2(B)
R3(B) , W2(B)
2. Determine the dependency between the transactions
R2(A) , W1(A) (T2 → T1)
R1(B) , W2(B) (T1 → T2)
R3(B) , W2(B) (T3 → T2)
 EXAMPLE
Check whether the given schedule S is conflict serializable
or not?
S : R1(A) , R2(A) , R1(B) , R2(B) , R3(B) , W1(A) , W2(B)
Solution
1. List all the conflicting operations
R2(A) , W1(A)
R1(B) , W2(B)
R3(B) , W2(B)
2. Determine the dependency between the transactions
R2(A) , W1(A) (T2 → T1)
R1(B) , W2(B) (T1 → T2)
R3(B) , W2(B) (T3 → T2)
3. Draw the precedence graph
 EXAMPLE
Check whether the given schedule S is conflict serializable
or not?
S : R1(A) , R2(A) , R1(B) , R2(B) , R3(B) , W1(A) , W2(B)
Solution
1. List all the conflicting operations
R2(A) , W1(A)
R1(B) , W2(B)
R3(B) , W2(B)
2. Determine the dependency between the transactions-
R2(A) , W1(A) (T2 → T1)
R1(B) , W2(B) (T1 → T2)
R3(B) , W2(B) (T3 → T2)
3. Draw the precedence graph-
There exists a cycle in the precedence graph. So, the given schedule S is not conflict
serializable
 EXAMPLE
Check whether the given schedule S is conflict serializable
or not?
 EXAMPLE
Check whether the given schedule S is conflict serializable or no
Solution
1. List all the conflicting operations

R2(X) , W3(X)
R2(X) , W1(X)
W3(X) , W1(X)
W3(X) , R4(X)
W1(X) , R4(X)
W2(Y) , R4(Y)
 EXAMPLE
Check whether the given schedule S is conflict serializable or no
Solution
1. List all the conflicting operations
R2(X) , W3(X)
R2(X) , W1(X)
W3(X) , W1(X)
W3(X) , R4(X)
W1(X) , R4(X)
W2(Y) , R4(Y)
2. Determine the dependency between the transactions-
R2(X) , W3(X) (T2 → T3)
R2(X) , W1(X) (T2 → T1)
W3(X) , W1(X) (T3 → T1)
W3(X) , R4(X) (T3 → T4)
W1(X) , R4(X) (T1 → T4)
W2(Y) , R4(Y) (T2 → T4)
3. Draw the precedence graph
 EXAMPLE
Check whether the given schedule S is conflict serializable or no
Solution
1. List all the conflicting operations
R2(X) , W3(X)
R2(X) , W1(X)
W3(X) , W1(X)
W3(X) , R4(X)
W1(X) , R4(X)
W2(Y) , R4(Y)
2. Determine the dependency between the transactions-
R2(X) , W3(X) (T2 → T3)
R2(X) , W1(X) (T2 → T1)
W3(X) , W1(X) (T3 → T1)
W3(X) , R4(X) (T3 → T4)
W1(X) , R4(X) (T1 → T4)
W2(Y) , R4(Y) (T2 → T4) There exists no cycles in the precedence
3. Draw the precedence graph graph. So, the given schedule S is conflict
serializable