Advanced Database Concepts
UNIT-3
TRANSACTION MANAGEMENT
WHAT IS TRANSACTION?:
Collections of operations that form a single logical unit of work are called transactions. A database
system must ensure proper execution of transactions despite failures— either the entire transaction
executes, or none of it does. Furthermore, it must manage concurrent execution of transactions in a way
that avoids the introduction of inconsistency.
PROPERTIES OF TRANSACTION:
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 are.
• Consistency. Execution of a transaction in isolation (that is, with no other transaction executing
concurrently) preserves the consistency of the database.
• Isolation. Even though multiple transactions may execute concurrently, the system guarantees that, 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.
• 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; the acronym is
derived from the first letter of each of the four 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. For
the time being, we assume that the database permanently resides on disk, but that some portion of it is
temporarily residing in main memory. Transactions 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 the local buffer of the transaction that executed the
write back to the database.
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. Without the consistency requirement, money could be created or destroyed by the
transaction. 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
that prevents Ti from completing its execution successfully. Examples of such failures include power
failures, hardware failures, and software errors. 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
Unit-3 Page 1
Advanced Database Concepts
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.
Thus, because of the failure, the state of the system no longer reflects a real state of the world that the
database is supposed to capture. We term such a state an inconsistent state
Durability requirement — 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.
Isolation: Even if the consistency and atomicity properties are ensured for each transaction, if several
transactions are executed concurrently, their operations may interleave in some undesirable way, resulting
in an inconsistent state. A way to avoid the problem of concurrently executing transactions is to execute
transactions serially—that is, one after the other.
TRANSACTION STATE:
In the absence of failures, all transactions 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. 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. It is part of the responsibility of the recovery scheme to manage transaction aborts. A transaction
that completes its execution successfully is said to be committed. A committed transaction that has
performed updates transforms the database into a new consistent state, which must persist even if there is
a system failure.
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
Unit-3 Page 2
Advanced Database Concepts
The state diagram corresponding to a transaction appears in Figure 15.1. We say that a transaction
has committed only if it has entered the committed state. Similarly, we say that a transaction has aborted
only if it has entered the aborted state. A transaction is said to have terminated if has either committed or
aborted. A transaction starts in the active state. When it finishes its final statement, it enters the partially
committed state. At this point, the transaction has completed its execution, but it is still possible that it
may have to be aborted, since the actual output may still be temporarily residing in main memory, and
thus a hardware failure may preclude its successful completion. 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 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 then aborted state.
TRANSACTION MANAGEMENT WITH SQL:
The American National Standards Institute (ANSI) has defined standards that govern SQL database
transactions.
Transaction support is provided by two SQL statements: COMMIT and ROLLBACK. The ANSI
standards require that when a transaction sequence is initiated by a user or an application program, the
sequence must continue through all succeeding SQL statements until one of the following four events
occurs:
-A COMMIT statement is reached, in which case all changes are permanently recorded within the
database. The
COMMIT statement automatically ends the SQL transaction.
- A ROLLBACK statement is reached, in which case all changes are aborted and the database is rolled
back to its previous consistent state.
-The end of a program is successfully reached, in which case all changes are permanently recorded within
the database. This action is equivalent to COMMIT.
- The program is abnormally terminated, in which case the changes made in the database are aborted and
the database is rolled back to its previous consistent state. This action is equivalent to ROLLBACK.
CONCURRENT EXECUTIONS:
Transaction-processing systems usually allow multiple transactions to run concurrently. Allowing
multiple transactions to update data concurrently causes several complications with consistency of the
data. There are two good reasons for allowing concurrency:
•Improved throughput and resource utilization. A transaction consists of many steps. Some involve
I/O activity; others involve CPU activity. The CPU and the disks in a computer system can operate in
parallel. Therefore, I/O activity can be done in parallel with processing at the CPU. The parallelism of the
CPU and the I/O system can therefore be exploited to run multiple transactions in parallel. While a read
or write on behalf of one transaction is in progress on one disk, another transaction can be running in the
CPU, while another disk may be executing a read or write on behalf of a third transaction. All of this
increases the throughput of the system—that is, the number of transactions executed in a given amount
of time. Correspondingly, the processor and disk utilization also increase; in other words, the processor
and disk spend less time idle, or not performing any useful work.
Unit-3 Page 3
Advanced Database Concepts
• Reduced waiting time. There may be a mix of transactions running on a system, some short and some
long. If transactions run serially, a short transaction may have to wait for a preceding long transaction to
complete, which can lead to unpredictable delays in running a transaction. If the transactions are
operating on different parts of the database, it is better to let them run concurrently, sharing the CPU
cycles and disk accesses among them. Concurrent execution reduces the unpredictable delays in running
transactions. Moreover, it also reduces the average response time: the average time for a transaction to
be completed after it has been submitted.
Suppose the current values of accounts A and B are $1000 and $2000, respectively. Suppose that the two
transactions are executed concurrently. One possible schedule appears in Figure 15.5. After this execution
takes place, we arrive at the same state as the one in which the transactions are executed serially in the
order T1 followed by T2. The sum A + B is indeed preserved.
Not all concurrent executions result in a correct state. To illustrate, consider the schedule of Figure 15.6.
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. Indeed, the sum A + B is not preserved by the execution of the two
transactions.
CONCURRENCY CONTROL:
The coordination of the simultaneous execution of transactions in a multiuser database system is
known as concurrency control. The objective of concurrency control is to ensure the serializability of
transactions in a multiuser database environment. Concurrency control is important because the
simultaneous execution of transactions over a shared database can create several data integrity and
consistency problems. The three main problems are lost updates, uncommitted data, and inconsistent
retrievals.
LOCK MANAGEMENT:
One way to ensure serializability is to require that data items be accessed in a mutually exclusive manner;
that is, while one transaction is accessing a data item, no other transaction can modify that data item. The
most common method used to implement this requirement is to allow a transaction to access a data item
only if it is currently holding a lock on that item.
Locks:
Unit-3 Page 4
Advanced Database Concepts
A lock is a mechanism to control concurrent access to a data item. There are various modes in which a
data item may be locked. In this section, we restrict our attention to two modes:
1. Shared. If a transaction Ti has obtained a shared-mode lock (denoted by S) on item Q, then Ti can
read, but cannot write, Q.
2. Exclusive. If a transaction Ti has obtained an exclusive-mode lock (denoted by X) on item Q, then Ti
can both read and write Q.
Given a set of lock modes, we can define a compatibility function on them as follows. Let A and B
represent arbitrary lock modes. Suppose that a transaction Ti requests a lock of mode A on item Q on
which transaction Tj (Ti _= Tj ) currently holds a lock of mode B. If transaction Ti can be granted a lock
on Q immediately, in spite of the presence of the mode B lock, then we say mode A is compatible with
mode B. Such a function can be represented conveniently by a matrix. The compatibility relation between
the two modes of locking discussed in this section appears in the matrix comp of Figure 16.1. An element
comp(A, B) of the matrix has the value true if and only if mode A is compatible with mode B.
Note that shared mode is compatible with shared mode, but not with exclusive mode. At any time, several
shared-mode locks can be held simultaneously (by different transactions) on a particular data item. A
subsequent exclusive-mode lock request has to wait until the currently held shared-mode locks are
released.
A transaction requests a shared lock on data item Q by executing the lock-S(Q) instruction. Similarly, a
transaction requests an exclusive lock through the lock-X(Q) instruction. A transaction can unlock a data
item Q by the unlock(Q) instruction.
To access a data item, transaction Ti must first lock that item. If the data item is already locked by another
transaction in an incompatible mode, the concurrency control manager will not grant the lock until all
incompatible locks held by other transactions have been released. Thus, Ti is made to wait until all
incompatible locks held by other transactions have been released.
As an illustration, consider again the simplified banking system. Let A and B be two accounts that are
accessed by transactions T1 and T2. Transaction T1 transfers $50 from account B to account A (Figure
16.2). Transaction T2 displays the total amount of money in accounts A and B—that is, the sum A + B
(Figure 16.3).
Unit-3 Page 5
Advanced Database Concepts
We shall require that each transaction in the system follow a set of rules, called a locking protocol,
indicating when a transaction may lock and unlock each of the data items. Locking protocols restrict the
number of possible schedules.
SERIALIZABILITY:
Goal: Deal with concurrent schedules that are equivalent to some serial execution.
Basic Assumption – Each transaction preserves database consistency. 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. We discuss different forms of schedule equivalence; they lead to the
notions of conflict serializability and view serializability.
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, and at least one of 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
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.
To illustrate the concept of conflicting instructions, we consider schedule 3, in Figure 15.7. The write(A)
instruction of T1 conflicts with the read(A) instruction of T2. However, the write(A) instruction of T2 does
not conflict with the read(B) instruction of T1, because the two instructions access different data items.
The concept of conflict equivalence leads to the concept of conflict serializability. We say that a schedule
S is conflict serializable if it is conflict equivalent to a serial schedule. Thus, schedule 3 is conflict
serializable.
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. 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.
Unit-3 Page 6
Advanced Database Concepts
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 .
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.
Conditions 1 and 2 ensure that each transaction reads the same values in both schedules and, therefore,
performs the same computation. Condition 3, coupled with conditions 1 and 2, ensures that both
schedules result in the same final system state.
The concept of view equivalence leads to the concept of view serializability. We say that a schedule S is
view serializable if it is view equivalent to a serial schedule. As an illustration, suppose that we augment
schedule 7 with transaction T6, and obtain schedule 9 in Figure 15.12. Schedule 9 is view serializable.
Indeed, it is view equivalent to the serial schedule <T3, T4, T6>, since the one read(Q) instruction reads
the initial value of Q in both schedules, and T6 performs the final write of Q in both schedules.
Every conflict-serializable schedule is also view serializable, but there are view serializable schedules that
are not conflict serializable. Indeed, schedule 9 is not conflict serializable, since every pair of consecutive
instructions conflicts, and, thus, no swapping of instructions is possible.
Observe that, in schedule 9, transactions T4 and T6 perform 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.
TWO-PHASE LOCKING TO ENSURE SERIALIZABILITY:
Two-phase locking defines how transactions acquire and relinquish locks. Two-phase locking guarantees
serializability, but it does not prevent deadlocks. The two phases are:
1. A growing phase, in which a transaction acquires all required locks without unlocking any data.
Once all locks have been acquired, the transaction is in its locked point.
2. A shrinking phase, in which a transaction releases all locks and cannot obtain any new lock.
Unit-3 Page 7
Advanced Database Concepts
The two-phase locking protocol is governed by the following rules:
_ Two transactions cannot have conflicting locks.
_ No unlock operation can precede a lock operation in the same transaction.
_ No data are affected until all locks are obtained—that is, until the transaction is in its locked point.
Figure 10.7 depicts the two-phase locking protocol.
In this example, the transaction acquires all of the locks it needs until it reaches its locked point. (In this
example, the transaction requires two locks.) When the locked point is reached, the data are modified to
conform to the transaction requirements. Finally, the transaction is completed as it releases all of the locks
it acquired in the first phase.
Two-phase locking increases the transaction processing cost and might cause additional undesirable
effects. One undesirable effect is the possibility of creating deadlocks.
Deadlocks:
A deadlock occurs when two transactions wait indefinitely for each other to unlock data. For example, a
deadlock occurs when two transactions, T1 and T2, exist in the following mode:
T1 = access data items X and Y
T2 = access data items Y and X
If T1 has not unlocked data item Y, T2 cannot begin; if T2 has not unlocked data item X, T1 cannot
continue. Consequently, T1 and T2 each wait for the other to unlock the required data item. Such a
deadlock is also known as a deadly embrace.
CONCURRENCY CONTROL WITH TIME STAMPING METHODS:
The time stamping approach to scheduling concurrent transactions assigns a global, unique time
stamp to each transaction. The time stamp value produces an explicit order in which transactions are
submitted to the DBMS.
Time stamps must have two properties: uniqueness and monotonicity. Uniqueness ensures that
no equal time stamp values can exist, and monotonicity1 ensures that time stamp values always increase.
All database operations (READ and WRITE) within the same transaction must have the same time stamp.
The DBMS executes conflicting operations in time stamp order, thereby ensuring serializability of the
Unit-3 Page 8
Advanced Database Concepts
transactions. If two transactions conflict, one is stopped, rolled back, rescheduled, and assigned a new
time stamp value.
The disadvantage of the time stamping approach is that each value stored in the database requires two
additional time stamp fields: one for the last time the field was read and one for the last update. Time
stamping thus increases memory needs and the database’s processing overhead. Time stamping demands
a lot of system resources because many transactions might have to be stopped, rescheduled, and
restamped.
Wait/Die and Wound/Wait Schemes:
You have learned that time stamping methods are used to manage concurrent transaction execution. In
this section, you will learn about two schemes used to decide which transaction is rolled back and which
continues executing: the wait/die scheme and the wound/wait scheme.2 An example illustrates the
difference. Assume that you have two conflicting transactions: T1 and T2, each with a unique time stamp.
Suppose T1 has a time stamp of 11548789 and
T2 has a time stamp of 19562545. You can deduce from the time stamps that T1 is the older transaction
(the lower time stamp value) and T2 is the newer transaction. Given that scenario, the four possible
outcomes are shown in Table 10.14.
Using the wait/die scheme:
_-If the transaction requesting the lock is the older of the two transactions, it will wait until the other
transaction is completed and the locks are released.
- If the transaction requesting the lock is the younger of the two transactions, it will die (roll back) and is
rescheduled using the same time stamp.
In short, in the wait/die scheme, the older transaction waits for the younger to complete and release its
locks.
In the wound/wait scheme:
-If the transaction requesting the lock is the older of the two transactions, it will preempt (wound) the
younger transaction (by rolling it back). T1 preempts T2 when T1 rolls back T2. The younger, preempted
transaction is rescheduled using the same time stamp.
_-If the transaction requesting the lock is the younger of the two transactions, it will wait until the other
transaction is completed and the locks are released.
In short, in the wound/wait scheme, the older transaction rolls back the younger transaction and
reschedules it.
Unit-3 Page 9
Advanced Database Concepts
In both schemes, one of the transactions waits for the other transaction to finish and release the locks.
However, in many cases, a transaction requests multiple locks. How long does a transaction have to wait
for each lock request? Obviously, that scenario can cause some transactions to wait indefinitely, causing a
deadlock. To prevent that type of deadlock, each lock request has an associated time-out value. If the lock
is not granted before the time-out expires, the transaction is rolled back.
CONCURRENCY CONTROL WITH VALIDATION-BASED PROTOCOLS:
It is used for ensuring serialiazability of a database.
1. Finish(Ti) < Start(Tj ). Since Ti completes its execution before Tj started, the serializability order is
indeed maintained.
2. The set of data items written by Ti does not intersect with the set of data items read by Tj, and Ti
completes its write phase before Tj starts its validation phase (Start(Tj ) < Finish(Ti) < Validation(Tj )).
Unit-3 Page 10
Advanced Database Concepts
This condition ensures that the writes of Ti and Tj do not overlap. Since the writes of Ti do not affect the
read of Tj , and since Tj cannot affect the read of Ti, the serializability order is indeed maintained.
ACCESSING DATABASE FROM A PROGRAMMING LANGUAGE:
Unit-3 Page 11
Advanced Database Concepts
Unit-3 Page 12
Advanced Database Concepts
Example: Creation of table using Python programming language
Unit-3 Page 13