TRANSACTION PROCESSING
▪ Transaction: A collection of operations that form a single logical
unit of work is called a transaction.
▪ The operations that make up a transaction typically consist of
requests to access existing data, modify existing data, add new data,
or any combination of these requests.
▪ The statements of a transaction are enclosed within the begin
transaction and end transaction statements.
▪ For successful completion of a transaction and database changes to
be permanent, the transaction must be completed in its entirety.
▪ That is, each step (or operation) in the transaction must succeed for
the transaction to be successful. If any part of the transaction fails,
then the entire transaction fails.
1
TRANSACTION PROCESSING
▪ Example: Paying the utility bill from the customer’s bank account.
▪ It involves several operations such as debiting the bill amount from
customer’s account and crediting the amount to the utility provider’s
account.
▪ All the operations of fund transfer from customer’s account to utility
provider’s account must succeed or fail as a group.
▪ It would be unacceptable if the customer’s account is debited but the
utility provider’s account is not credited.
▪ Therefore, in this topic we will cover the basic concepts of transactions
that include the desirable properties and various states of a transaction.
▪ We will discuss how concurrent execution of multiple transactions may
lead to several anomalies.
▪ We will also discuss the various types of transaction schedules including
serial, serializable, recoverable, and cascade less schedules.
2
DESIRABLE PROPERTIES OF A TRANSACTION
▪ To ensure the integrity of the data, the database system must
maintain some desirable properties of the transaction.
▪ These properties are known as ACID properties, the acronym derived
from the first letter of the terms a tomicity, c onsistency, i solation,
and d urability.
▪ Atomicity implies that either all of the operations that make up a
transaction should execute or none of them should occur. It is the
responsibility of the transaction management component of a DBMS
to ensure atomicity.
▪ Consistency implies that if all the operations of a transaction are
executed completely, the database is transformed from one consistent
state to another. It is the responsibility of the application
programmers who code the transactions to ensure consistency of the
database.
3
DESIRABLE PROPERTIES OF A TRANSACTION
▪ Isolation implies that each transaction appears to run in isolation
with other concurrently running transactions. That is, the execution
of a transaction should not be interfered by any other concurrently
running transaction. It is the responsibility of the concurrency control
component (will discussed later in detail) of the database system to
allow concurrent execution of transactions without any interference
from each.
▪ Durability (also known as permanence) implies that once a
transaction is completed successfully, the changes made by the
transaction persist in the database, even if the system fails. The
durability property is ensured by the recovery management
component of the database system.
4
Example
▪ Consider a transaction T1 that transfers $100 from account A to
account B. Let the initial values of account A be $2000 and account
B is $1500. The sum of the values of account A and B is $3500
before the execution of transaction T1. Since T1 is a fund
transferring transaction, the sum of the values of account A and B
should be $3500 even after its execution.
T1: read(A); If transaction T1 is executed, either $100 should be
A:=A–100; transferred from account A to B or neither of the
write(A); accounts should be affected. If T1 fails after debiting
read(B); $100 from account A, but before crediting $100 to
B:= B+100; account B, the effects of this failed transaction on
write(B); account A must be undone. This is the atomicity
property of transaction T1.
5
Example
▪ The execution of transaction T1 should also preserve the consistency
of the database, that is, the sum of the values of account A and B
should be $3500 even after the execution of T1.
▪ Now, let us consider the isolation property of T1. Suppose that
during the execution of transaction T1 when $100 is debited from
account A and not yet credited to account B, another concurrently
running transaction, say T2 reads the values of account A and B.
Since T1 has not yet completed, T2 will read inconsistent values. The
isolation property ensures that the effects of the transaction T1 are
not visible to other transaction T2 until T1 is completed.
▪ If the transaction T1 is successfully completed and the user who
initiated the transaction T1 has been notified about successful
transfer of funds, then the data regarding the transfer of funds should
not be lost even if the system fails. This is the durability property of
6 T1.
STATES OF A TRANSACTION
▪ Whenever a transaction is submitted to a DBMS for execution, either
it executes successfully or fails due to some reasons. During its
execution, a transaction passes through various states that are active,
partially committed, committed, failed, and aborted.
7
Cont…
▪ A transaction enters into the active state with its commencement. At
this point, the system marks BEGIN_TRANSACTION operation to
specify the beginning of the transaction execution.
▪ During its execution, the transaction stays in the active state and
executes several READ and WRITE operations on the database.
▪ The READ operation transfers a data item from the database to a
local buffer of the transaction that has executed the read operation.
▪ The WRITE operation transfers the data item from the local buffer of
the transaction back to the database.
▪ Once the transaction executes its final operation, the system marks
END_TRANSACTION operation to specify the end of the
transaction execution.
▪ At this point, the transaction enters into the Partially Committed
8
state.
Cont…
▪ The actual output at this point may still be residing in the main
memory and, thus, any kind of hardware failure might prevent its
successful completion. In such a case, the transaction may have to be
aborted.
▪ Before actually updating the database on the disk, the system first
writes the details of updates performed by the transaction in the log
file.
▪ The log file is then written to the disk so that, even in case of failure,
the system can re-construct the updates performed by the transaction
when the system restarts after the failure.
▪ When this information is successfully written out in the log file, the
system marks COMMIT_TRANSACTION operation to indicate the
successful end of the transaction. Now, the transaction is said to be
committed, and all its changes must be reflected permanently in the
9
database.
Cont…
▪ If the transaction is aborted during its active state or the system fails
to write the changes in the log file, the transaction enters the failed
state.
▪ The failed transaction must be rolled back to undo its effects on the
database to maintain the consistency of the database.
▪ When the transaction leaves the system, it enters into the terminated
state. At this point, the transaction information maintained in the log
file during its execution is removed.
10
Cont…
▪ There are some situations when a transaction needs to perform write
operations on a terminal or a printer. These writes are known as
observable external writes.
▪ Note that once a transaction has been committed, its effects cannot
be undone by aborting it. The only way to undo the effects of a
committed transaction is to execute a compensating transaction.
▪ For example, a transaction that has added $100 in an account can be
reversed back by executing a compensating transaction that would
subtract $100 from the account.
11
CONCURRENT EXECUTION OF TRANSACTIONS
▪ The transaction-processing system allows concurrent execution of
multiple transactions to improve the system performance.
▪ In concurrent execution, the database management system controls
the execution of two or more transactions in parallel; however,
allows only one operation of any transaction to occur at any given
time within the system. This is also known as interleaved execution
of multiple transactions.
▪ The database system allows concurrent execution of transactions due
to two reasons:
1) CPU and I/O Working Together:
When a transaction is reading or writing data using I/O devices, the
CPU may not be used at that moment.
While one transaction is busy with I/O, the CPU can work on another
transaction. This happens because the CPU and I/O devices can work
12
at the same time (in parallel).
CONCURRENT EXECUTION OF TRANSACTIONS
By overlapping CPU and I/O work:
Both CPU and I/O stay busy.
Idle time for CPU and disks is reduced.
More transactions are completed in less time (higher throughput).
2) Interleaved Execution of Short and Long Transactions:
If a short transaction waits for a long one to finish (serial execution),
it takes a long time to complete. This causes unpredictable delays
and makes the system slower.
But if short and long transactions run at the same time
(concurrently), the short one can finish quickly. This reduces overall
waiting time and improves the system’s average response time.
Interleaved Execution means the system executes a few steps of one
transaction, then a few steps of another, and so on.
13
Anomalies Due to Interleaved Execution
Note: Despite the correctness of each individual transaction,
undesirable interleaving of multiple transactions may lead to database
inconsistency.
If the transactions are interleaved in an undesirable manner, it may
lead to several anomalies such as:
i) lost update
ii) dirty read
iii) unrepeatable read.
14
Lost update
Consider two transactions T1 and T2, where Suppose that the operations of T1
T1 transfers $100 from account A to account and T2 are interleaved in such a
B, and T2 adds two percent interest to account way that T2 reads the value of
A. Suppose that the initial values of account account A before T1 updates its
A and B are $2000 and $1500, respectively. value in the database. Now, when
Then, after the serial execution of T2 updates the value of account A
transactions T1 and T2 (T1 followed by T2), in the database, the value of
the value of account A should be $1938 and account A updated by the
that of account B should be $1600. transaction T1 is overwritten and
hence, is lost. This is known as
lost update problem.
The value of account A at the end of both
the transactions is $2040 instead of $1938
which leads to data inconsistency.
The interleaved execution of transactions
T1 and T2 that leads to lost update problem.
15
Dirty read
The second problem occurs when a transaction fails after updating a data item, and
before this data item is changed back to its original value, another transaction reads
this updated value.
For example, assume that T1 fails after debiting
$100 from account A, but before crediting this
amount to account B. This will leave the
database in an inconsistent state. The value of
account A is now $1900, which must be
changed back to original one, that is, $2000.
However, before the transaction T1 is rolled
back, let another transaction T2 reads the
incorrect value of account A. This incorrect
value of account A that is read by transaction
T2 is called dirty data, and the problem is The interleaved execution of
called dirty read problem. transactions T1 and T2 that
leads to dirty read problem.
16
Unrepeatable read
The third problem occurs when a transaction tries to read the value of the data item
twice, and another transaction updates the same data item in between the two read
operations of the first transaction. As a result, the first transaction reads varied values
of same data item during its execution. This is known as unrepeatable read.
For example, consider a transaction T3 that
reads the value of account A. At this point,
let another transaction T4 updates the value
of account A. Now if T3 again tries to read
the value of account A, it will get a different
value. As a result, the transaction T3
receives different values for two reads of
account A. This different values of A that is
read by Transaction T3 is called The interleaved schedule of
unrepeatable read. and the problem is transactions T3 and T4 that leads
called unrepeatable read problem. to a problem of unrepeatable
read.
17
Important Note:
The three anomalies, namely, lost update, dirty read, and unrepeatable read can also
be described in terms of when the actions of two transactions, say T1 and T2, conflict
with each other. In this case, the lost update problem is known as write-write (WW)
conflict, the dirty read problem is known as write-read (WR) conflict, and
unrepeatable problem is known as read-write (RW) conflict.
18
TRANSACTION SCHEDULES
• A list of operations (such as reading, writing, aborting or committing) from a set
of transactions is known as a schedule (or history).
• A schedule should comprise all the instructions of the participating transactions
and also preserve the order in which the instructions appear in each individual
transaction.
Consider two transactions T1 and T5,
where T1 transfers $100 from account A to
account B and T5 transfers $50 from
account B to account C. Here, account C is
another account of the shopkeeper.
Suppose that the values of account A, B,
and C are $2000, $1500, and $500,
respectively. The sum A + B + C is $4000.
Also suppose that the two transactions are
executed one after the other in the order
T1 followed by T5. This sequence of execution of the
19
transactions is called a serial schedule.
TRANSACTION SCHEDULES
• Similarly, if the transaction T1 is executed after the execution of transaction T5,
then also the sum A + B + C is preserved. The serial schedule of transactions T1
and T5 in the order T5 followed by T1
A schedule can also be described with the help
of shorthand notation that uses the symbols r,
w, c, and a, for the operations read, write,
commit, and abort, respectively.
For example: Schedule 1 of Figure, which may
be named S1, can be expressed as:
S1: r5(B); w5(B); r5(C); w5(C); r1(A); w1(A);
r1(B); w1(B);
Each transaction in a serial schedule is executed independently without any
interference from the operations of other transactions. As long as every transaction is
executed from beginning to end without any interference from other transactions, it
gives a correct end result on the database. Therefore, every serial schedule is
considered to be correct.
20
SERIALIZABLE SCHEDULES
• In a multi-user database system, several transactions are executed concurrently
for efficient use of system resources.
• When two transactions are executed concurrently, the operating system may
execute one transaction for some time, then perform a context switch and
execute the second transaction for some time, and then switch back to the first
transaction, and so on.
• Thus, when multiple transactions are executed concurrently, the CPU time is
shared among all the transactions. The schedule resulted from this type of
interleaving of operations from various transactions is known as non-serial
schedule.
• If the operating system is given the entire responsibility of executing the
transactions concurrently, then it can even generate the schedules that can leave
the database in inconsistent state.
• Therefore, it is the responsibility of concurrency-control component of database
system to ensure that only those schedules should be executed that will leave
the database in a consistent state.
21
SERIALIZABLE SCHEDULES
• The consistency of the database under concurrent execution can be ensured by
interleaving the operations of transactions in such a way that the concurrent final
output is same as that of some serial schedule of those transactions. Such a
schedule is referred to as serializable schedule.
A concurrent schedule resulting in an A concurrent schedule resulting in
inconsistent state of database consistent state of the database
The final values of accounts A, B, and C The final values of accounts A, B, and C are
are $1900, $1600, and $550. Thus, the $1900, $1550, and $550. Thus, the sum A + B +
sum A + B + C is not preserved C is preserved and hence, it is a serializable
schedule.
22
CONCURRENCY CONTROL TECHNIQUES
▪ When multiple transactions execute at the same time, problems like
lost updates, dirty reads, and inconsistent data can occur. To
prevent these, the DBMS uses concurrency control techniques.
▪ Concurrency control techniques are required to control the
interaction among concurrent transactions. These techniques ensure
that the concurrent transactions maintain the integrity of a database
by avoiding the interference among them.
▪ Concurrency control techniques ensure serializability order in the
schedule.
▪ Two major types of concurrency control techniques are: locking,
timestamp-based.
23
LOCKING
▪ Whenever a data item is being accessed by a transaction, it must not be
modified by any other transaction. In order to ensure this, a transaction
needs to acquire a lock on the required data items.
▪ A lock is a variable associated with each data item that indicates
whether a read or write operation can be applied to the data item. In
addition, it synchronizes the concurrent access of the data item.
▪ Acquiring the lock by modifying its value is called locking.
▪ It controls the concurrent access and manipulation of the locked data
item by other transactions and hence, maintains the consistency and
integrity of the database.
▪ Database systems mainly use two modes of locking, namely, exclusive
locks and shared locks.
24
Exclusive lock (X-Lock)
▪ An Exclusive Lock allows only one transaction to both read and
write a data item.
▪ When a transaction holds an exclusive lock, no other transaction can
place any lock (shared or exclusive) on that data.
▪ Prevents both reading and writing by other transactions.
▪ Used during write operations (INSERT, UPDATE, DELETE).
Example: Suppose Transaction T1 acquires an exclusive lock on a row
to update it. While T1 holds this lock: No other transaction can read or
modify that row. Other transactions must wait until T1 commits or rolls
back.
25
Shared Lock (S-Lock)
▪ A Shared Lock allows multiple transactions to read the same data at
the same time, but it prevents any transaction from writing
(modifying) the data while the shared lock is active.
▪ Many transactions can acquire a shared lock on the same data item
simultaneously.
▪ No transaction can modify the data until all shared locks are
released.
▪ Shared locks are typically used during read operations (SELECT
statements).
Example: Suppose Transaction T1 places a shared lock on a row to read
it. While T1 is reading: Transaction T2 can also place a shared lock and
read the same row. But Transaction T3 cannot place an exclusive lock
to update or delete the row until both T1 and T2 release their shared
locks.
26
Comparision Table
27
Implementation of Locking in Databases
• A lock is a control mechanism used to manage concurrent access to data
items in a database. It acts as a control block, containing information
about the type of lock (e.g., shared or exclusive) and identity the
transaction that holds the lock.
• The locking or unlocking of the data items is implemented by a
subsystem of the database system known as lock manager.
Functions of the Lock Manager:
i) Receives lock requests from transactions: Replies with Lock Grant
message → if the lock can be assigned and Rollback message → if a
deadlock is detected.
ii) Unlock requests: Sends an acknowledgement. May trigger lock grants
to other transactions waiting for the data item.
iii) Handling Waiting Transactions: When multiple transactions are
waiting for the same data item, the lock manager must decide the order
in which locks are granted following some priority technique,
Otherwise, it may result in starvation.
28
Starvation
• Starvation: a transaction waits indefinitely for a lock because other
requests keep jumping ahead.
Example Scenario: Starvation
Consider a data item Q:
1. Transaction Ti acquires a Shared Lock on Q.
2. Transaction Tj requests an Exclusive Lock on Q → must wait until Ti
releases its shared lock.
3. Meanwhile, Transaction Tk requests another Shared Lock on Q →
request is granted, because shared locks are compatible with other
shared locks.
4. More transactions (T1, T2, …) may keep requesting shared locks.
5. Result: Tj keeps waiting for an exclusive lock. Since new shared locks
keep being granted, Tj never gets the exclusive lock. This is starvation.
29
Starvation
• Preventing Starvation:
Use priority-based queuing: If Tj’s exclusive lock request arrives first, then
subsequent shared lock requests (like Tk’s) are queued behind Tj. This
ensures fairness and prevents indefinite waiting.
Key Points:
• Locking ensures data consistency in concurrent environments.
• The Lock Manager controls when locks are granted or released.
• Priority rules are crucial to avoid starvation of transactions, especially for
exclusive lock requests.
30
Lock Based Techniques
• A transaction does not release a lock on the data item as long as it uses
that data item. It may release the lock immediately after the final
accessing of the data item is done. However, releasing the data item
immediately is not always desirable. For example:
Consider transactions T1 and
T2, and data items Q and R
with the initial value of 500
units and 1000 units,
respectively. T1 wants to
deduct 200 units from the data
item R and add 200 units to the
data item Q. Whereas T2 wants
to add the values of Q and R.
If these transactions are executed serially, either The transactions T1 and T2 with
T1 followed by T2 or vice-versa, T2 will display
lock requests are given in
the sum 1500. Alternatively, T1 and T2 may be
31 executed concurrently. Figure.
Lock Based Techniques
This schedule shows the statements issued
by the transactions in the interleaved
manner. Note that the lock must be
granted after the transaction requests the
lock, but before the transaction executes
its next statement. The lock can be
granted anywhere in between this
interval; however, we are not interested in
the exact point of time where the lock is
granted. For simplicity, we assume that
the lock is granted immediately before the
execution of next statement by the
transaction.
The concurrent execution of the transactions results in displaying the sum 1300 units
instead of 1500. Observe that the database is in an inconsistent state since 200 units are
deducted from data item R but not added to Q. In addition, T2 is allowed to read the values
of Q and R before transaction T1 is complete. This is because the locks on the data items Q
32 and R are released as soon as possible.
Lock Based Techniques
The concurrent execution of the transactions results in displaying the sum 1300
units instead of 1500. Observe that the database is in an inconsistent state since
200 units are deducted from data item R but not added to Q. In addition, T2 is
allowed to read the values of Q and R before transaction T1 is complete. This is
because the locks on the data items Q and R are released as soon as possible.
Now, suppose that the unlock statements in Figure, are delayed to the end of the
transactions. Then, T1 unlocks Q and R only after the completion of its actions.
So, the database remains in consistent state.
However, sometimes delaying the lock until the end of transaction may lead to an
undesirable situation, called deadlock.
• Deadlock is a situation that occurs when all the transactions in a set of two or
more transactions are in a simultaneous wait state and each of them is waiting
for the release of a data item held by one of the other waiting transaction in the
set. None of the transactions can proceed until at least one of the waiting
transactions releases lock on the data item.
33
Example of Deadlock
• Observe that T3 is waiting for T4 to unlock Q, and T4 is waiting for T3 to
unlock R. Thus, a situation is arrived where these two transactions can no
longer continue with their normal execution. This situation is called
deadlock.
• Now, one of these transactions must be rolled back by the system so that the
data items locked by that transaction are released and become available to the
other transaction.
34
Observation
From this discussion, it is clear that if locking is not used or if data items are
unlocked too early, a database may become inconsistent. On the other hand, if the
locks on data items are not released until the end of transaction, deadlock may
occur.
Out of these two problems, deadlocks are more desirable, since they can be handled
by the database system but inconsistent state cannot be handled.
There is a need that all the transactions in a schedule must follow some set of
rules called locking technique. These rules indicate when a transaction may lock
or unlock any data item.
35
TWO-PHASE LOCKING (2PL) PROTOCOL)
• This is the most widely used lock-based protocol to ensure serializability.
It has two phase:
i) Growing Phase: Transaction may acquire locks but cannot release
any.
ii) Shrinking Phase: Once a lock is released, no new locks can be
obtained.
Deadlocks possible
36
LOCK CONVERSION
• In 2PL, locks can be upgraded or downgraded during proper phases.
Example
•T1 has S-lock(A) to read A.
•Later, it needs to update A → Upgrade to X-lock(A).
37
GRAPH-BASED LOCKING (PARTIAL ORDER LOCKING)
• A deadlock-free method that uses a hierarchical order among data items.
Concept
• Data items form a Directed Acyclic Graph (DAG).
• Transactions must request locks in order (root → leaf).
• Once a lock is released, the transaction cannot request a lock on a predecessor.
• T1 can lock A → then B or C.
• T2 cannot lock B first if A is already locked by T1.
• Deadlocks avoided but Requires predefined data order
38
DEADLOCK HANDLING
• A deadlock occurs when two or more transactions wait for each other’s
locks indefinitely.
Both are waiting → Deadlock!
Deadlock Prevention
• The system prevents deadlocks by following rules that avoid circular waiting.
1. Wait-Die Scheme (Non-preemptive): If an older transaction requests a lock held
by a younger one → it waits. If a younger one requests a lock held by an older → it
dies (rolls back).
39
DEADLOCK HANDLING
Deadlock Prevention
2. Wound-Wait Scheme (Preemptive): If an older transaction requests a lock held
by a younger → younger one rolls back. If younger requests from older → it waits.
3. Resource Ordering: Transactions request locks in a fixed order (like Graph-
Based Locking).
Deadlock Detection
• System allows deadlocks to occur but detects them using a Wait-For Graph
(WFG).
Each transaction = a node.
Edge T1 → T2 means T1 is waiting for T2.
Cycle in the graph → Deadlock exists.
Example:
T1 → T2 → T3 → T1. Cycle found → Deadlock detected.
Detection is automatic
40
DEADLOCK HANDLING
Deadlock Recovery
• Once a deadlock is detected, system recovers by rolling back one or more
transactions.
Methods:
• Abort victim: Choose transaction to rollback (based on priority, age, or cost).
• Restart transaction after some delay.
System continues normally after recovery.
41
TIMESTAMP-BASED TECHNIQUES
• Avoids locks by assigning each transaction a unique timestamp (TS) at start.
Rules:
Each data item X has:
• Read_TS(X) – largest TS of any transaction that read X
• Write_TS(X) – largest TS of any transaction that wrote X
Execution Rules:
1. Read Rule: If TS(T) < Write_TS(X) → transaction is rolled back (reading
outdated value).
2. Write Rule: If TS(T) < Read_TS(X) or TS(T) < Write_TS(X) → rollback
(violates order).
42
TIMESTAMP-BASED TECHNIQUES
No deadlocks
43