Database Management System

Module 5

1
 Introduction to Transaction
Processing Concepts and
Theory

2
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Introduction to Transaction Processing
Transactions refer to a set of operations that are used for performing a set of logical work.
- A transaction is a single logical unit of work that accesses and possibly modifies the
contents of a database. Transactions access data using read and write operations.
- A transaction includes one or more database access operations—these can include
insertion, deletion, modification, or retrieval operations.

Single-User versus Multiuser Systems

A DBMS is single-user if at most one user at a time can use the system.
Multiuser if many users can use the system concurrently.

Single-user DBMSs are mostly restricted to personal computer systems.

An airline reservations system is used by hundreds of users and travel agents concurrently.

Multiple users can access databases—and use computer systems—simultaneously because of

the concept of multiprogramming, which allows the operating system of the computer to
execute multiple programs—or processes—at the same time

3
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Different properties of transaction
1. Atomicity - mean that either the entire transaction takes place at once or doesn’t
happen at all. There 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 the database are not visible.
Commit: If a transaction commits, changes made are visible.

Atomicity is also known as the ‘All or nothing rule’.

2. Consistency: Integrity constraints must be maintained so that the database is consistent

before and after the transaction. It refers to the correctness of a database.

4
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 3. Isolation: This property ensures that multiple transactions can occur concurrently
without leading to the inconsistency of the database state.

Changes occurring in a particular transaction will not be visible to any other

transaction until that particular change in that transaction is written to memory or
has been committed.

4. Durability: This property ensures that once the transaction has completed
execution, the updates and modifications to the database are stored in and written to
disk and they persist even if a system failure occurs. These updates now become
permanent and are stored in non-volatile memory. The effects of the transaction, thus,
are never lost.

5
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
Interleaved processing versus parallel processing of concurrent
transactions.

6
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Transactions, Database Items, Read and Write
Operations, and DBMS Buffers
1. A transaction is an executing program that forms a logical unit of database
processing. The database operations that form a transaction can either be embedded
within an application program or they can be specified interactively via a high-level
query language such as SQL.
2. One way of specifying the transaction boundaries is by specifying explicit begin
transaction and end transaction statements in an application program; in this case,
all database access operations between the two are considered as forming one
transaction.
3. A single application program may contain more than one transaction if it contains
several transaction boundaries. If the database operations in a transaction do not
update the database but only retrieve data, the transaction is called a read-only
transaction; otherwise it is known as a read-write transaction.

7
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 The basic database access operations that a transaction can include are as follows:

1. read_item(X). Reads a database item named X into a program variable. To simplify

our notation,we assume that the program variable is also named X.

2. write_item(X). Writes the value of program variable X into the database item named
X.

8
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Executing a read_item (X) command includes the following steps:

1. Find the address of the disk block that contains item X.

2. Copy that disk block into a buffer in main memory (if that disk block is not already in
some main memory buffer). The size of the buffer is the same as the disk block size.
3. Copy item X from the buffer to the program variable named X.

Executing a write_item (X) command includes the following steps:

1. Find the address of the disk block that contains item X.

2. Copy that disk block into a buffer in main memory (if that disk block is not already in
some main memory buffer).
3. Copy item X from the program variable named X into its correct location in the
buffer.
4. Store the updated disk block from the buffer back to disk (either immediately or at
some later point in time).

9
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Transaction States
Active State : When the instructions of the transaction are running then the transaction is
in active state. If all the ‘read and write’ operations are performed without any error then it
goes to the “partially committed state”; if any instruction fails, it goes to the “failed state”.

10
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 2. Partially Committed: After completion of all the read and write
operation the changes are made in main memory or local buffer. If the
changes are made permanent on the Database then the state will change
to “committed state” and in case of failure it will go to the “failed state”.

3. Failed State: When any instruction of the transaction fails, it goes to

the “failed state” or if failure occurs in making a permanent change of
data on Database.

4. Committed State: It is the state when the changes are made

permanent on the Database and the transaction is complete and therefore
terminated in the “terminated state”.

5. Terminated State: If there isn’t any roll-back or the transaction

comes from the “committed state”, then the system is consistent and
ready for new transaction and the old transaction is terminated.

11
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Why Concurrency Control Is Needed
1. Several problems can occur when concurrent transactions execute in an uncontrolled
manner. We illustrate some of these problems by referring to a much simplified
airline reservations database in which a record is stored for each airline flight.
2. Transaction T1 that transfers N reservations from one flight whose number of reserved
seats is stored in the database item named X to another flight whose number of
reserved seats is stored in the database item named Y.

12
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 The Lost Update Problem
Occurs when two transactions read the same data and then update it, with one
update overwriting the other.

If X = 80 at the start (originally there were 80 reservations on the flight), N = 5 (T1

transfers 5 seat reservations from the flight corresponding to X to the flight corresponding
to Y), and M = 4 (T2 reserves 4 seats on X).

13
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 The Temporary Update (or Dirty Read) Problem
Occurs when a transaction reads data that has been modified by another transaction
but not yet committed. If the modifying transaction is rolled back, the reading
transaction has read invalid data.

14
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 The Incorrect Summary Problem
Occurs when one transaction is calculating an aggregate summary of data while
other transactions are updating the data, leading to an incorrect summary.

15
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Unrepeatable Read Problem

Occurs when a transaction reads the same data multiple times and gets different
results because another transaction modifies the data in between the reads.

T1 T2

Reads Balance: 1000

UPDATE Account
Balance = 1200

Reads Balance: 1200

16
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Why Recovery Is Needed
Whenever a transaction is submitted to a DBMS for execution, the system is responsible
for making sure that either all the operations in the transaction are completed successfully
and their effect is recorded permanently in the database, or
that the transaction does not have any effect on the database or any other transactions.

In the first case, the transaction is said to be committed, whereas in the second case, the
transaction is aborted.

17
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Types of Failures
Failures are generally classified as transaction, system, and media failures.

1. A computer failure (system crash) - A hardware, software, or network error occurs

in the computer system during transaction execution. Hardware crashes are usually
media failures
2. A transaction or system error - Some operation in the transaction may cause it to
fail, such as integer overflow or division by zero. Transaction failure may also occur
because of erroneous parameter values or because of a logical programming error.
3. Local errors or exception conditions detected by the transaction - During
transaction execution, certain conditions may occur that necessitate cancellation of
the transaction.

18
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 4. Concurrency control enforcement - The concurrency control method may abort a
transaction because it violates serializability or it may abort one or more transactions to
resolve a state of deadlock among several transactions. Transactions aborted because of
serializability violations or deadlocks are typically restarted automatically at a later time

5. Disk failure - Some disk blocks may lose their data because of a read or write
malfunction or because of a disk read/write head crash. This may happen during a read or
a write operation of the transaction.

6. Physical problems and catastrophes - This refers to an endless list of problems that
includes power or air-conditioning failure, fire, theft, sabotage, overwriting disks or tapes
by mistake, and mounting of a wrong tape by the operator.

19
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 The System Log
To be able to recover from failures that affect transactions, the system maintains a log to keep
track of all transaction operations that affect the values of database items, as well as other
transaction information that may be needed to permit recovery from failures.

The following are the types of entries—called log-records—that are written to the log file
and the corresponding action for each log record. In these entries, T refers to a unique
transaction-id that is generated automatically by the system for each transaction and that is
used to identify each transaction:

1. [start transaction, T]: Indicates that the transaction T has started execution.
2. [write item, T, X, old value, new value]: Indicates that transaction T has changed the
value of database item X from old value to new value.
3. [read item, T, X]: Indicates that transaction T has read the value of database item X.
4. [commit, T]. Indicates that transaction T has completed successfully, and affirms that its
effect can be committed (recorded permanently) to the database.
5. [abort, T]. Indicates that transaction T has been aborted.

20
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Characterizing Schedules Based on Recoverability
When transactions are executing concurrently in an interleaved fashion, then the order of
execution of operations from all the various transactions is known as a schedule (or
history).

Schedules (Histories) of Transactions

A schedule (or history) S of n transactions T1, T2, ..., Tn is an ordering of the

operations of the transactions subject to the constraint that, for each transaction Ti
that participates in S, the operations of Ti in S must appear in the same order in which
they occur in Ti . Note, however, that operations from other transactions Tj can be
interleaved with the operations of Ti in S.

21
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 A shorthand notation for describing a schedule uses the symbols b, r, w, e,
c, and a for the operations

b begin_transaction
r read_item
w write_item ,
e end_transaction ,
c commit
a abort

22
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Sa : r1(X); r2(X); w1(X); r1(Y); w2(X); w1(Y);

The schedule can be written as above.

23
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Sb : r1(X); w1(X); r2(X); w2(X); r1(Y); a1 ;

24
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Conflicting Operations in a Schedule: Two operations in a schedule are
said to conflict if they satisfy all three of the following conditions:

(1) they belong to different transactions

(2) they access the same item X and

(3) at least one of the operations is a write_item(X).

25
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 - In Sa the operations r1(X) and w2(X) conflict, as do the operations r2(X) and
w1(X), and the operations w1(X) and w2(X).
- The operations r1(X) and r2(X) do not conflict, since they are both read
operations
- The operations w2(X) and w1(Y) do not conflict because they operate on
distinct data items X and Y
- The operations r1(X) and w1(X) do not conflict because they belong to the
same transaction.

26
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 A schedule S of n transactions T1, T2, ..., Tn, is said to be a complete schedule if
the following conditions hold:
1. The operations in S are exactly those operations in T1, T2, ..., Tn, including a
commit or abort operation as the last operation for each transaction in the
schedule.
2. For any pair of operations from the same transaction Ti , their order of
appearance in S is the same as their order of appearance in Ti .
3. For any two conflicting operations, one of the two must occur before the
other in the schedule.

27
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Read-Write Conflict:

1. If Transaction T1 reads a data item before Transaction T2 writes to it, T1 gets the
old value of the data item.
2. If T2 writes to the data item before T1 reads it, T1 gets the new value.
3. The order affects the value read by T1 and thus the outcome of T1.

Write-Write Conflict:

1. If Transaction T1 writes to a data item before Transaction T2 writes to it, the final
value of the data item will be what T2 wrote.
2. If T2 writes before T1, the final value will be what T1 wrote.
3. The order affects the final value of the data item.

28
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Once a transaction T is committed, it should never be necessary to roll back T. This
ensures that the durability property of transactions is not violated. The schedules that
theoretically meet this criterion are called recoverable schedules.

A schedule where a committed transaction may have to be rolled back during recovery is
called nonrecoverable and hence should not be permitted by the DBMS.

If sufficient information is kept (in the log), a recovery algorithm can be devised for any
recoverable schedule.

The (partial) schedules Sa, and Sb from are both recoverable, since they satisfy the above
definition. Consider the schedule S, given below, which is the same as schedule Sa except
that two commit operations have been added to Sa :

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

Sa' is recoverable, even though it suffers from the lost update problem; this problem is
handled by serializability theory.

29
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
Sc : r1(X); w1(X); r2(X); r1(Y); w2(X); c2 ; a1 ;
Sc is not recoverable because T2 reads item X from T1, but T2 commits before T1 commits.
The problem occurs if T1 aborts after the c2 operation in Sc ; then the value of X that T2 read
is no longer valid and T2 must be aborted after it is committed, leading to a schedule that is
not recoverable.

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

For the schedule to be recoverable, the c2 operation in Sc must be postponed until after T1
commits, as shown in Sd.

Se : r1(X); w1(X); r2(X); r1(Y); w2(X); w1(Y); a1 ; a2 ;

If T1 aborts instead of committing, then T2 should also abort as shown in Se , because the
value of X it read is no longer valid. In Se , aborting T2 is acceptable since it has not
committed yet, which is not the case for the nonrecoverable schedule Sc .

30
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Characterizing Schedules Based on Serializability
They have characterized schedules based on their recoverability properties. Now we
characterize the types of schedules that are always considered to be correct when
concurrent transactions are executing. Such schedules are known as serializable
schedules.

Suppose that two users—for example, two airline reservations agents—submit to the
DBMS transactions T1 and T2 in Slide 12 at approximately the same time. If no
interleaving of operations is permitted, there are only two possible outcomes:

1. Execute all the operations of transaction T1 (in sequence) followed by all the
operations of transaction T2 (in sequence).
2. Execute all the operations of transaction T2 (in sequence) followed by all the
operations of transaction T1 (in sequence).

These two schedules—called serial schedules

31
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 A schedule S is serial if, for every transaction T participating in the
schedule, all the operations of T are executed consecutively in the
schedule; otherwise, the schedule is called nonserial.

Consider the schedules in (a), (b), (c) , and assume that the initial values of
database items are X = 90 and Y = 90 and that N = 3 and M = 2. After
executing transactions T1 and T2,we would expect the database values to be
X = 89 and Y= 93, according to the meaning of the transactions. Executing
either of the serial schedules A or B gives the correct results.

Now consider the nonserial schedules C and D.Schedule C gives the results
X= 92 and Y= 93, in which the X value is erroneous, whereas schedule D
gives the correct results.

32
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Schedules A and B in Figures(a) and (b) are called serial because the operations of each
transaction are executed consecutively, without any interleaved operations from the other
transaction. In a serial schedule, entire transactions are performed in serial order: T1 and
then T2

33
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Schedules C and D in (c) are called nonserial because each sequence interleaves operations
from the two transactions.

Schedule C gives an erroneous result because of the lost update problem. Transaction T2
reads the value of X before it is changed by transaction T1, so only the effect of T2 on X is
reflected in the database. The effect of T1 on X is lost, overwritten by T2, leading to the
incorrect result for item X. However, some nonserial schedules give the correct expected
result, such as schedule D.

34
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 The definition of serializable schedule is as follows: A schedule S of n transactions is
serializable if it is equivalent to some serial schedule of the same n transactions.

There are several ways to define schedule equivalence. Two schedules are called result
equivalent if they produce the same final state of the database. However, two different
schedules may accidentally produce the same final state.

For example, in Figure below, schedules S1 and S2 will produce the same final database
state if they execute on a database with an initial value of X= 100; however, for other
initial values of X, the schedules are not result equivalent.

35
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 The definition of conflict equivalence of schedules is as follows:
Two schedules are said to be conflict equivalent if the order of any two conflicting
operations is the same in both schedules.

Two operations in a schedule are said to conflict if they belong to different transactions,
access the same database item, and either both are write_item operations or one is a
write_item and the other a read_item.

If two conflicting operations are applied in different orders in two schedules, the effect
can be different on the database or on the transactions in the schedule, and hence the
schedules are not conflict equivalent.

36
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Serializable Schedules. Using the notion of conflict equivalence, we define a schedule
S to be serializable if it is (conflict) equivalent to some serial schedule S′.

In such a case, we can reorder the nonconflicting operations in S until we form the
equivalent serial schedule S′.

According to this definition, schedule D in Figure 20.5(c) is equivalent to the serial

schedule A in Figure 20.5(a).
read_item (X) of T2 reads the value of X written by T1
T1 is the last transaction to write Y
T2 is the last transaction to write X in both schedules

Schedule C in Figure 20.5(c) is not equivalent to either of the two possible serial
schedules A and B, and hence is not serializable.

r2(X) and w1(X) conflict, which means that we cannot move r2(X) down to get the
equivalent serial schedule T1 , T2
w1(X) and w2(X) conflict, we cannot move w1(X) down to get the equivalent serial
schedule T2 , T1 .

37
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Testing for Serializability of a Schedule
Algorithm 20.1 can be used to test a schedule for conflict serializability. The algorithm looks
at only the read_item and write_item operations in a schedule to construct a precedence
graph (or serialization graph), which is a directed graph

G = (N, E) that consists of a set of nodes N = {T1 , T2 , … , Tn } and a set of directed edges E
= {e1 , e2 , … , en }. There is one node in the graph for each transaction Ti in the schedule.

Each edge ei in the graph is of the form (Tj → T k ), 1 ≤ j ≤ n, 1 ≤ k ≤ n, where Tj is the

starting node of ei and Tk is the ending node of ei.

Such an edge from node Tj to node Tk is created by the algorithm if a pair of conflicting
operations exist in Tj and Tk and the conflicting operation in Tj appears in the schedule
before the conflicting operation in Tk.

38
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 The precedence graph is constructed based on the Algorithm 20.1.
If there is a cycle in the precedence graph, schedule S is not (conflict) serializable;
if there is no cycle, S is serializable.

39
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Test for conflict serializability

40
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 View Equivalence and View Serializability
View equivalence: Less restrictive definition of equivalence of schedules is called view
equivalence.

View serializability: Two schedules S and S’ are said to be view equivalent if the
following three conditions hold:

41
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
The definitions of conflict serializability and view serializability are similar if a condition
known as the constrained write assumption (or no blind writes) holds on all transactions in
the schedule.

A blind write is a write operation in a transaction T on an item X that is not dependent on the
value of X, so it is not preceded by a read of X in the transaction T.

The definition of view serializability is less restrictive than that of conflict serializability under
the unconstrained write assumption, where the value written by an operation wi(X) in Ti can
be independent of its old value from the database. This is possible when blind writes are
allowed, and it is illustrated by the following schedule Sg of three transactions
T1: r1(X); w1(X); T2: w2(X); T3: w3(X):
Sg: r1(X); w2(X); w1(X); w3(X); c1; c2; c3;

In Sg the operations w2(X) and w3(X) are blind writes, since T2 and T3 do not read the value
of X. The schedule Sg is view serializable, since it is view equivalent to the serial schedule T1,
T2, T3. However, Sg is not conflict serializable, since it is not conflict equivalent to any serial
schedule.

42
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Other Types of Equivalence of Schedules
Serializability of schedules is sometimes considered to be too restrictive as a condition for
ensuring the correctness of concurrent executions. Some applications can produce
schedules that are correct by satisfying conditions less stringent than either conflict
serializability or view serializability.

T1: r1(X); X := X−10; w1(X); r1(Y); Y := Y + 10; w1(Y);

T2: r2(Y); Y := Y−20; w2(Y); r2(X); X := X + 20; w2(X);

Sh: r1(X); w1(X); r2(Y); w2(Y); r1(Y); w1(Y); r2(X); w2(X);

With the additional knowledge, or semantics, that the operations between each ri(I) and
wi(I) are commutative, we know that the order of executing the sequences consisting of
(read, update, write) is not important as long as each (read, update, write) sequence by a
particular transaction Ti on a particular item I is not interrupted by conflicting operations.

43
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 Transaction Support in SQL
A transaction is a logical unit of work and is guaranteed to be atomic. A single SQL
statement is always considered to be atomic—either it completes execution without an error
or it fails and leaves the database unchanged.

With SQL, there is no explicit Begin Transaction statement. Transaction initiation is done
implicitly when particular SQL statements are encountered. But every transaction must have
an explicit end statement, which is either a COMMIT or a ROLLBACK.

Transaction characteristics are specified by a SET TRANSACTION statement in SQL. The

characteristics are the access mode, the diagnostic area size, and the isolation level.

The access mode can be specified as READ ONLY or READ WRITE. The default is
READ WRITE, unless the isolation level of READ UNCOMMITTED is specified, in which
case READ ONLY is assumed. A mode, of READ WRITE allows select, update, insert,
delete, and create commands to be executed. A mode of READ ONLY is for data retrieval.

44
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 The diagnostic area size option, DIAGNOSTIC SIZE n, specifies an integer value n,
which indicates the number of conditions that can be held simultaneously in the
diagnostic area. These conditions supply feedback information (errors or exceptions) to the
user or program on the n most recently executed SQL statement.

The isolation level option is specified using the statement ISOLATION LEVEL
<isolation>, where the value for <isolation> can be READ UNCOMMITTED, READ
COMMITTED, REPEATABLE READ, or SERIALIZABLE. The default isolation level is
SERIALIZABLE, although some systems use READ COMMITTED as their default. The
use of the term SERIALIZABLE is based on not allowing violations that cause dirty read,
unrepeatable read, and phantoms.

45
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 If a transaction executes at a lower isolation level than SERIALIZABLE, then one or more
of the following three violations may occur:

1. Dirty read: A transaction Ti may read the update of a transaction T2, which has not
yet committed. If T2 fails and is aborted, then T1 would have read a value that does
not exist and is incorrect.
2. Nonrepeatable read: A transaction Ti may read a given value from a table. If another
transaction T2 later updates that value and T1 reads that value again, Ti will see a
different value.
3. Phantoms: A transaction T1 may read a set of rows from a table based on some
condition specified in the SQL WHERE-clause. Now suppose that a transaction T2
inserts a new row r that also satisfies the WHERE-clause condition used in T1 , into
the table used by T1 . The record r is called a phantom that a violation is possible and
an entry of No indicates that it is not possible.

46
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 47
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT
 THANK YOU

48
© Archana Bhat, Asst. Prof., Dept. of AI & ML, BMSIT