Database Management Systems UNIT-IV

UNIT-IV
LEARNING MATERIAL

1. Transaction Concept
 Transaction: A transaction is a unit of program execution that
accesses and possibly updates various data items. As an example
consider the following transaction that transfers $50 from account A to
account B. It can be written as:
1. read(A)
2. A := A – 50
3. write(A)
4. read(B)
5. B := B + 50
6. write(B)
This transaction consists of 6 actions that need to takes place in order to
transfer $50 from account A to account B.

 Comparing Transaction and Program: A transaction is the result

from the execution of user program written in high-level data
manipulation language (DML) or programming language and it is started
and ended between the statements begin transaction and end
transaction.

 Transaction operations: Every transaction access data using two

operations:
 read(X) : which transfers the data item X from the database to a
local buffer belonging to the transaction that executed the read
operation.
 write(X): which transfers the data item X from the local buffer of the
transaction that executed the write back to the database.

2. Properties of the Transaction

Department of Information Technology A.Y.2019-20 II-II GEC Page 1

 Database Management Systems UNIT-IV

 To ensure integrity of the data, we require that the database system

maintain the following properties of the transactions:
o Atomicity. Either all operations of the transaction are reflected
properly in the database, or none are.
o Consistency. Execution of a transaction in isolation (that is, with no
other transaction executing concurrently) preserves the consistency
of the database.
o 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. Thus, each transaction is unaware of
other transactions executing concurrently in the system.
o Durability. After a transaction completes successfully, the changes it
has made to the database persist, even if there are system failures.
 These properties are often called the ACID properties.
 To gain a better understanding of ACID properties and the need for them,
consider a simplified banking system consisting of several accounts and a
set of transactions that access and update those accounts.
 Let Ti be a transaction that transfers $50 from account A to account B. This
transaction can be defined as;
Ti : read(A);
A := A − 50;
write(A);
read(B);
B := B + 50;
write(B).
Let us now consider each of the ACID requirements.
 Consistency: The consistency requirement here is that the sum of A and B
be unchanged by the execution of the transaction.

Department of Information Technology A.Y.2019-20 II-II GEC Page 2

 Database Management Systems UNIT-IV

 It can be verified easily that, if the database is consistent before an

execution of the transaction, the database remains consistent after the
execution of the transaction.

 Atomicity: Suppose that, just before the execution of transaction Ti the

values of accounts A and B are $1000 and $2000, respectively.
 Now suppose that, during the execution of transaction Ti, a failure occurs
(power failures, hardware failures, and software errors) that prevent Ti from
completing its execution successfully.
 Further, suppose that the failure happened after the write(A) operation but
before the write(B) operation. In this case, the values of accounts A and B
reflected in the database are $950 and $2000. The system destroyed $50
as a result of this failure. In particular, we note that the sum A + B is no
longer preserved.
 We call such a state as an inconsistent state. We must ensure that such
inconsistencies are not visible in a database system.
 This state, however, is eventually replaced by the consistent state where
the value of account A is $950, and the value of account B is $2050.
 This is the reason for the atomicity requirement: If the atomicity property is
present, all actions of the transaction are reflected in the database, or none
are.
 The basic idea behind ensuring atomicity is this: The database system
keeps track (on disk) of the old values of any data on which a transaction
performs a write, and, if the transaction does not complete its execution,
the database system restores the old values to make it appear as though
the transaction never executed.

 Isolation: If several transactions are executed concurrently, their

operations may interleave in some undesirable way, resulting in an
inconsistent state.
 For example consider the following; 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).

Department of Information Technology A.Y.2019-20 II-II GEC Page 3

 Database Management Systems UNIT-IV

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)

 A way to avoid the problem of concurrently executing transactions is to

execute transactions serially—that is, one after the other.
 However, executing multiple transactions concurrently has significant
benefits, as we will see later.

 Durability: The durability property guarantees that, once a transaction

completes successfully (i.e., the transfer of the $50 has taken place), all
the updates that it carried out on the database persist, even if there is a
system failure after the transaction completes execution.

3. Transaction State
 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

Department of Information Technology A.Y.2019-20 II-II GEC Page 4

 Database Management Systems UNIT-IV

 In the absence of failures, all transactions complete successfully.

 A transaction may not always complete its execution successfully. Such a
transaction is termed aborted. An aborted transaction must have no
effect on the state of the database. Thus, any changes that the aborted
transaction made to the database must be undone.
 Once the changes caused by an aborted transaction have been undone, we
say that the transaction has been rolled back.
 A transaction that completes its execution successfully is said to be
committed.
 A transaction enters the failed state after the system determines that the
transaction can no longer proceed with its normal execution (for example,
because of hardware or logical errors). Such a transaction must be rolled
back. Then, it enters the aborted state. At this point, the system can
either restart the transaction or kill the transaction.
4. Schedules
 A schedule is a sequences of instructions that specify the chronological
order in which instructions of transactions are executed.
 Serial Schedule: If transactions are executed from start to finish, one
after another then the schedule is called as a serial schedule.
 Concurrent schedule: If the instructions of different transactions are
interleaved then the schedule is called as a concurrent schedule.
 Let T1 and T2 be two transactions that transfer funds from one account to
another. Transaction T1 transfers $50 from account A to account B. It is
defined as;


Department of Information Technology A.Y.2019-20 II-II GEC Page 5

 Database Management Systems UNIT-IV

T1: read(A);
A := A − 50;
write(A);
read(B);
B := B + 50;
write(B).

 Transaction T2 transfers 10 percent of the balance from account A to

account B. It is defined as;
T2: read(A);
temp := A * 0.1;
A := A − temp;
write(A);
read(B);
B := B + temp;
write(B).
 The following figure shows a serial schedule in which T1 executes before
T2.

Department of Information Technology A.Y.2019-20 II-II GEC Page 6

 Database Management Systems UNIT-IV

 Similarly, the following figure shows a serial schedule in which T2 executes

before T1.

 Thus, for a set of n transactions, there exist n! different valid serial

schedules.
 If two transactions are running concurrently, the operating system may
execute one transaction for a little while, then perform a context switch,
execute the second transaction for some time, and then switch back to the
first transaction for some time, and so on. With multiple transactions, the
CPU time is shared among all the transactions.
 Concurrent execution of transactions improves the performance of the
system. Following figure shows a concurrent schedule.

Department of Information Technology A.Y.2019-20 II-II GEC Page 7

 Database Management Systems UNIT-IV

 In case of concurrent execution, several execution sequences are possible,

since various instructions from different transactions may now be
interleaved. Thus, the number of possible schedules for a set of n
transactions is much larger than n!.

 Not all concurrent executions result in a correct state. To illustrate,

consider the schedule shown in following Figure. Suppose the current
values of accounts A and B are $1000 and $2000, respectively. After the
execution of this schedule, we arrive at a state where the final values of
accounts A and B are $950 and $2100, respectively. This final state is an
inconsistent state, since we have gained $50 in the process of the
concurrent execution and the sum A + B is not preserved by the execution
of the two transactions.

Department of Information Technology A.Y.2019-20 II-II GEC Page 8

 Database Management Systems UNIT-IV

 We can ensure consistency of the database under concurrent execution by

making sure that any schedule that executed has the same effect as a
schedule that could have occurred without any concurrent execution. The
concurrency-control component of the database system carries out this
task.
 A transaction that successfully completes its execution will have a commit
instruction 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

5. Serializability
 The database system must control concurrent execution of transactions, to
ensure that the database state remains consistent.
 For this, we must first understand which schedules will ensure consistency,
and which schedules will not. For this, we need to consider simplified view
of transactions.
 Simplified view of transactions

Department of Information Technology A.Y.2019-20 II-II GEC Page 9

 Database Management Systems UNIT-IV

o We ignore operations other than read and write instructions

o We assume that transactions may perform arbitrary computations on
data in local buffers in between reads and writes.
o Our simplified schedules consist of only read and write instructions
 The following schedule consist only read and write instructions.

 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
5.1 Conflict Serializability

 Let us consider a schedule S in which there are two consecutive

instructions Ii and Ij, of transactions Ti and Tj , respectively (i ≠ j). If Ii and Ij
refer to different data items, then we can swap Ii and Ij without affecting
the results of any instruction in the schedule. If Ii and Ij refer to the same
data item Q, then the order of the two steps may matter.
 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.
1. li = read(Q), lj = read(Q). li and lj don’t conflict.

Department of Information Technology A.Y.2019-20 II-II GEC Page 10

 Database Management Systems UNIT-IV

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
 We say that Ii and Ij conflict if they are operations by different transactions
on the same data item, and at least one of these instructions is a write
operation.
 If a schedule S can be transformed into a schedule S´ by a series of swaps
of nonconflicting 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.
 To illustrate the concept of conflicting instructions, consider schedule 3,
shown in the above figure. By performing a series of swaps of
nonconflicting instructions, schedue 3 can be transformed to a serial
schedule as follows;
 Swap read(B) of T1 with write(A) of T2. The result of this is shown beow;

 Similarly, by performing the following series of swaps of nonconflicting

instructions, schedule 3 is transformed to a serial schedule as shown below;
o Swap read(B) of T1 with read(A) of T2.
o Swap write(B) of T1 with write(A) of T2.
o Swap write(B) of T1 with read(A) of T2.

Department of Information Technology A.Y.2019-20 II-II GEC Page 11

 Database Management Systems UNIT-IV

 The final result of these swaps, schedule 6 shown above, is a serial

schedule. Thus, we have shown that schedule 3 is equivalent to a serial
schedule and therefore schedule 3 is a conflict serializable schedule..
 Consider the schedule 7 of the following figure; it consists of only the read
and write operations of transactions T3 and T4. This schedule is not conflict
serializable, since it is not equivalent to either the serial schedule <T3,T4>
or the serial schedule <T4,T3>.

Schedule 7
5.2 View Serializability

 Let S and S1 be two schedules with the same set of transactions. The
schedules S and S1 are said to be view equivalent if three conditions are
met, for each data item Q:
1. If in schedule S, transaction Ti reads the initial value of Q, then in
schedule S’ also transaction Ti must read the initial value of Q.

Department of Information Technology A.Y.2019-20 II-II GEC Page 12

 Database Management Systems UNIT-IV

2. If in schedule S transaction Ti executes read(Q), and that value was

produced by transaction Tj (if any), then in schedule S’ also transaction
Ti must read the value of Q that was produced by the same write(Q)
operation of transaction Tj .
3. The transaction (if any) that performs the final write(Q) operation in
schedule S must also perform the final write(Q) operation in schedule
S’.
As can be seen, view equivalence is also based purely on reads and
writes alone.

 A schedule S is view serializable if it is view equivalent to a serial

schedule.
 Every conflict serializable schedule is also view serializable.
 Below is a schedule which is viewserializable but not conflict serializable.

Schedule 9 – A view serializable schedule

 Every view serializable schedule that is not conflict serializable has blind
writes
Testing for Serializability
 Consider some schedule of a set of transactions T1, T2, ..., Tn
 Precedence graph — a direct graph where the vertices are the
transactions (names).
 We draw an arc from Ti to Tj if the two transaction conflict.
 A schedule is conflict serializable iff its precedence graph is acyclic.
 Examples;

Department of Information Technology A.Y.2019-20 II-II GEC Page 13

 Database Management Systems UNIT-IV

Schedule (c)
 The schedules shown above are conflict serializable schedules since, their
precedence graphs are acyclic.
 The following schedule is not conflict serializable as its precedence graph
consists a cycle.

Department of Information Technology A.Y.2019-20 II-II GEC Page 14

 Database Management Systems UNIT-IV

6. Recoverability
 If a transaction Ti fails, we need to undo the effect of this transaction to
ensure the atomicity property of the transaction.
 In the following sections, we address the issue of what schedules are
acceptable from the viewpoint of recovery from transaction failure.

6.1 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 .
 The following schedule (schedule 11) is not a recoverable schedule if T9
commits immediately after the read(A) operation.

Schedule 11 – non-recoverable schedule

Department of Information Technology A.Y.2019-20 II-II GEC Page 15

 Database Management Systems UNIT-IV

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

6.2 Cascadeless Schedules

 Cascading rollback – a single transaction failure leads to a series of
transaction rollbacks.
 Consider the following schedule where none of the transactions has yet
committed (so the schedule is recoverable).

Schedule 12

If T10 fails, T11 and T12 must also be rolled back.

 Cascading rollback lead to the undoing of a significant amount of work.

 A 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 .
 Every cascadeless schedule is also recoverable
 It is desirable to restrict the schedules to those that are cascadeless.

Department of Information Technology A.Y.2019-20 II-II GEC Page 16