0% found this document useful (0 votes)
10 views59 pagesDbms Mod5@Azdocuments - in
ee
Uploaded by
rahulshinde121012Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
10 views59 pagesDbms Mod5@Azdocuments - in
ee
Uploaded by
rahulshinde121012Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 59
Database Management System [18CS53]
Module 5
Chapter 1: Transaction Processing
5.0 Introduction
5.1 Obje
5.2 Introduction to Transaction Processing
5.2.1 Single-User versus Multiuser Systems
5.2.2 Transactions, Database Items, Read and Write Operations, and DBMS Buffers
5.2.3 Why Concurrency Control Is Needed
5.2.4 Why Recovery Is Needed
5.3 Transaction and System Concepts
5.3.1 Transaction States and Additional Operations
5.3.2 The System Log
5.3.3 Commit Point of a Transaction:
5.3.4 DBMS specific buffer Replacement policies
5.4 Desirable Properties of Transactions
5.5 Characterizing Schedules Based on Recoverability
5.6 Characterizing Schedules Based on Serializability
5.6.1 Testing conflict serializability of a Schedule S
5.7 Transaction Support in SQL
5.8 Introduction to Concurrency Control
5.9 Two-Phase Locking Techniques for Concurrency Control
5.9.1 Types of Locks and System Lock Tables
5.9.2 Guaranteeing Serializability by Two-Phase Locking
5.10 Variations of Two-Phase Locking
5.1] Dealing with Deadlock and Starvation
5.11 Deadlock Detection.
5.13 Concurrency Control Based on Timestamp Ordering
5.13.1 Timestamps
5.13.2 The Timestamp Ordering Algorithm
5.14Multiversion Concurrency Control Techniques
5.14.1 Multiversion Technique Based on Timestamp Ordering
5.14.2 Multiversion Two-Phase Locking Using Certify Locks
5.15 Validation (Optimistic) Concurrency Control Techniques
5.16 Granularity of Data Items and Multiple Granularity Locking
5.16.1 Granularity Level Considerations for Locking
5.16.2 Multiple Granularity Level Locking
5.17 Recovery Concepts
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
5.17.1 Recovery Outline and Categorization of Recovery Algorithms
5.17.2 Caching (Buffering) of Disk Blocks
5.17.3 Write-Ahead Logging, Steal/No-Steal, and Foree/No-Force
5.17.4 Checkpoints in the System Log and Fuzzy Checkpointing
5.17.5 Transaction Rollback and Cascading Rollback
5.17.6 Transaction Actions That Do Not Affect the Database
5.18 NO-UNDO/REDO Recovery Based on Deferred Update
5.19 Recovery Techniques Based on Immediate Update
5.20 Shadow Paging
5.21. The ARIES Recovery Algorithm
5.22, Database Backup and Recovery from Catastrophic Failures
5.23 Assignment Questions
5.24 Expected Outcome
5.25. Further Reading
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
5.0 Introduction
The concept of transaction provides a mechanism for describing logical units of database
processing. Transaction processing systems are systems with large databases and hundreds of
concurrent users executing database transactions, Examples:
+ airline reservations
+ banking
+ credit card processing
+ online retail purchasing,
+ Stock markets, supermarket checkouts, and many other applications
These systems require high availability and fast response time for hundreds of concurrent
users. A transaction is typically implemented by a computer program, which includes database
commands such as retrievals, insertions, deletions, and updates.
5.1 Objectives
* To study transaction properties
* To study creation of schedule and maintaining schedule equivalence.
°
To check whether the given schedule is serailizable or not.
‘ study protocols used for locking objects
© Differentiating between 2PL and Strict 2PL
5.2 Introduction to Transaction Processing
5.2.1 Single-User versus Multiuser Systems
* One criterion for classifying a database system is according to the number of users who
can use the system concurrently
Single-User versus Multiuser Systems
* ADBMSis
+ single-user
~at most one user at a time can use the system
- Eg: Personal Computer System
+ multiuser
- many users can use the system and hence access the database concurrently
- Eg: Airline reservation database
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
= Concurrent access is possible because of Multiprogramming. Multiprogramming can
be achieved by’
+ interleaved execution
+ Parallel Processing
* Multiprogramming operating systems execute some commands from one process,
then suspend that process and execute some commands from the next process, and so
on
* A process is resumed at the point where it was suspended whenever it gets its turn to
use the CPU again
"Hence, concurrent execution of processes is actually interleaved, as illustrated in
Figure 21.1
Figure 21.4
Interieaved process-
ing versus paral
processing
surent transal
= Figure 21.1, shows two processes, A and B, executing concurrently in an interleaved
fashion
= Interleaving keeps the CPU busy when a process requires an input or output (I/O)
operation, such as reading a block from disk
«The CPU is switched to execute another process rather than remai
time
* __Interleaving also prevents a long process from delaying other processes.
= If the computer system has multiple hardware processors (CPUs), parallel processing
of multiple processes is possible, as illustrated by processes C and D in Figure 21.1
* Most of the theory conceming concurrency control in databases is developed in terms of
interleaved concurrency
le during VO
* In a multiuser DBMS, the stored data items are the primary resources that may be
accessed concurrently by interactive users or application programs, which are constantly
retrieving information from and modifying the database.
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
5.2.2 Transactions, Database Items, Read and Write Operations, and DBMS
Buffers
* A Transaction an executing program that forms a logical unit of database processing
+ It includes one or more DB access operations such as insertion, deletion, modification or
retrieval operation.
+ It can be either embedded within an application program using begin transaction and
end transaction statements Or specified interactively via a high level query language
such as SQL
* Transaction which do not update database are known as read only transactions.
= Transaction which do update database are known as read write transactions.
"A database is basically represented as a collection of named data items The size of a
data item is called its granularity.
= A data item can be a database record, but it can also be a larger unit such as a whole
disk block, or even a smaller unit such as an individual field (attribute) value of some
record in the database
= Each data item has a unique name
"Basic DB access operations that a transaction can include are:
+ read_item(X): Reads a DB item named X into a program variable.
+ write_item(X): Writes the value of a program variable into the DB item named X
+ Executing read_item(X) include the following steps:
1, Find the address of the disk block that contains item X
2. Copy the block into a buffer in main memory
3. Copy the item X from the buffer to program variable named X.
+ Executing write_i
1. Find the address of the disk block that contains item X
fem(X) include the following steps:
2. Copy the disk block into a buffer in main memory
3, Copy item X from program variable named X into its correct location in buffer.
4, Store the updated disk block from buffer back to disk (either immediately or later),
* Decision of when to store a modified disk block is handled by recovery manager of the
DBMS jn cooperation with operating system.
"ADB cache includes a number of data buffers.
= When the buffers are all occupied a buffer replacement policy is used to choose one of
the buffers to be replaced. EG: LRU
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
A transaction includes read_item and write_item operations to access and update DB.
(a) 7 () T Figure 21.2
# ‘Two sample transac-
read_item(Xx); read_item(X); tions. (a) Transaction
X=X-N; X=X+M; T,. (6) Transaction Ty.
write_item(X); write_item(X);
read_item(Y);
Y=Y+N;
write_item(¥);
The read-set of a transaction is the set of all items that the transaction reads
* The
-set is the set of all items that the transaction writes
For example, the read-set of T1 in Figure 21.2 is {X, Y} and its write-set is also {X, Y}.
5.2.3 Why Concurrency Control Is Needed
"Several problems can occur when concurrent transactions execute in an uncontrolled
manner
= Example’
+ We consider an Airline reservation DB
+ Each records is stored for an airline flight which includes Number of reserved seats
among other information.
+ Types of problems we may encounter:
1, The Lost Update Problem
2. The Temporary Update (or Dirty Read) Problem
3. The Incorrect Summary Problem
4, The Unrepeatable Read Problem
Ty qT
read_item(X); read_item(X);
X=X+M; X=X-N;
write_item(X); write_item(X);
read_item(Y);
Y=Y+N;
write_item(Y);
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
"Transaction T1
+ 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.
= Transaction T2
+ reserves M seats on the first flight (X)
1. The Lost Update Problem
"occurs when two transactions that access the same DB items have their operations
interleaved in a way that makes the value of some DB item incorrect
" Suppose that transactions T1 and T2 are submitted at approximately the same time, and
suppose that their operations are interleaved as shown in Figure below
qh Tb
read item(X);
X=X-N;
read item(X);
X=X4M;
Time | | write item(x);
read item(Y); Item X has an incorrect value because
ere Tere 2}; its update by T; is lost (overwritten),
=Y4N;
write_item(Y);
"Final value of item X is incorrect because 72 reads the value of X before T1 changes it in
the database, and hence the updated value resulting from 71 is lost.
"For example:
X = 80 at the start (there were 80 reservations on the flight)
N-=5 (71 transfers 5 seat reservations from the flight corresponding
to X to the flight corresponding to Y)
M=4 (72 reserves 4 seats on X)
The final result should be X = 79.
* The interleaving of operations shown in Figure is X = 84 because the update in T1 that
removed the five seats from X was lost.
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
2. The Temporary Update (or Dirty Read) Problem
= occurs when one transaction updates a database item and then the transaction fails for
some reason
«Meanwhile the updated item is accessed by another transaction before it is changed back
to its original value
qh I
read_item(X);
X=X-N,
write_item(X);
Time reed item(X);
X=X+M:
written
Transaction T, fails and must change
read_item(Y); the value of X back to its old value;
meanwhile T, has read the temporary
incorrect value of X.
3. The Incorrect Summary Problem
+ If one transaction is calculating an aggregate summary function on a number of db items
while other transactions are updating some of these items, the aggregate function may
calculate some values before they are updated and others after they are updated.
T a
ma = 0
road tan
sum = sum +
‘oto
som,
‘ae Reset x“ Tyreads X after 1Vis subtracted and reads
seen sum: | bor dod wong suey
Eee i the rat (of by M)
as ar:
Yeon
ter
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
4. The Unrepeatable Read Problem
= Transaction T reads the same item twice and gets different values on each read, since
the item was modified by another transaction T’ between the two reads.
* for example, if during an airline reservation transaction, a customer inquires about seat
availability on several flights
+ When the customer decides on a particular flight, the transaction then reads the number
of seats on that flight a second time before completing the reservation, and it may end
Up reading a different value for the item.
5.2.4 Why Recovery Is Needed
= Whenever a transaction is submitted to a DBMS for execution, the system is responsible
for making sure that either
1. All the operations in the transaction are completed successfully and their effect is
recorded permanently in the database or
2The 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
+ Ifa transaction fails after executing some of its operations but before executing all of
them, the operations already executed must be undone and have no lasting effect.
Types of failures
1. Acomputer failure (system crash
+ A hardware, software, or network error occurs in the computer system during
transaction execution
+ Hardware crashes are usually media failures—for example, main memory failure.
2. Atransaction or system error:
+ Some operation in the transaction may cause it to fail, such as integer overflow or
division by zero
+ Also occur because of erroneous parameter values
3. Local errors or exception conditions detected by the transaction:
* During transaction execution, certain conditions may occur that necessitate cancellation
of the transaction
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
+ For example, data for the transaction may not be found
4, Concurrency control enforcement:
+The concurrency control may decide to abort a transaction because itviolates
serializability or several transactions are in a state of deadlock
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.
6. Physical problems and catastrophes:
+ refers to an endless list of problems that includes power or air-conditioning failure, fire,
theft, overwriting disks or tapes by mistake
+ Failures of types 1, 2, 3, and 4 are more common than those of types 5 or 6.
= Whenever a failure of type 1 through 4 occurs, the system must keep sufficient information to
quickly recover from the failure.
= Disk failure or other catastrophic failures of type 5 or 6 do not happen frequently; if they do
‘occur, recovery is a major task
5.3 Transaction and System Concepts
5.3.1 Transaction States and Additional Operations
* A transaction is an atomic unit of work that should either be completed in its entirety or
not done at all. For recovery purposes, the system keeps track of start of a transaction,
termination, commit or aborts.
+ BEGIN_TRANSACTION: marks the beginning of transaction execution
+ READ or WRITE: specify read or write operations on the database items that are
executed as part of a transaction
+ END_TRANSACTION: specifies that READ and WRITE transaction operations have
ended and marks the end of transaction execution
+ COMMIT_TRANSACTION: signals a successful end of the transaction so that any
changes (updates) executed by the transaction can be safely committed to the
database and will not be undone
+ ROLLBACK: signals that the transaction has ended unsuccessfully, so that any
changes or effects that the transaction may have applied to the database must be
undone
10
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
ma
an
‘TRARSACTION TRANSACTION | /parmauiy COMM
Bach Sear Coane
™ s8ont
5) —~C rtd)
Figure: State transition diagram illustrating the states for transaction execution
A transaction goes into active state immediately after it starts execution and can
execute read and write operations
‘When the transaction ends it moves to partially committed state.
At this end additional checks are done to see if the transaction can be committed or not
If these checks are successful the transaction is said to have reached commit point and
enters committed state. All the changes are recorded permanently in the db,
A transaction can go to the failed state if one of the checks fails or if the transaction is
aborted during its active state. The transaction may then have to be rolled back to undo
the effect of its write operation.
Terminated state corresponds to the transaction leaving the system. All the information
about the transaction is removed from system tables.
5.3.2 The System Log
Log or Journal keeps track of all transaction operations that affect the values of
database items
This information may be needed to permit recovery from transaction failures.
The log is kept on disk, so it is not affected by any type of failure except for disk or
catastrophic failure
one (or more) main memory buffers hold the last part of the log file, so that log entries.
are first added to the main memory buffer
When the log buffer is filled, or when certain other conditions occur, the log buffer is
appended to the end of the log file on disk.
u
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
= In addition, the log is periodically backed up to archival storage (tape) to guard against
such catastrophic 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 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_i
4, [commit, T]. Indicates that transaction T has completed successfully, and affirms that
1m, T, X]. Indicates that transaction T has read the value of database item X.
its effect can be committed (recorded permanently) to the database.
5. [abort, T]. Indicates that transaction T has been aborted,
5.3.3 Commit Point of a Transaction:
+ Defin
na Commit Pe
= A transaction T reaches its commit point when all its operations that access the
database have been executed successfully and the effect of all the transaction
operations on the database has been recorded in the log.
— Beyond the commit point, the transaction is said to be committed, and its effect is
assumed to be permanently recorded in the database.
— The transaction then writes an entry [commit,T] into the log,
+ Roll Back of transactions:
= Needed for transactions that have a [start_transaction,T] entry into the log but no
commit entry [commit,T] into the log.
5.3.4 DBMS specific buffer Replacement policies
Domain Separation(DS) method
+ DBMS cache is divided into separate domains, each handles one type of disk pages
and replacements within each domain are handled via basic LRU page replacement.
+ LRU is a static algorithm and does not adopts to dynamically changing loads because
the number of available buffers for each domain is predetermined.
+ Group LRU adds dynamically load balancing feature since it gives each domain a
priority and selects pages from lower priority level domain first for replacement.
2
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
Hot Set Method:
= This is useful in queries that have to scan a set of pages repeatedly.
= The hot set method determines for each db processing algorithm the set of disk pages
that will be accessed repeatedly and it does not replace them until their processing is
completed
The DBMIN method:
"uses a model known as QLSM (Query Locality set model), which predetermines the
pattem of page references for each algorithm for a particular db operation
= Depending on the type of access method, the file characteristics, and the algorithm
used the QLSM will estimate the number of main memory buffers needed for each file
involve
the operation,
5.4 Desirable Properties of Transactions
= Transactions should possess several properties, often called the ACID properties
‘A. Atomicity: a transaction is an atomic unit of processing and itis either performed
entirely or not at all
C Consistency Preservation: a transaction should be consistency preserving that is it
must take the database from one consistent state to another.
| Isola
n/independence: A transaction should appear as though itis being executed
in isolation from other transactions, even though many transactions are executed
concurrently.
D Durability (or Permanency): if a transaction changes the database and is committed,
the changes must never be lost because of any failure,
* The atomicity property requires that we execute a transaction to completion. It is the
responsibility of the transaction recovery subsystem of a DBMS to ensure atomicity.
= The preservation of consistency is generally considered to be the responsibilty of the
programmers who write the database programs or of the DBMS module that enforces
integrity constraints
"The isolation property is enforced by the concurrency control subsystem of the DBMS.
If every transaction does not make its updates (write operations) visible to other
transactions until it is committed, one form of isolation is enforced that solves the
temporary update problem and eliminates cascading rollbacks
"Durability is the responsibility of recovery subsystem.
B
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
5.5 Characterizing Schedules Based on Recoverability
* schedule (or history): the order of execution of operations from alll the various
transactions
+ Schedules (Histories) of Transactions: A schedule S of n transactions Ti, Ta,.......Tr
is a sequential ordering of the operations of the n transactions.
— The transactions are interleaved
+ 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)
* Conflicting operations:
+ 1(X) conflicts with wa(X) } Read write conflict
+ r2(X) conflicts with wi(X)
+ wi(X) conflicts with wa(X) Write conflict
+ 110%) do not conflicts with r2(X)
Schedules classified on recoverability:
+ Recoverable schedule:
= One where no transaction needs to be rolled back.
- Aschedule § is recoverable if no transaction T in S commits unti all transactions
T that have written an item that T reads have committed.
= Example:
+ Se ri(X); wal; 0X): (YY; we): 2; art
+ Sa 0X); wal; 20); (YD; wel; walYY; OH C2;
+ Cascadeless schedule:
= One where every transaction reads only the items that are written by committed
transactions,
+ Schedules requiring cascaded rollback:
= A schedule in which uncommitted transactions that read an item from a failed
transaction must be rolled back.
+ Strict Schedules:
= A schedule in which a transaction can neither read or write an item X until the
last transaction that wrote X has committed.
4
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
5.6 Characterizing Schedules Based on Serializability
schedules that are always considered to be correct when concurrent transactions are
‘executing are known as serializable schedules
Suppose that two users—for example, two airline reservations agents—submit to the
DBMS transactions T1 and 72 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 72 (in sequence).
2. Execute all the operations of transaction T2 (in sequence) followed by all the
operations of transaction T1 (in sequence).
Figure 21.5
Examples of serial and nonsarial schedules involving transactions T; and Tp (a)
chadule A:T; folloqiad by Tp (b) Serial schedule BT, felowred by Ty
(© Two nonsetial schedules C ahd B with interleaving of operations.
@ Te © 7 Te
road_iterniX};
XX M;
wite_item(0)
time | | Teaditemini: time | | t2ad-itemix)
vil Seer} read item(Y)
Y=7eN
write_temn(¥};
‘Schedule B
o h ie hi Te
read item(X) read item(xX)
XN X=X=N;
read_itom0x); ‘wie
=X, echoes
stim | | weite_tom(xy; Time read itom(X);
read item(Y) X=X4 Ms
‘o ‘weit itern(X);
=Van, eH road item(¥),
write temn(): Ya Vows
write tom();
Schedule C Schedule D
15
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
+ Serial schedule:
- Asschedule 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 schedule.
+ Serializable schedule:
= Aschedule S is serializable if it is equivalent to some serial schedule of the same
n transactions.
+ Result equivalent:
= Two schedules are called result equivalent if they produce the same final state of
the database,
* Conflict equivalent:
= Two schedules are said to be conflict equivalent if the order of any two conflicting
operations is the same in both schedules
+ Conflict serializable:
— Asschedule $ is said to be conflict serializable if itis conflict equivalent to some
serial schedule S’.
* Being serializable is not the same as being serial
* Being serializable implies that the schedule is a correct schedule.
— Itwill eave the database in a consistent state.
— The interleaving is appropriate and will result in a state as if the transactions
were serially executed, yet will achieve efficiency due to concurrent execution.
5.6.1 Testing conflict serializability of a Schedule S
For each transaction Ti participating in schedule S,create a node labeled Ti in the
precedence graph.
For each case in S where Tj executes a read_item(X) after Ti executes a write_item(X),
create an edge (Ti->T}) in the precedence graph,
For each case in S where Tj executes a write_item(X) after Ti executes a read_item (X)
,oreate an edge (Ti->T)) in the precedence graph.
For each case in S where Tj executes a write_item(X) after Ti exeoutes a write_item(X),
create an edge (Ti>T}) in the precedence graph.
The schedule $ is serializable if and only if the precedence graph has no cycles,
16
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
@
© x
%
Ny
RY
Fig: Constructing the precedence graphs for schedules A and D from fig 21.5 to test for conflict
serializability.
(a) Precedence graph for serial schedule A
(b) Precedence graph for serial schedule B.
(0) Precedence graph for schedule C (not serializable)
(d) Precedence graph for schedule D (serializable, equivalent to schedule A).
= Another example of serializability testing. (a) The READ and WRITE operations of three
transactions T;, Te, and Ta.
@ transaction T, transaction Tz transaction T,
read_item (X); read_item (Z); read_item (Y);
write item (X); read item (¥): read item (Z);
read_item (Y); vwrite_item (Y); vwrite_item (Y);
wirite_item (Y); read_item (X); write_item (Z);
write_item (X);
Dept. of CSE, ATMECE, Mysuru
v ©
read_tem (X);
Time | write item (X);
read_item (Y);
write_item (Y/);
©
read item (X);
Time | wte_item (X};
read _item (Y);
write_item (Y);
Dept. of CSE, ATMECE, Mysuru
read_item (2);
read_item (Y);
write_item (Y);
read _item (X);
wite_item (X);
Schedule E
read item (2);
read_item (¥);
vwrite_itern (Y);
readl_item (X);
vwrite_item (X);
Schedule F
Database Management System [18CS53]
transaction Ts
read_item (¥),
read _item (Z);
write_item (¥);
write_item (7);
‘transaction Ts
read item (¥);
read item (Z);
write_item (¥);
swrite_iter (Z);
18 Database Management System [18CS53]
= Precedence graph for schedule E
7 Se Eade i tin
Pin LJ - ‘None.
fan
e ihe eyete X(T, -*T), YT +7)
oycte X(T, “+7, Z(To*T. MT 9T)
Cn
"Precedence graph for schedule F
Equivalent serial schedules
hw hoh
5,7 Transaction Support in SQL
= The basic definition of an SQL transaction is, it 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
= Every transaction must have an explicit end statement, which is either a COMMIT or a
ROLLBACK
«Every transaction has certain characteristics attributed to it and are specified by a SET.
TRANSACTION statement in SQL
19
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
"The characteristics are
+ The access mode
+ can be specified as READ ONLY or READ WRITE
- The default is READ WRITE
- Amode of READ WRITE allows select, update, insert, delete, and create
commands to be executed
+ Amode of READ ONLY, as the name implies,
simply for data retrieval.
+ The diagnostic area size
- 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
- specified using the statement ISOLATION LEVEL , where the value for
can be READ UNCOMMITTED, READ COMMITTED, REPEATABLE
READ, or SERIALIZABLE
- The default isolation level is SERIALIZABLE
~ The use of the term SERIALIZABLE here is based on not allowing violations that
cause dirty read, unrepeatable read, and phantoms
- Ifa transaction executes at a lower isolation level than SERIALIZABLE, then one
oF more of the following three violations may occur:
1. Dirty read. A transaction T1 may read the update of a transaction 72, which
has not yet committed. If 72 fails and is aborted, then T1 would have read a
value that does not exist and is incorrect.
2. Nonrepeatable read. A transaction T1 may read a given value from a table. If
another transaction 72 later updates that value and T1 reads that value again,
T1 will see a different value.
3. Phantoms, A transaction T1 may read a set of rows from a table, perhaps
based on some condition specified in the SQL WHERE-clause. Now suppose
that a transaction 72 inserts a new row that also satisfies the WHERE-clause
condition used in 1, into the table used by 71. If 71 is repeated, then T1 will
see a phantom, a row that previously did not exist
20
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
Table 21.1. Possible Volations Based on lsolation Levels as Defined in SOL
Tye of Violation
Isolation Levet DiryRead Nonrepestable Read Phantom
READ UNCOMMITTED Yes Yes Yes
READ COMMITTED. No Yes Yes
REPEATABLE READ No No Yes
‘SERIALIZABLE No No 0
EXEC SQL WHENEVER SQLERROR Goro UNDO;
EMEC SQL SET TRANSACTION
READ WRITE
DIAGNOSTIC SIZE 5
ISOLATION LEVEL SERIALIZARLE;
EXEC SQL INSERT INTO EMPLOYEE (Fname, Iname, Ssn, Dno, Salary)
VALUES [ ‘Robert’, ‘smitn", 991004321", 2, 35000);
EXEC SOL UPDATE EMPLOYEE
SBT salary = Salary * 1.1 WHERE pao
EXEC SQL COMMIT;
GoTo THE_END;
UNDO: EXEC SQL ROLLBACK;
THE END: we;
+ The transaction consists of first inserting a new row in the EMPLOYEE table and then
updating the salary of all employees who work in department 2
« Ifan error occurs on any of the SQL statements, the entire transaction is rolled back
+ This implies that any updated salary (by this transaction) would be restored to its
previous value and that the newly inserted row would be removed.
21
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
Chapter 2: Concurrency Control in Databases
5.8 Introduction to Concurrency Control
+ Purpose of Concurrency Control
To enforce Isolation (through mutual exclusion) among conflicting transactions.
- To preserve database consistency through consistency preserving execution of
transactions,
— To resolve read-write and write-write conflicts.
+ Example:
= In concurrent execution environment if 1 conflicts with T2 over a data item A, then
the existing concurrency control decides if T1 or T2 should get the A and if the other
transaction is rolled-back or waits.
5.9 Two-Phase Locking Techniques for Concurrency Control
= The concept of locking data items is one of the main techniques used for controlling the
concurrent execution of transactions.
"A lock is a variable associated with a data item in the database, Generally there is a lock
for each data item in the database
= A lock describes the status of the data item with respect to possible operations that can be
applied to that item.
* Itis used for synchronizing the access by concurrent transactions to the database items.
= A transaction locks an object before using it
= When an object is locked by another transaction, the requesting transaction must wait
5.9.1 Types of Locks and System Lock Tables
1, Binary Locks
* Abinary lock can have two states or values: locked and unlocked (or 1
and 0).
* Ifthe value of the lock on X is 1, item X cannot be accessed by a database
operation that requests the item
22
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
If the value of the lock on X is 0, the item can be accessed when
requested, and the lock value is changed to 1
= We refer to the current value (or state) of the lock associated with item X
as lock(X).
* Two operations, lock_item and unlock_item, are used with binary
locking.
= A transaction requests access to an item X by first issuing a lock_item(X)
operation
= If LOCK(X) = 1, the transaction is forced to wait.
= IfLOCK(X) = 0, it is set to 1 (the transaction locks the item) and the
transaction is allowed to access item X
= When the transaction is through using the item, it issues an
unlock_item(X) operation, which sets LOCK(X) back to 0 (unlocks the
item) so that X may be accessed by other transactions
* Hence, a binary lock enforces mutual exclusion on the data item
lock_item(x):
B: if LOCK(X) = 0 (* item is unlocked *)
then LOCK(X) «1 (* lock the item *)
else
begin
wait (until LOCK(X) = 0
and the lock manager wakes up the transaction),
gotoB
end;
unlock_item(x):
LOCK(X) — 0; (* unlock the item *)
if any transactions are waiting
then wakeup one of the waiting transactions;
Fig: 2.1.1 Lock and unlock operations for binary licks.
23
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
+ The lock_item and unlock_item operations must be implemented as indivisible units that
is, no interleaving should be allowed once a lock or unlock operation is started until the
operation terminates or the transaction waits
+ The wait command within the lock_item(X) operation is usually implemented by putting
the transaction in a waiting queue for item X until X is unlocked and the transaction can
be granted access to it
* Other transactions that also want to access X are placed in the same queue.Hence, the
wait command is considered to be outside the lock_item operation
* It is quite simple to implement a binary lock; all that is needed is a binary-valued
variable, LOCK, associated with each data item X in the database
= In its simplest form, each lock can be a record with three fields: plus a queue for transactions that are waiting to access the
item
* If the simple binary locking scheme described here is used, every transaction must obey
the following rules:
1. A transaction T must issue the operation lock item(x) before any
read_item(X) or write_item(X) operations are performed in T.
2. A transaction T must issue the operation unlock_item(X) after all
read_item(X) and write_item(X) operations are completed in T.
3. A transaction T will not issue a lock_item(X) operation if it already holds the lock
on item X.
4. A transaction T will not issue an unlock_item(X) operation unless it already holds
the lock on item X.
2. Shared/Exclusive (or Read/Write) Locks
= binary locking scheme is too restrictive for database items because at most, one
transaction can hold a lock on a given item
= should allow several transactions to access the same item X if they all access X for
reading purposes only
* if'a transaction is to write an item X, it must have exclusive access to X
* For this purpose, a different type of lock called a multiple-mode lock is used
= In this scheme—called shared/exclusive or read/write locks—there are three locking
operations: read_lock(X), write_lock(X), and unlock(X)
24
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
A read-locked item is also called share-locked because other transactions are allowed
to read the item, whereas a writeocked item is called exclusive-tlocked because a
single transaction exclusively holds the lock on the item
Method to implement readwrite lock is to
- keep track of the number of transactions that hold a shared (read) lock
on an item in the lock table
= Each record in the lock table will have four fields
.
If LOCK(x)=wrte-locked, the value of locking_transaction(s) is single transaction that
holds the exclusive (write) lock on X.
If LOCK(X)=read-locked, the value of locking transaction(s) is a list of one or more
transactions that hold the shared (read) lock on X,
read_lock(X):
B: if LOCK(X) = “unlocked”
thenbegin LOCK() «~ “read-locked”;
no_of_reads(X) — 1
end
else if LOGK(X) = “readt-locked”
then no_of_reads(X) < no_of_reads(X) +1
else begin
wait (until LOCK) = “unlocked”
and the lock manager wakes up the transaction);
gotoB
end;
lock(0:
B: if LOCK(X) = “unlocked”
then LOCK() — “write-locked”
else begin
wait (until LOCK(X) = "unlocked"
and the lock manager wakes up the transaction);
gotoB
end;
25
Dept. of CSE, ATMECE, Mysuru Database Management System [18CS53]
unlock (X):
if LOGK(X) = “write-locked”
‘then begin LOCK(X) < “unlocked”;
wakeup one of the waiting transactions, if any
end
else it LOCK(X) = “read-locked”
then begin
no_of_reads(X)
