UNIT - 8

TRANSACTIONS
 Transaction Concept
 A transaction refers to a collection of
operations that form a single logical unit of
work
It is a unit of program execution that accesses
and possibly updates various data items.
E.g. transaction to transfer $50 from
account A to account B:
begin
A := A – 50
B := B + 50
end
 Transaction is initiated by user program
written in high level data manipulation
language (typically SQL)
 A transaction access data using reads and
writes of database objects
 Example of Fund Transfer:
Transfer $50 from account A to B (Initially
A=100, B=100)
1. read(A)
2. A := A – 50
3. write(A)
4. read(B)
5. B := B + 50
6. write(B)
 ACID Properties
To preserve the integrity of data, the
database system must ensure:
• Atomicity
A
Properti
es of • Consistency
C
Transact
ion • Isolation
I
( ACID)
• Durability
D
1) Atomicity Property:
 Either all operations of the transaction are properly done in the
database or none
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, money
will be “lost” leading to an inconsistent database state
 Failure could be due to software or hardware
 The system should ensure that updates of a partially executed
transaction are not reflected in the database
 Ensuring atomicity is the responsibility of the database system
itself; specifically, it is handled by a component called the
2) Consistency Property:
 Execution of a transaction in isolation (i.e. with no other transaction
executing concurrently) preserves the consistency of the database.
Example of Fund Transfer :
 Transaction to transfer $50 from account A ($100) to account B ($
100):

1. read(A) 50
2. A := A – 50 20
3. write(A)
4. read(B) 15 0
5. B := B + 50 0
6. write(B)

Consistency requirement
 The sum of A and B be unchanged by the execution of the
transaction
 If the database is consistent before an execution of the transaction,
the database remains consistent after the execution of the
transaction
3) Isolation Property:
 Although multiple transactions may execute concurrently,
each transaction must be unaware of other concurrently
executing transactions.
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.
 Intermediate transaction results must be hidden from other
concurrently executed transactions.
 Ensuring the isolation property is the responsibility of a
component of the database system called the
concurrency-control component.
it means can we convert parallel schedule to serial
schedule, we need to do this bcoz serial schedule is
consistent.
Isolation requirement

T1 T2
1. read(A)
2. A := A – 50
3. write(A)
read(A), read(B),
print(A+B)
4. read(B)
5. B := B + 50
6. write(B

• if between steps 3 and 6, another transaction T2 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).

•Isolation can be ensured trivially by running transactions

serially that is, one after the other.
4) Durability Property:
 After a transaction completes successfully, the
changes it has made to the database persist,
even if there are system failures.
 The durability property guarantees that 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 even if there are
software or hardware failures.
 Ensuring durability is the responsibility of a
component of the database system called the
recovery-management component.
 Transaction States
 All transaction must be completed successfully
 A transaction that completes its execution without any
failure known as “Committed”
 For successfully completion of a transaction, a
transaction must be in one of the following
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 has been restored to its state prior
to the start of the transaction
 Committed: after successful completion
State Diagram of a
Transaction
 Transaction
Termination

Committe
Aborted
d

Rolled
Back
Committed: After successful execution of a transaction, all changes
made within it are permanently saved
Aborted: If a transaction fails, all changes made within it are not
saved
Rolled Back: An operation which returns the database to its previous
state. Rollbacks are important for database integrity, because they
mean that the database can be restored to a clean copy even after
We
erroneous cannot
operations areabort or rollback a
performed
committed transaction
 Aborted State
(System has 2 options)

Restart Kill
Transacti Transacti
on on

RESTART is considered to be a new transaction without having

any internal logical error

KILL is commonly used to terminate a process that is blocking

other important processes. In database, kill is used for rewriting
the application program.
 Implementation of
Atomicity and Durability
The recovery-management component of a
database system can support atomicity and
durability by a variety of schemes.
We first consider a simple, but extremely inefficient
scheme called the shadow copy scheme.
This scheme is based on making copies of the
database, called shadow copies, assumes that
only one transaction is active at a time.
 The scheme also assumes that the database is
simply a file on
disk. A pointer called db-pointer is maintained on
disk; it points to the current copy of the database.
 In the shadow-copy scheme, a transaction that wants
to update the database first creates a complete copy
of the database.
 All updates are done on the new database copy,
leaving the original copy, the shadow copy,
untouched.
 If at any point, the transaction has to be aborted, the
system merely deletes the new copy. The old copy of
the database has not been affected.
 If all operations are successfully completed on shadow
copy of the database then delete the old copy
 The implementation actually depends on the write to
db-pointer
 The atomicity and durability properties of transactions
are ensured by the shadow-copy implementation of
the recovery-management component
Shadow copy technique for atomicity
and durability
 Concurrent
Executions
• Multiple transactions are allowed to run concurrently in
the system
Advantages:
1. increased processor and disk utilization,
leading to better transaction throughput E.g. one
transaction can be using the CPU while another is
reading from or writing to the disk
2. reduced average response time for
transactions: short transactions need not wait
behind long ones.

• When several transactions run concurrently, database

consistency can be destroyed despite the correctness of
each individual transaction
 Schedules
• Schedule – a sequences 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
• A transaction that fails to successfully
Serial complete its
Schedul
execution will have an abort instruction as the last
statement
e Concurre
nt
 Serial Schedule
• Let T1 transfer $50 from A to B, and T2 transfer
10% of the balance from A to B. A = $1000, B =
$2000 Schedules 1 Schedules 2

Serial
Schedules
 Serial Schedule
• Let T1 transfer $50 from A to B, and T2 transfer
10% of the balance from A to B. A = $1000, B =
$2000
A + B = $3000
Schedule T1
A: 1000-50 = 950
A = 950
B: 2000+50 = 2050
B = 2050 T2
A : 950
Temp: 950*0.1 =
95
A : 950 – 95 =
855
A= 855
Final B: 2050
Values B : 2050 + 95 =
2145
B = 2145
 Concurrent Schedule
Schedules 3 Schedules 4

It Preserves It does not preserve

Consistency Consistency
 Dirty Read Problem

T1 T2 T3
R(A) If A=70, and T1 fails, no
A=A-50 credibility of T2 operation and it
W(A) is called dirty read in T2
R(A)
A=A*2
W(A)
Commit
R(B)
W(B)

Fail
 Serializability
• The database system must control concurrent execution of
transactions, to ensure that the database state remains
consistent
• 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.

• Different forms of schedule equivalence give rise to the

notions of:
Two ways/method of knowing whether given parallel
schedule is serializable or not,
1. conflict serializability
2. view serializability

Let we have T1, T2, T3, so to make serializable we have 6

possibility, (factorial of 3)
T1->T2->T3
 T1 T2
Read (A)
Write (A)
Serializabi Read (B)
lity Write (B)
Read (A)
Write (A)
Read (B)
Write (B)
Concurrent
Schedule Serial Schedule
For checking whether
conflict equivalent of
schedule exist or not,
swap non conflict
pairs.

After swapping if it
gets converted into
serializable schedule
it means conflict
equivalent exists and
can be said that given
parallel schedule is
serializable
 Conflict Serializability
• 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 (same data item accessed by different
transaction at the same time), and at least one of these
instructions is a write operation.
• 4 Cases to ensure conflict serializability:
 Conflict Serializability
Conflict :
different
operations on
same data item
(Case 3)

No Conflict :
different
operations on
different data
item

Conflict equivalent leads to conflict

serializability
Convert Conflict Equivalence into Serializability

A conflict (concurrent) schedule can be

transformed into serial schedule by
number of swap operations:

[Link] Ii = Read (Q) ; Ij = Read (Q) : We

can swap it
[Link] Ii = Read (Q) ; Ij = Read (P) : We
can swap it
[Link] Ii = Read (Q) ; Ij = Write (P) : We
can swap it
[Link] Ii = Write (Q) ; Ij = Read (P) : We
can swap it
5. if Ii=Write(Q); Ij=Write(P): we
 T1 T2
Read
(A)
Write
(A) Read
Read (A)
(B) Write
(A)

Write Read
(B) (B)
Write
T1 T2 T1 (B)T2
Read Read
(A) (A)
Write Write
Serial (A) (A) Read
Schedule Read Read Read (A)
After (B) (A) (B)
swapping Write Write Write
(B) (A) Write (A)
Read (B) Read
Example for Non-Conflict
Schedule

Schedule

We are unable to swap instructions in the above

schedule to obtain either the serial schedule < T3,
T4> or the serial schedule < T4, T3> due to write
operation on same data item
 Precedence graph Method
Check given schedule is conflict serializable
or not,
T1 T2 T3
R(x) conflict pair:- T2
T1
R(y) R-W
R(x)
R(y) W-R
R(Z) W-W T3
W(y)
W(z) As no loop so it is conflict serializable schedule
R(Z) (there is a serializable schedule exist
W(x) equivalent to this) and it is consistent.
W(z)
Now for serializability there could be 6
possibility (factorial3). So to know this schedule
is equivalent to which of these 6 check graph
with indegree=0 (no node coming in (ex. Here
T2)).Then dissole T2 and both its edges. Then
remaining T3 and T2 pair, here indrgree of T3 is
 Example
T1 T2 T3

R(A)

W(A)

W(A)

W(A)
As loop, it is not conflict serializable. No serial
schedule exist. Or no answer whether serial
equivalent exist for this. So, use second
method, view serializable
 View Serializability

• It always gives guarantee for serializability but it

is less powerful than conflict seralizability
• View-serializability considers all the connections
between transactions T and U such that T writes a
database element whose value U reads
• The key difference between view- and
conflict serializability is that when T writes a
data item then no other transaction reads
that same data item

• All conflict serializable transactions are view

serializable but reversal is not true
 View Serializability
Consider two schedules S and S’, where the same set
of transactions participates in both schedules. The
schedules S and S’ are said to be view equivalent if
Three conditions are met:
1. If in schedule S, transaction Ti reads the initial
value of Q, then in schedule S’ also transaction
Ti mustTiread the
Tj initial value
Ti of Q.
Tj
Read Read
(Q) (Q)
Read Read Read Read
(Y) (A) (B) (A)
Write Write
Schedule
(A) S Schedule
(A) S’
 View Serializability
2. For each data item Q, if transaction Ti executes
read(Q) in schedule S, and if that value was produced by a
write(Q) operation executed by transaction Tj , then the
read(Q) operation of transaction Ti must in schedule S’ ,
also read the value of Q that was produced by the same
write(Q) operation of transaction Tj
Ti Tj Ti Tj
Read Read
(Q) (Q)
Write Write
(Q) (Q)
Read
Schedule S Schedule
(Q)
S’

Conditions 1 & 2 ensure that each transaction reads

the same data item in both schedules
 View Serializability
3. For each data item Q, the transaction (if any)
that performs the final write(Q) operation in
schedule S must perform the final write(Q)
operation in schedule S’
Ti Tj Ti Tj
Read Read
(Q) (Q)
Write Write
(Q) (Q)

Write Write
(Q) Schedule S (Q) Schedule
S’
 View Serializability Example
Schedule
Schedule
S1
S2

View
Serializab

• Transactions T4 and T6 perform in schedule (S1, S2)

write(Q) operations without having performed a read(Q)
operation. Writes of this sort are called blind writes.
• Blind writes appear in any view-serializable schedule
that is not conflict serializable
Not view
serializable
 Testing for Serializability
• When designing concurrency control schemes, we must
show that schedules generated by the scheme are
serializable

Testing for Conflict Serializability:

Method: Precedence Graph (directed graph) - G (V,

E)

V = set of vertices consists of all the transactions

participating in the schedule

E = set of edges consists of all edges Ti →Tj for which

one of three conditions holds:

1. Ti executes write(Q) before Tj executes read(Q)

2. Ti executes read(Q) before Tj executes write(Q)
3. Ti executes write(Q) before Tj executes write(Q)
Testing for Conflict Serializability:
S2
S1
T1 T2
T1 T2
Read
Read (Q)
(Q) Write
Write Write Write (Q)
(Q) (Q) (Q)
Read Read
(P) (P)
Write Write
(P) (P)

Precedence Graphs for S1 and S2

Testing for Conflict Serializability:

If the precedence graph for S has a cycle, then schedule S

is not conflict serializable.
If the graph contains no cycles, then the schedule S is
conflict serializable.
 Recoverability
• If a transaction Ti fails, for whatever reason, we need to
undo the effect of this transaction to ensure the atomicity
property of the transaction
• In a system that allows concurrent execution, it is
necessary also to ensure that any transaction Tj that is
dependent on Ti (that is, Tj has read data written by Ti) is
also aborted

Recoverable Schedules:
A recoverable schedule is one where, for each pair
of transactions Ti and Tj such that Tj reads a data item
previously written by Ti, the commit operation of Ti
appears before the commit operation of Tj .
Cascadeless Schedules:
A single transaction failure leads to a series of
transaction rollbacks, is called cascading
rollback
Even if a schedule is recoverable, to recover
correctly from the failure of a transaction Ti, we
may have to roll back several transactions

Transaction T10 writes a value of A that is read by transaction

T11. Transaction T11 writes a value of A that is read by
transaction T12.
Suppose that, at this point, T10 fails. T10 must be rolled back.
Since T11 is dependent on T10, T11 must be rolled back.
Since T12 is dependent on T11, T12 must be rolled back. This
Cascadeless schedule is one where, for each pair of
transactions Ti and Tj such that Tj reads a data item
previously written by Ti, the commit operation of Ti appears
before the read operation of Tj

Ti Tj
Read
(Q)
Write
(Q) Read
Commit (Q)
Write
(P)

Cascading rollback is undesirable