TRANSACTIONS

6/5/2023
Transaction Concept
Transaction State

Parul Saxena
Implementation of Atomicity and Durability
Concurrent Executions
Serializability
Recoverability

1
TRANSACTION CONCEPT

6/5/2023
A transaction is a unit of program execution
that accesses and possibly updates various data
items.

Parul Saxena
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.
Two main issues to deal with:
Failures of various kinds, such as hardware failures and
system crashes
Concurrent execution of multiple transactions

2
ACID PROPERTIES
To preserve integrity of data, the database system must
ensure:

6/5/2023
Atomicity. Either all operations of the transaction
are properly reflected in the database or none are.
Consistency. Execution of a transaction in

Parul Saxena
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. 3
EXAMPLE OF FUND TRANSFER

6/5/2023
Transaction to transfer $50 from account A to account B:
1. read(A)
2. A := A – 50

Parul Saxena
3. write(A)
4. read(B)
5. B := B + 50
6. write(B)
Consistency requirement – the sum of A and B is unchanged
by the execution of the transaction i.e. total of all accounts is
constant.
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.

4
EXAMPLE OF FUND TRANSFER (CONT.)

6/5/2023
Durability requirement — once the user has been
notified that the transaction has completed (i.e.,

Parul Saxena
the transfer of the $50 has taken place), the
updates to the database by the transaction must
persist despite failures.
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
5
 6/5/2023
A transaction is a single logical unit of work which
accesses and possibly modifies the contents of a

Parul Saxena
database. Transactions access data using read and write
operations.
In order to maintain consistency in a database, before
and after the transaction, certain properties are followed.
These are called ACID properties.

6
6/5/2023 Parul Saxena
7
ATOMICITY

6/5/2023
By this, we mean that either the entire transaction
takes place at once or doesn’t happen at all. There

Parul Saxena
is no midway i.e. transactions do not occur
partially. Each transaction is considered as one
unit and either runs to completion or is not
executed at all. It involves the following two
operations.
— Abort: If a transaction aborts, changes made to
database are not visible.
— Commit: If a transaction commits, changes
made are visible.
Atomicity is also known as the ‘All or nothing 8
rule’.
Consider the following transaction T consisting
of T1 and T2: Transfer of 100 from account X to
account Y.

6/5/2023
Parul Saxena
If the transaction fails after completion of T1 but before
completion of T2.( say, after write(X) but before write(Y)),
then amount has been deducted from X but not added to Y.
This results in an inconsistent database state. Therefore, the
transaction must be executed in entirely in order to ensure
correctness of database state.
9
Consistency
This means that integrity constraints must be
maintained so that the database is consistent

6/5/2023
before and after the transaction. It refers to the
correctness of a database. Referring to the

Parul Saxena
example above,
The total amount before and after the transaction
must be maintained.
Total before T occurs = 500 + 200 = 700.
Total after T occurs = 400 + 300 = 700.
Therefore, database is consistent. Inconsistency
occurs in case T1 completes but T2 fails. As a
result T is incomplete.

10
Isolation
This property ensures that multiple transactions
can occur concurrently without leading to the

6/5/2023
inconsistency of database state. Transactions
occur independently without interference.
Changes occurring in a particular transaction

Parul Saxena
will not be visible to any other transaction until
that particular change in that transaction is
written to memory or has been committed. This
property ensures that the execution of
transactions concurrently will result in a state
that is equivalent to a state achieved these were
executed serially in some order.
Let X= 500, Y = 500.
Consider two transactions T and T”. 11
 6/5/2023
Parul Saxena
Suppose T has been executed till Read (Y) and
then T’’ starts. As a result , interleaving of operations
takes place due to which T’’ reads correct value
of X but incorrect value of Y and sum computed by
T’’: (X+Y = 50, 000+500=50, 500)
is thus not consistent with the sum at end of
transaction:
T: (X+Y = 50, 000 + 450 = 50, 450).
This results in database inconsistency. Hence,
transactions must take place in isolation and changes
should be visible only after they have been made to 12
the main memory.
Durability:
This property ensures that once the transaction has
completed execution, the updates and modifications to

6/5/2023
the database are stored in and written to disk and they
persist even if a system failure occurs. These updates

Parul Saxena
now become permanent and are stored in non-volatile
memory. The effects of the transaction, thus, are never
lost.
The ACID properties, in totality, provide a mechanism to
ensure correctness and consistency of a database in a
way such that each transaction is a group of operations
that acts a single unit, produces consistent results, acts in
isolation from other operations and updates that it makes
are durably stored.
13
TRANSACTION STATE

6/5/2023
Active, the initial state; the transaction stays in this state
while it is executing. During this state read or write
operations can be performed.

Parul Saxena
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
kill the transaction
Committed, after successful completion. 14
TRANSACTION STATE (CONT.)

6/5/2023
Parul Saxena
15
IMPLEMENTATION OF ATOMICITY AND
DURABILITY
The recovery-management component of a

6/5/2023
database system implements the support for
atomicity and durability.

Parul Saxena
The shadow-database scheme:
assume that only one transaction is active at a time.
a pointer called db_pointer always points to the current
consistent copy of the database.
all updates are made on a shadow copy of the database,
and db_pointer is made to point to the updated shadow
copy only after the transaction reaches partial commit and
all updated pages have been flushed to disk.
in case transaction fails, old consistent copy pointed to by
db_pointer can be used, and the shadow copy can be
deleted.
16
 IMPLEMENTATION OF ATOMICITY AND DURABILITY
(CONT.)
The shadow-database scheme:

6/5/2023
Parul Saxena
Assumes disks to not fail
Useful for text editors, but extremely inefficient
for large databases: executing a single
17
transaction requires copying the entire database.
CONCURRENT EXECUTIONS
Multiple transactions are allowed to run

6/5/2023
concurrently in the system. Advantages are:
increased processor and disk utilization, leading
to better transaction throughput: one transaction can

Parul Saxena
be using the CPU while another is reading from or
writing to the disk
reduced average response time for transactions:
short transactions need not wait behind long ones.
Concurrency control schemes – mechanisms to
achieve isolation, i.e., to control the interaction
among the concurrent transactions in order to
prevent them from destroying the consistency
of the database 18
SCHEDULES

6/5/2023
Schedules – sequences that indicate the
chronological order in which instructions of

Parul Saxena
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.

19
EXAMPLE SCHEDULES
Let T1 transfer $50 from A to B, and T2 transfer 10%

6/5/2023
of the balance from A to B. The following is a serial
schedule (Schedule 1), in which T1 is followed by T2.

Parul Saxena
20
EXAMPLE SCHEDULE (CONT.)
Let T1 and T2 be the transactions defined previously. The
following schedule (Schedule 3) is not a serial schedule, but

6/5/2023
it is equivalent to Schedule 1.

Parul Saxena
21

In both Schedule 1 and 3, the sum A + B is preserved.

EXAMPLE SCHEDULES (CONT.)
The following concurrent schedule (Schedule 4) does
not preserve the value of the the sum A + B.

6/5/2023
Parul Saxena
22
SERIALIZABILITY
Basic Assumption – Each transaction preserves
database consistency.

6/5/2023
Thus serial execution of a set of transactions
preserves database consistency.

Parul Saxena
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:
1. conflict serializability
2. view serializability
We ignore operations other than read and write
instructions, and 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.
23
CONFLICT SERIALIZABILITY

6/5/2023
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

Parul Saxena
these instructions wrote Q.
1. li = read(Q), lj = read(Q). li and lj don’t conflict.
2. li = read(Q), lj = write(Q). They conflict.
3. li = write(Q), lj = read(Q). They conflict
4. li = write(Q), lj = write(Q). They conflict
Intuitively, a conflict between li and lj forces a
(logical) temporal order between them. If li and lj are
consecutive in a schedule and they do not conflict,
their results would remain the same even if they had
been interchanged in the schedule. 24
CONFLICT SERIALIZABILITY (CONT.)
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.

6/5/2023
We say that a schedule S is conflict serializable if it is
conflict equivalent to a serial schedule

Parul Saxena
Example of a schedule that is not conflict serializable:
T3 T4

read(Q)
write(Q)
write(Q)

We are unable to swap instructions in the above schedule

to obtain either the serial schedule < T3, T4 >, or the
serial schedule < T4, T3 >. This is not conflict serializable.

25
CONFLICT SERIALIZABILITY (CONT.)
Schedule 3 below can be transformed into

6/5/2023
Schedule 1, a serial schedule where T2 follows
T1, by series of swaps of non-conflicting

Parul Saxena
instructions. Therefore Schedule 3 is conflict
serializable.

26
WHICH OF THE FOLLOWING ARE CONFLICT SERIALIZABLE

S1: W1(A)W1(B)W2(A)R2(B)

6/5/2023
S2: W2(A)W1(B)W1(A)R2(B)
R1(X)R2(X)W1(X)W2(X)

Parul Saxena
R1(X)W2(X)W1(X)
W1(X)R2(X)W1(X)
R1(X)R2(X)R2(Y)W1(X)W1(Y)W2(Y)
R1(X)R2(X)R2(Y)W1(X)W2(Y)W1(Y)
R1(X)W1(X)R2(X)W1(Y)R2(Y)W2(Y)
R2(X)R2(Y)R1(X)W1(X)W1(Y)W2(Y)
R2(X)W3(X)W1(Y)R2(Y)W2(Z)
S : r1(x) r1(y) w2(x) w1(x) r2(y)
S1: r1(x) r3(y) w1(x) w2(y) r3(x) w2(x) 27
VIEW SERIALIZABILITY

Let S and S´ be two schedules with the same set of

6/5/2023
transactions. S and S´ are view equivalent if the
following three conditions are met:

Parul Saxena
1. For each data item Q, if transaction Ti reads the initial value of Q in
schedule S, then transaction Ti must, in schedule S´, also read the
initial value of Q.
2. For each data item Q if transaction Ti executes read(Q) in schedule
S, and that value was produced by transaction Tj (if any), then
transaction Ti must in schedule S´ also read the value of Q that was
produced by transaction Tj .
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´.
As can be seen, view equivalence is also based purely on
reads and writes alone.

28
VIEW SERIALIZABILITY (CONT.)
A schedule S is view serializable it is view
equivalent to a serial schedule.

6/5/2023
Every conflict serializable schedule is also view
serializable.

Parul Saxena
Schedule — a schedule(left side) which is view-
serializable but not conflict serializable.

Every view serializable schedule that is not conflict

29
serializable has blind writes.
WHY WE NEED VIEW SERIALIZABILITY?
As we know that a serial schedule never leaves
the database in inconsistent state because there
are no concurrent transactions execution.

6/5/2023
However a non-serial schedule can leave the
database in inconsistent state because there are

Parul Saxena
multiple transactions running concurrently. By
checking that a given non-serial schedule is view
serializable, we make sure that it is a consistent
schedule.
We may be wondering instead of checking that a
non-serial schedule is serializable or not, can’t we
have serial schedule all the time? The answer is
no, because concurrent execution of transactions
fully utilize the system resources and are
considerably faster compared to serial schedules. 30
VIEW EQUIVALENT
Two schedules T1 and T2 are said to be view
equivalent, if they satisfy all the following conditions:
1. Initial Read: Initial read of each data item in
transactions must match in both schedules. For

6/5/2023
example, if transaction T1 reads a data item X before
transaction T2 in schedule S1 then in schedule S2, T1
should read X before T2.

Parul Saxena
2. Final Write: Final write operations on each data
item must match in both the schedules. For example,
a data item X is last written by Transaction T1 in
schedule S1 then in S2, the last write operation on X
should be performed by the transaction T1.
3. Update Read: If in schedule S1, the transaction T1
is reading a data item updated by T2 then in schedule
S2, T1 should read the value after the write operation
of T2 on same data item. For example, In schedule S1,
T1 performs a read operation on X after the write
operation on X by T2 then in S2, T1 should read the X
after T2 performs write on X.
31
VIEW SERIALIZABLE
If a schedule is view equivalent to its serial
schedule then the given schedule is said to be
View Serializable. Lets take an example.

6/5/2023
View Serializable Example

Parul Saxena
32
Initial Read
In schedule S1, transaction T1 first reads the data item X. In S2
also transaction T1 first reads the data item X.
Lets check for Y. In schedule S1, transaction T1 first reads the
data item Y. In S2 also the first read operation on Y is performed
by T1.

6/5/2023
We checked for both data items X & Y and the initial
read condition is satisfied in S1 & S2.
Final Write

Parul Saxena
In schedule S1, the final write operation on X is done by
transaction T2. In S2 also transaction T2 performs the final write
on X.
Lets check for Y. In schedule S1, the final write operation on Y is
done by transaction T2. In schedule S2, final write on Y is done by
T2.
We checked for both data items X & Y and the final
write condition is satisfied in S1 & S2.
Update Read
In S1, transaction T2 reads the value of X, written by T1. In S2,
the same transaction T2 reads the X after it is written by T1.
In S1, transaction T2 reads the value of Y, written by T1. In S2,
the same transaction T2 reads the value of Y after it is updated
by T1. 33
The update read condition is also satisfied for both the schedules.
RECOVERABILITY
Need to address the effect of transaction failures on
concurrently running transactions.

6/5/2023
Recoverable schedule — if a transaction Tj reads a data
items previously written by a transaction Ti , the commit

Parul Saxena
operation of Ti appears before the commit operation of Tj.
The following schedule is not recoverable if T9 commits
immediately after the read

If T8 should abort, T9 would have read (and possibly shown to

the user) an inconsistent database state. Hence database
must ensure that schedules are recoverable.
34
CASCADING ROLLBACK SCHEDULE-

6/5/2023
If in a schedule, failure of one transaction causes

Parul Saxena
several other dependent transactions to rollback
or abort, then such a schedule is called as
a Cascading Schedule or Cascading
Rollback or Cascading Abort.
It simply leads to the wastage of CPU time.

35
6/5/2023 Parul Saxena
36
Here,
Transaction T2 depends on transaction T1.
Transaction T3 depends on transaction T2.
Transaction T4 depends on transaction T3.

6/5/2023
In this schedule,

Parul Saxena
The failure of transaction T1 causes the transaction T2
to rollback.
The rollback of transaction T2 causes the transaction T3 to
rollback.
The rollback of transaction T3 causes the transaction T4 to
rollback.
Such a rollback is called as a Cascading Rollback.

NOTE-

If the transactions T2, T3 and T4 would have committed

before the failure of transaction T1, then the schedule
would have been irrecoverable. 37
CASCADELESS SCHEDULE-

If in a schedule, a transaction is not allowed to

6/5/2023
read a data item until the last transaction that
has written it is committed or aborted, then such
a schedule is called as a Cascadeless Schedule.

Parul Saxena
In other words,
Cascadeless schedule allows only committed read
operations.
Therefore, it avoids cascading roll back and thus
saves CPU time.

38
6/5/2023 Parul Saxena
39
STRICT SCHEDULE-

If in a schedule, a transaction is neither

6/5/2023
allowed to read nor write a data item until
the last transaction that has written it is

Parul Saxena
committed or aborted, then such a schedule is
called as a Strict Schedule.
In other words,
Strict schedule allows only committed read and
write operations.
Clearly, strict schedule implements more
restrictions than cascadeless schedule.

40
6/5/2023 Parul Saxena
41
Remember-
Strict schedules are more strict than cascadeless
schedules.

6/5/2023
All strict schedules are cascadeless schedules.
All cascadeless schedules are not strict schedules.

Parul Saxena
42
RECOVERABILITY (CONT.)
Cascading rollback – a single transaction failure

6/5/2023
leads to a series of transaction rollbacks. Consider
the following schedule where none of the
transactions has yet committed (so the schedule is
recoverable)

Parul Saxena
If T10 fails, T11 and T12 must also be rolled back.
Can lead to the undoing of a significant amount of
work
43
RECOVERABILITY (CONT.)

6/5/2023
Cascadeless schedules — cascading rollbacks
cannot occur; for each pair of transactions Ti and

Parul Saxena
Tj such that Tj reads a data item previously
written by Ti, the commit operation of Ti appears
before the read operation of Tj.
Every cascadeless schedule is also recoverable
It is desirable to restrict the schedules to those
that are cascadeless

44
 6/5/2023
S1 : W2(A)W1(B)W1(A)R2(B)C1C2
R1(X)R2(X)W1(X)W2(X)

Parul Saxena
R1(X)W2(X)W1(X)c1
R1(X)W2(X)W1(X)C2C1
W1(X)R2(X)W1(X)c1
W1(X)R2(X)W1(X)C2C1
R2(X)W3(X)C3W1(Y)C1R2(Y)W2(Z)C2

45
IRRECOVERABLE SCHEDULE:

6/5/2023
Parul Saxena
46
RECOVERABLE WITH CASCADING
ROLLBACK:

6/5/2023
Parul Saxena
47
CASCADELESS RECOVERABLE
ROLLBACK:

6/5/2023
Parul Saxena
48
TESTING FOR SERIALIZABILITY
Consider some schedule of a set of transactions
T1, T2, ..., Tn

6/5/2023
Precedence graph — a direct graph where the
vertices are the transactions (names).
We draw an arc from Ti to Tj if the two

Parul Saxena
transaction conflict, and Ti accessed the data
item on which the conflict arose earlier.
We may label the arc by the item that was
accessed.
Example 1

49
y
EXAMPLE SCHEDULE (SCHEDULE A)
T1 T2 T3 T4 T5
read(X)

6/5/2023
read(Y)
read(Z)
read(V)
read(W)

Parul Saxena
read(W)
read(Y)
write(Y)
write(Z)
read(U)
read(Y)
write(Y)
read(Z)
write(Z)
read(U)
write(U)

50
PRECEDENCE GRAPH FOR SCHEDULE A

6/5/2023
T1 T2

Parul Saxena
T4
T3

51
PROBLEM-01:
Are the following three schedules result
equivalent?

6/5/2023
Parul Saxena
52
Solution-

To check whether the given schedules are result equivalent

or not,
We will consider some arbitrary values of X and Y.

6/5/2023
Then, we will compare the results produced by each schedule.
Those schedules which produce the same results will be result
equivalent.

Parul Saxena
Let X = 2 and Y = 5.
On substituting these values, the results produced by each
schedule are-

Results by Schedule S1- X = 21 and Y = 10

Results by Schedule S2- X = 21 and Y = 10
Results by Schedule S3- X = 11 and Y = 10

Clearly, the results produced by schedules S1 and S2 are

same.
Thus, we conclude that S1 and S2 are result equivalent 53
schedules.
PROBLEM-02:
Are the following two schedules conflict
equivalent?

6/5/2023
Parul Saxena
54
Solution-
To check whether the given schedules are conflict equivalent or not,
We will write their order of pairs of conflicting operations.
Then, we will compare the order of both the schedules.
If both the schedules are found to have the same order, then they will be
conflict equivalent.

6/5/2023
For schedule S1-

Parul Saxena
The required order is-
R1(A) , W2(A)
W1(A) , R2(A)
W1(A) , W2(A)

For schedule S2-

The required order is-

R1(A) , W2(A)
W1(A) , R2(A)
W1(A) , W2(A)

Clearly, both the given schedules have the same order.

Thus, we conclude that S1 and S2 are conflict equivalent schedules. 55
6/5/2023 Parul Saxena
END OF CHAPTER
56
SCHEDULE 2 -- A SERIAL SCHEDULE IN WHICH
T2 IS FOLLOWED BY T1

6/5/2023
Parul Saxena
57
SCHEDULE 5 -- SCHEDULE 3 AFTER SWAPPING A PAIR
OF INSTRUCTIONS

6/5/2023
Parul Saxena
58
SCHEDULE 6 -- A SERIAL SCHEDULE THAT IS
EQUIVALENT TO SCHEDULE 3

6/5/2023
Parul Saxena
59
 6/5/2023 Parul Saxena
60
SCHEDULE 7
PRECEDENCE GRAPH FOR
(A) SCHEDULE 1 AND (B) SCHEDULE 2

6/5/2023
Parul Saxena
61
ILLUSTRATION OF TOPOLOGICAL SORTING

6/5/2023
Parul Saxena
62
 6/5/2023 Parul Saxena
63
PRECEDENCE GRAPH
 6/5/2023 Parul Saxena
64
15.21
FIG.