BCA-4

BCA-22-403: Database Management System

Dr. Aditya Kumar Gupta
Professor

UNIT-IV
 Transaction Processing

“Transaction of information in databases is similar to transaction of

money in banks. So it requires a much efforts to keep track of flow of
information. Any failure to keep record of this may cause of big pitfalls
and error, for both banking system as well as in information system.”

A DBMS is called multi-user if many user many user use the system
and, hence access database concurrently. On the other hand in
single-user if at most one user can use a system at a time. The
model of a database is used to explain a transaction-processing
concept is much simplified. A database is basically represented as a
collection of named data items. The size of the data is called
granularity, and it can be field of some record in the database, or it
may be large unit such as record or even whole disk. One

A transaction is a logical unit of database processing that includes

one or more database access operation; these may include insertion,
deletion, modification, or retrieval operations. The database
operations that form a transaction can either be embedded within
an application program or they can be specified via a high-level
language such as SQL. The transaction consists of the data, we
require that the transaction executed between the begin transaction
and end transaction.
A database system must ensure proper execution of
transaction despite failures-either the entire transaction executes,
or none of it execute well. It must be manage concurrent execution
of transaction in a way that avoids the introduction of inconsistency.
ACID TEST

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

maintain the following properties of the transactions.

 Atomicity: Either all operations of the transaction are

reflected properly in the database, or none of them reflected.

 Consistency: Execution of a transaction in isolation (that is,

with no other transaction executing concurrently) preserves
the consistency of the database.

 Isolation: Even through multiple transactions may execute

concurrently, the system guarantees that, for 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
transaction executing concurrently in the system.

 Durability: After a transaction completes successfully, the

changes it has made to the database persist, even if there are
system failures.

These properties are also called as AICD properties( On the basis

of first latter of each property.)Some access operation that a
transaction can include is given as follows:
 1. read_item(X): Reads a database item named X into a
program variable. Here X also denotes program variable.
Executing a read_item(X) command includes the following
steps:

 Find the address of the disk block that contain item X.

 Copy that disk block into a buffer in main memory.
 Copy item X from the buffer to the program variable named X.

1. write_item (X): Writes the value of program variable X into

the database item named X.

Executing a write_item (X) command includes following steps:

 Find he address of the disk block that contains item X.
 Copy that disk block into a buffer in main memory.
 Copy item X from the program variable named X into its
correct location in the buffer.
 Store the update block from the buffer block to disk.

A transaction includes read_item and write_item operation to access

and update the database. The read-set of a transaction is the set of
all items that the transaction reads, and the write-set is the set of all
items that the transaction writes.
T1 T2
read_item (x) read_item (x)
X:= X-N; X:= X-N;
write_item (X); write_item (X);
read_item (Y);
Y:=Y+N;
Write_item (Y);
1. Concurrency Control

Concurrency control is concerned with database access commands

in a transaction. Transaction submitted by various users may
execute concurrently and may access and updates the same
database items. Uncontrolled concurrency may lead the problem of
inconsistent database. There are following problems that must be
controlled via controlling concurrency.

The Lost Update Problem

This problem occurs when two transactions that access the same
database items have their operations interleaved in a way that
makes value of some database item incorrect. Suppose that
transaction T1 and T2 submitted at approximately the same time,
and suppose that their operations are interleaved then the final
value of item X is incorrect, because T2 reads the value of X before T1
changes it in the database, and hence the update value resulting
from T1 is lost.

T1 T2

read_item(X)
X:= X-N; read_item (X);
X:=X+M;
write_item(X);
read_item(Y);
write_item(X);
Time
Item X has an incorrect value because its
Y=Y+N; update by T1 is “lost” (overwritten)
write_item(Y);
 T1 T2

read_item(X)
X:= X-N;

read_item (X);
X:=X+M;
write_item(X);
Time
read_item(Y);

The Temporary Update Problem/ Dirty Read Problem

This problem occurs when one transaction updates a database item

and then the transaction fails or some reason. The update item is
accessed by another transaction before it is changed back to its
original value.

T1 T2

sum:=0;
read_item(X)
read_item (X);
X:=X-M;
write_item(X);

T3 reads X after N is subtracted

read_item(Y); and reads Y before N is added; a
sum:=sum+ X; wrong is result (off by N)
write_item(X);
sum:=sum+ Y:

read_item (Y);
X:=X-M;
write_item(Y);
The Above Figure shows an example where T1 updates item X and
then fails before competition, so the system must change X back to
its original value. Before it can do so, however, transaction T2 reads
the “temporary” value of X, which will not be recorded permanently
in the database because it has been created by a transaction that has
not been done yet; this problem is known as dirty read problem.

Transaction State: In the absence of failures, all transaction

complete successfully. However, as we noted earlier, a transaction
may not always complete its execution successfully. Such a
transaction is termed aborted. If we are to ensure the atomicity
property, an aborted transaction must have no effect on the state of
the database. A transaction that completes its execution successfully
is said to be committed. A committed transaction that has
committed, we cannot undo its effects by aborting it. The only way
to undo the effects of a committed transaction is to execute a
compensating 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.
Committed: After successful completion of transaction itself. We
can say that a transaction has committed only if it has entered the
committed only if it has entered into committed state.
Failed: After the discovery that normal execution has been rolled
back and the database have been restored to its state prior to start
of the transaction.
 Partially Committed
Committed

Active

Failed Aborted

A transaction state in the active state, when it finishes its final

statement, it enters the partially committed state.

The database system then writes out enough information to disk

that, even in the event of a failure, the updates performed by the
transaction can be re-created when the system restarts after the
failure. When the last of this information is written out, the
transaction enters the committed state. A enters the failed state
after the system determines that the transaction can no longer
proceed with its normal execution. Such a transaction must be rolled
back. Then, it enters the aborted state. At this point, the system has
two options:
Restart: It can restart the transaction, but only if the transaction
was aborted as a result of some hardware or software error that
was not created through the internal logic of the transaction. A
restarted transaction is considered to be a new transaction.

Kill: It can kill transaction. It usually does so because of some

internal logical error that can be corrected only by rewriting the
application program, or because the input was bad, or because the
desired data were not found in the database.

System Failure
The transaction is said to have been committed at the point where
the updated db pointer is written to disk. If the transaction fails at
any time before db-pointer is updated, the old content of the
database re not affected. We can abort the transaction by just
deleting the new copy of database. Once the transaction has been
committed, all the updates that it performed are in the database
pointed to by db pointer. Thus, either all updates of the transaction
are reflected, or none of the effects are reflected regardless of
transaction failure.

Review Questions
1. What is mean by the concurrent execution of database
transaction in multi-user system?
2. Draw a state diagram, and discus the typical state transaction
goes through during execution.
3. Define the term system failure and recoverability.
 Database Recovery

The main goal of database recovery is to ensure the atomicity

property of a transaction. If a transaction fails before completing its
execution, the recovery mechanism has to make sure that the
transaction has no lasting effects on the database. Recovery from
transaction failures usually means that the database is recovered to
the most recent consistent state just before the time of failure. To do
this, the system must keep information about the changes that were
applied to data items by the various transactions.

If the database is physically damaged, such as a disk crash, the

recovery method stores a past copy of the database. Recovery from
non-catastrophic transaction failure can be classified into two types

 If there is extensive damage to a vide portion of the database

due to disaster failure, such as disk crash, the recovery method
restores a past copy of the database that was backed up to
archival storage and reconstructs a more current state by
reapplying or redoing the operation of committed transaction
from the backed up log, up to the time failure.

 When the database is not physically damaged but has become

inconsistent due to non-catastrophic failures. The strategy is
to reveres any changes that caused the inconsistency by
undoing some operations. It may also be necessary to redo
some operations in order to restore a consistent state of the
database. In this case we need log file to keep record on
transaction. There is no need of archival copy of database.
Classification of Transaction Failures
There are following three reason for system crash

1. Transaction Failure
 Logical Error
Transaction can no longer continue with its normal executing
due to some internal condition such as bad input, data not
found, overflow or recourse limit exceeded.
 Physical Error
The system has entered an undesirable state such as deadlock.

2. System Crash
There is a hardware manufacture problem or a bug in the database
software or operating system that causes the loss of the content of
volatile storage and brings the transaction processing to a halt. The
content of the non-volatile storage remains intact and is not
corrupted.

3. Disk Failure
A disk block loses its content as a result of either a head crash or
failure during a data transfer operation.
Recovery Techniques: Conceptually, there are two main
techniques for recovery from non-catastrophic transaction failures:

Late Update or Deferred Update

Deferred Update does not physically update database on disk until
after a transaction reaches its commit point, then the updates are
recorded in the database. Before reaching commit, all transaction
updates are recorded in the local transaction workspace or buffers.
During commit, the updates are first recorded persistently in the log
and then written to the database. If a transaction fails before
reaching its commit point, it will not have changed the database in
any way, so UNDO is not needed.

Immediate Update
The database may be updated by some operations of a transaction
before the transaction reaches its commit point. However, these
operations are transaction before the transaction typically recorded
in the log on disk by force writing before they are applied to the
database, making recovery still possible. If a transaction fails after
recording some changes in the database but before reaching its
commit point, the effect of its operation on the database must be
undone. That is the transaction must be rolled back. However, these
operations are typically recorded in the log file.

Recovery Techniques Base on Deferred Update

The idea behind deferred update techniques is to defer or
postponed any actual updates to the database until the transaction
completes its execution successfully and reaches its commit point.

 During transaction execution, the updates are stored only in

the log and in the cache buffers. After the transaction reaches
 its commit point and the log is force-written to disk, the
updates are recorded in the databases.

 If a transaction fails before reaching its commit point, there is

no need to undo any operations.
 Some transactions do not affect the database e.g. generating
and printing messages or reports from information retrieved
from database.

A typical deferred update protocol as follows:

1. A database cannot change the database on disk until it reaches its

commit point.
2. A transaction does not reach its commit point until its updates
operations are recorded
in the log and the log is force-written to disk.

The deferred modification technique ensures transaction atomicity

by recording all database modification in the log but deferring the
execution of all write operations of a transaction until the
transaction partially commits.

Recovery Techniques Base on Immediate Update

The database can be update immediately, without ant need to wait
for the transaction to reach its commit point but an update
operation must be recorded in the log or disk before it is applied to
the database.
If the recovery technique ensures that all updates of a transaction
are recorded in the database on disk before the transaction
commits, there is never a need to REDO any operations of
committed transactions. This is called the UNDO/NO-REDO recovery
algorithm. On the other hand if the transaction is allowed to commit
before all its change are written to the database, we have the most
complex technique. When concurrent execution is permitted, the
recovery process depends on the protocols used for concurrency
control.

Shadow Paging
The recovery system does not require the use of a log in single user
environment. In a multi user environment, a log may be needed for
the concurrency control method. Shadow paging considers the
database is stored in number of fixed size pages or disk blocks for
recovery purpose.

This recovery scheme does not require the use of a log in a single-
user environment. In a multi-user environment, a log may be needed
for the concurrency control method. A directory with n entries is
constructed, where the ith entry point to ith database page on disk.
The directory is kept in main memory if it is not too large, and all
references, reads or writes to database pages on disk go through it.
The shadow directory is then saved on disk while the current
directory is used by transaction.
Transaction Rollback
A Transaction may have updated a data item more than once.
< Ti, A, 10, 20>
<Ti, A, 20, 30>
The scanning of the log terminates when the log records <Ti, start>
is found
The value 10 will be restored in the rollback.

Check Points
Use checkpoints to reduce the number of log records that are
scanned when the system recovers from a crash. Consider the
situation when transaction can execute concurrently. Several
transactions may have been active time of most recent checkpoint.
These checkpoints may be in form of <Checkpoint L>, where L is the
list of transaction active at the time of checkpoint.

Restart Recovery
Generally, system recovers from crash that constructs two lists undo
list and redo list. Initially these both list are empty. We can scan
backward, examining each record until the first <checkpoint>
record is found.
(i) For each record found of the form <Ti commit>, we add Ti
to redo-list.
(ii) For each record found of the form < Ti, start>, if Ti is not in
redo-list, then we add Ti to undo-list.
We can check the list L in the check point record. For each
transaction Ti in L, if Ti is not in redo-list then we add Ti to undo-list.
Buffer Management
Every log record is output to stable storage at the time it is created.
Typically output to stable storage is in units of blocks. The cost of
performing the output of a block to stable storage is sufficiently high
that is desirable to output multiple records at once. To do so, we
write log records to a log buffer in main memory, where they stay
temporarily until they are output to stable storage. Multiple log
records can be gathered in the log buffer and output to stable
storage in a single output operation.

Database Buffering
It is necessary to overwrite a block B1 in main memory when
another block B2 needs to be brought into memory. If B1 has been
modified, B1 must be output prior to the input of B2. If B1 has been
modified, B1 must be output prior to the input of B2.

The sequence of action by the system would be as follows

 Output log records to stable storage until all log records
pertaining to block B1has been output.
 Output block B1 to disk i.e. Non volatile storage.
 Input block B2 from disk to main memory.

Review Questions

1. Discuss the immediate update recovery in both single –user

and multi-user environments.
2. What are UNDO type and REDO type log entries?
3. Discuss the deferred update techniques of recovery.