Database Management System
Unit 7: Transactions Processing and
Concurrency Control
Lecture 1
Outline
7.1 ACID properties
7.2 Concurrent Executions
7.3 Serializability Concept
2
Transaction Concept
• A transaction is a unit of program execution that accesses and possibly
updates various data items.
• E.g. transaction to transfer $50 from account A to account B:
[Link](A)
2.A := A – 50
[Link](A)
[Link](B)
5.B := B + 50
[Link](B)
• Two main issues to deal with:
• Failures of various kinds, such as hardware failures and system crashes
• Concurrent execution of multiple transactions
3
Example of Fund Transfer
• Transaction to transfer $50 from account A to account B:
1. read(A)
2. A := A – 50
3. write(A)
4. read(B)
5. B := B + 50
6. write(B)
• Atomicity requirement
• If the transaction fails after step 3 and before step 6, money will be “lost” leading to an
inconsistent database state
• Failure could be due to software or hardware
• The system should ensure that updates of a partially executed transaction are not reflected in
the database
• 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.
4
Example of Fund Transfer (Cont.)
• Consistency requirement in above example:
• The sum of A and B is unchanged by the execution of the transaction
• In general, consistency requirements include
• Explicitly specified integrity constraints such as primary keys and foreign keys
• Implicit integrity constraints
• e.g., sum of balances of all accounts, minus sum of loan amounts must
equal value of cash-in-hand
• A transaction must see a consistent database.
• During transaction execution the database may be temporarily inconsistent.
• When the transaction completes successfully the database must be consistent
• Erroneous transaction logic can lead to inconsistency
5
Example of Fund Transfer (Cont.)
• Isolation requirement — if between steps 3 and 6, another transaction T2 is
allowed to access the partially updated database, it will see an inconsistent
database (the sum A + B will be less than it should be).
T1 T2
1. read(A)
2. A := A – 50
3. write(A)
read(A), read(B), print(A+B)
4. read(B)
5. B := B + 50
6. write(B
• Isolation can be ensured trivially by running transactions serially
• That is, one after the other.
• However, executing multiple transactions concurrently has significant benefits
6
ACID Properties
A transaction is a unit of program execution that accesses and possibly updates
various data [Link] preserve the integrity of data the database system must ensure:
• Atomicity. Either all operations of the transaction are properly reflected in
the database or none are.
• Consistency. Execution of a transaction in isolation preserves the
consistency of the database.
• Isolation. Although multiple transactions may execute concurrently, each
transaction must be unaware of other concurrently executing transactions.
Intermediate transaction results must be hidden from other concurrently
executed transactions.
• That is, 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.
• Durability. After a transaction completes successfully, the changes it has
made to the database persist, even if there are system failures.
7
Transaction State
• 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
restored to its state prior to the start of the transaction. Two options after
it has been aborted:
• restart the transaction
• can be done only if no internal logical error
• kill the transaction
• Committed – after successful completion.
8
Transaction State (Cont.)
9
Concurrent Executions
• Multiple transactions are allowed to run concurrently in the system.
Advantages are:
• Increased processor and disk utilization, leading to better transaction
throughput
• e.g., one transaction can be using the CPU while another is reading from or writing to the
disk
• Reduced average response time for transactions: short transactions need not
wait behind long ones.
• Concurrency control schemes – mechanisms to achieve isolation
• That is, to control the interaction among the concurrent transactions in order
to prevent them from destroying the consistency of the database
10
Schedules
• Schedule – a sequences of instructions that specify the chronological
order in which instructions of concurrent transactions are executed
• A schedule for a set of transactions must consist of all instructions of those
transactions
• Must preserve the order in which the instructions appear in each individual
transaction.
• A transaction that successfully completes its execution will have a
commit instructions as the last statement
• By default transaction assumed to execute commit instruction as its last step
• A transaction that fails to successfully complete its execution will have
an abort instruction as the last statement
11
Schedule 1
• Let T1 transfer $50 from A to B,
and T2 transfer 10% of the
balance from A to B.
• A serial schedule in which T1 is
followed by T2 :
12
Schedule 2
• A serial schedule where T2 is
followed by T1
13
Schedule 3
• Let T1 and T2 be the transactions
defined previously.
• The following schedule is not a serial
schedule, but it is equivalent to
Schedule 1.
In Schedules 1, 2 and 3, the sum A + B is preserved.
14
Schedule 4
• The following concurrent
schedule does not preserve
the value of (A + B ).
15
Serializability
• 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. Different forms of schedule equivalence give rise to
the notions of:
1. conflict serializability
2. view serializability
16
Simplified view of transactions
• We ignore operations other than read and write instructions
• We assume that transactions may perform arbitrary computations on
data in local buffers in between reads and writes.
• Our simplified schedules consist of only read and write instructions.
17
Conflicting Instructions
• 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
• Intuitively, a conflict between li and lj forces a (logical) temporal order
between them.
• If li and lj are consecutive in a schedule and they do not conflict, their results
would remain the same even if they had been interchanged in the schedule.
18
Conflict Serializability
• If a schedule S can be transformed into a schedule S’ by a series of
swaps of non-conflicting instructions, we say that S and S’ are conflict
equivalent.
• We say that a schedule S is conflict serializable if it is conflict
equivalent to a serial schedule
19
Conflict Serializability (Cont.)
• Schedule 3 can be transformed into Schedule 6, a serial schedule where T2
follows T1, by series of swaps of non-conflicting instructions. Therefore Schedule
3 is conflict serializable.
Schedule 3 Schedule 6
20
Conflict Serializability (Cont.)
• Example of a schedule that is not conflict serializable:
• We are unable to swap instructions in the above schedule to obtain
either the serial schedule < T3, T4 >, or the serial schedule < T4, T3 >.
21
Example 1: Conflict Serializability
• Lets consider the schedule:
• To convert this schedule into a serial schedule,
the R(A) operation of transaction T2 should be
swapped with the W(A) operation of transaction
T1.
• However we cannot swap these two operations
because they are conflicting operations, thus the
given schedule is not Conflict Serializable.
22
Example 2: Conflict Serializability
• Lets consider the schedule:
• Lets swap non-conflicting operations:
• After swapping R(A) of T1 and R(A) of T2 we get:
23
Example 2: Conflict Serializability conti..
• After swapping R(A) of T1 and R(B) of T2 we get:
• After swapping R(A) of T1 and W(B) of T2 we get:
• We finally got a serial schedule after swapping all the
non-conflicting operations so we can say that the
given schedule is Conflict Serializable.
24
View Serializability
• Let S and S’ be two schedules with the same set of transactions. S and S’ are view
equivalent if the following three conditions are met, for each data item Q,
1. Initial Read : If in schedule S, transaction Ti reads the initial value of Q, then in schedule S’
also transaction Ti must read the initial value of Q.
Suppose two schedule S1 and S2. In schedule S1, if a transaction T1 is reading
the data item A, then in S2, transaction T1 should also read A.
25
View Serializability Conti..
2. Updated Read : If in schedule S transaction Ti executes read(Q), and that value was
produced by transaction Tj (if any), then in schedule S’ also transaction Ti must read
the value of Q that was produced by the same write(Q) operation of transaction Tj .
Above two schedules are not view equal because, in S1, T3 is reading A
updated by T2 and in S2, T3 is reading A updated by T1.
26
View Serializability Conti..
3. Final Write: The transaction (if any) that performs the final write(Q)
operation in schedule S must also perform the final write(Q) operation
in schedule S’.
Above two schedules is view equal because Final write operation in S1 is
done by T3 and in S2, the final write operation is also done by T3.
27
View Serializability (Cont.)
• A schedule S is view serializable if it is view equivalent to a serial schedule.
• Every conflict serializable schedule is also view serializable.
• Below is a schedule which is view-serializable but not conflict serializable.
• Classwork: What serial schedule is above equivalent to?
• Every view serializable schedule that is not conflict serializable has blind writes.
• A blind write occurs when a transaction writes a value without reading it
28
View Serializability (Cont.)
• Taking first schedule S1
• Step 1: Initial Read
• The initial read operation in S is done by T1 and in S1, it is also
• 3! = 6 done by T1.
• S1 = <T1 T2 T3> • Step 2: Updated Read
• S2 = <T1 T3 T2> • In both schedules S and S1, there is no read except the initial
read that's why we don't need to check that condition.
• S3 = <T2 T3 T1> • Step 3: Final Write
• S4 = <T2 T1 T3> • The final write operation in S is done by T3 and in S1, it is also
done by T3. So, S and S1 are view Equivalent.
• S5 = <T3 T1 T2> • The first schedule S1 satisfies all three conditions, so we
don't need to check another schedule.
• S6 = <T3 T2 T1> • Hence, view equivalent serial schedule is:
• T1 T2 T3
29
Next
7.4 Lock based Protocols
7.5 Deadlock handling and Prevention
30
Database Management System
Unit 7: Transactions Processing and
Concurrency Control
Lecture 2
Previous
7.1 ACID properties
7.2 Concurrent Executions
7.3 Serializability Concept
2
Outline
7.4 Lock based Protocols
7.5 Deadlock handling and Prevention
3
Lock-Based Protocols
• A lock is a mechanism to control concurrent access to a data item
• Data items can be locked in two modes :
1. exclusive (X) mode
• Data item can be both read as well as written
• X-lock is requested using lock-X instruction.
2. shared (S) mode
• Data item can only be read
• S-lock is requested using lock-S instruction.
• Lock requests are made to concurrency-control manager. Transaction can proceed
only after request is granted.
4
Lock-Based Protocols (Cont.)
• Lock-compatibility matrix
• A transaction may be granted a lock on an item if the requested lock is compatible with
locks already held on the item by other transactions
• Any number of transactions can hold shared locks on an item,
• But if any transaction holds an exclusive on the item no other transaction may
hold any lock on the item.
• If a lock cannot be granted, the requesting transaction is made to wait till all
incompatible locks held by other transactions have been released. The lock is
then granted.
5
Schedule With Lock Grants
• Assume grant happens just
before the next instruction
following lock request
• A locking protocol is a set of
rules followed by all
transactions while requesting
and releasing locks.
• Locking protocols enforce
serializability by restricting
the set of possible schedules.
6
Deadlock
• Consider the partial schedule
Neither T3 nor T4 can make progress — executing lock-S(B) causes T4 to wait for
T3 to release its lock on B, while executing lock-X(A) causes T3 to wait for T4 to
release its lock on A.
• Such a situation is called a deadlock.
• To handle a deadlock one of T3 or T4 must be rolled back
and its locks released.
7
Deadlock (Cont.)
• The potential for deadlock exists in most locking protocols.
• Starvation is also possible if concurrency control manager is badly
designed. For example:
• A transaction may be waiting for an X-lock on an item, while a
sequence of other transactions request and are granted an S-lock
on the same item.
• The same transaction is repeatedly rolled back due to deadlocks.
• Concurrency control manager can be designed to prevent starvation.
8
The Two-Phase Locking (2PL) Protocol
• 2PL protocol divides the execution phase of a transaction into three
different parts.
• In the first part, when the transaction begins to execute, it requires
permission for the locks it needs.
• The second part is where the transaction obtains all the locks. When a
transaction releases its first lock, the third part starts.
• In this third part, the transaction cannot demand any new locks. Instead, it
only releases the acquired locks.
9
2PL
10
The Two-Phase Locking (2PL) Protocol
• A protocol which ensures conflict-serializable schedules.
• Phase 1: Growing Phase
• Transaction may obtain locks
Locks
• Transaction may not release locks
• Phase 2: Shrinking Phase
• Transaction may release locks Time
• Transaction may not obtain locks
• The protocol assures serializability. The transactions can be
serialized in the order of their lock points (i.e., the point where
a transaction acquired its final lock).
11
The Two-Phase Locking Protocol (Cont.)
• Two-phase locking does not ensure freedom from deadlocks
• Extensions to basic two-phase locking needed to ensure recoverability of
freedom from cascading roll-back
• Strict two-phase locking: a transaction must hold all its exclusive locks till it
commits/aborts.
• Ensures recoverability and avoids cascading roll-backs
• Rigorous two-phase locking: a transaction must hold all locks till commit/abort.
• Transactions can be serialized in the order in which they commit.
• Most databases implement rigorous two-phase locking, but refer to it as
simply two-phase locking
12
Locking Protocols
• Given a locking protocol (such as 2PL)
• A schedule S is legal under a locking protocol if it can be generated by a set of transactions
that follow the protocol
• A protocol ensures serializability if all legal schedules under that protocol are serializable
14
Lock Conversions
• Two-phase locking protocol with lock conversions:
– Growing Phase:
• can acquire a lock-S on item
• can acquire a lock-X on item
• can convert a lock-S to a lock-X (upgrade)
– Shrinking Phase:
• can release a lock-S
• can release a lock-X
• can convert a lock-X to a lock-S (downgrade)
• This protocol ensures serializability
15
Automatic Acquisition of Locks
• A transaction Ti issues the standard read/write instruction, without explicit locking calls.
• The operation read(D) is processed as:
if Ti has a lock on D
then
read(D)
else begin
if necessary wait until no other
transaction has a lock-X on D
grant Ti a lock-S on D;
read(D)
end
16
Automatic Acquisition of Locks (Cont.)
• write(D) is processed as:
if Ti has a lock-X on D
then
write(D)
else begin
if necessary wait until no other trans. has any lock on D,
if Ti has a lock-S on D
then
upgrade lock on D to lock-X
else
grant Ti a lock-X on D
write(D)
end;
• All locks are released after commit or abort
17
Implementation of Locking
• A lock manager can be implemented as a separate process
• Transactions can send lock and unlock requests as messages
• The lock manager replies to a lock request by sending a lock grant
messages (or a message asking the transaction to roll back, in case of
a deadlock)
• The requesting transaction waits until its request is answered
• The lock manager maintains an in-memory data-structure called a lock table to
record granted locks and pending requests
18
Lock Table
• Dark rectangles indicate granted locks, light colored
ones indicate waiting requests
• Lock table also records the type of lock granted or
requested
• New request is added to the end of the queue of
requests for the data item, and granted if it is
compatible with all earlier locks
• Unlock requests result in the request being deleted,
and later requests are checked to see if they can now
be granted
• If transaction aborts, all waiting or granted requests of
the transaction are deleted
• lock manager may keep a list of locks held by each
transaction, to implement this efficiently
19
Graph-Based Protocols
• Graph-based protocols are an alternative to two-phase locking
• Impose a partial ordering on the set D = {d1, d2 ,..., dh} of all data items.
• If di dj then any transaction accessing both di and dj must access di before accessing dj.
• Implies that the set D may now be viewed as a directed acyclic graph, called a database
graph.
• The tree-protocol is a simple kind of graph protocol.
20
Tree Protocol
Tree protocol:
1. Only exclusive locks are allowed.
2. The first lock by Ti may be on any data item. Subsequently, a data Q can be locked by Ti only if the
parent of Q is currently locked by Ti.
3. Data items may be unlocked at any time.
4. A data item that has been locked and unlocked by Ti cannot subsequently be relocked by Ti
21
Deadlock Handling
• System is deadlocked if there is a set of transactions such that every
transaction in the set is waiting for another transaction in the set.
23
Deadlock Handling
• Deadlock prevention protocols ensure that the system will never enter into a deadlock state.
Some prevention strategies:
• Require that each transaction locks all its data items before it begins execution (pre-
declaration).
• Impose partial ordering of all data items and require that a transaction can lock data items
only in the order specified by the partial order (graph-based protocol).
24
More Deadlock Prevention Strategies
• wait-die scheme — non-preemptive
• Older transaction may wait for younger one to release data item.
• Younger transactions never wait for older ones; they are rolled back instead.
• A transaction may die several times before acquiring a lock
• wound-wait scheme — preemptive
• Older transaction wounds (forces rollback) of younger transaction instead of waiting for it.
• Younger transactions may wait for older ones.
• Fewer rollbacks than wait-die scheme.
• In both schemes, a rolled back transactions is restarted with its
original timestamp.
• Ensures that older transactions have precedence over newer ones, and starvation is thus
avoided.
25
Deadlock prevention (Cont.)
• Timeout-Based Schemes:
• A transaction waits for a lock only for a specified amount of time. After that, the wait times
out and the transaction is rolled back.
• Ensures that deadlocks get resolved by timeout if they occur
• Simple to implement
• But may roll back transaction unnecessarily in absence of deadlock
• difficult to determine good value of the timeout interval.
• Starvation is also possible
26
Deadlock Detection
• Wait-for graph
• Vertices: transactions
• Edge from Ti Tj. : if Ti is waiting for a lock held in conflicting mode byTj
• The system is in a deadlock state if and only if the wait-for graph has a cycle.
• Invoke a deadlock-detection algorithm periodically to look for cycles.
Wait-for graph without a cycle Wait-for graph with a cycle
27
Deadlock Recovery
• When deadlock is detected :
• Some transaction will have to rolled back (made a victim) to break deadlock cycle.
• Select that transaction as victim that will incur minimum cost
• Rollback -- determine how far to roll back transaction
• Total rollback: Abort the transaction and then restart it.
• Partial rollback: Roll back victim transaction only as far as necessary to release locks that
another transaction in cycle is waiting for
• Starvation can happen
• One solution: oldest transaction in the deadlock set is never chosen as victim
28
NEXT
29
Multiple Granularity
• Allow data items to be of various sizes and define a hierarchy of data granularities, where the
small granularities are nested within larger ones
• Can be represented graphically as a tree (but don't confuse with tree-locking protocol)
• When a transaction locks a node in the tree explicitly, it implicitly locks all the node's descendents
in the same mode.
• Granularity of locking (level in tree where locking is done):
• Fine granularity (lower in tree): high concurrency, high locking overhead
• Coarse granularity (higher in tree): low locking overhead, low concurrency
30
Example of Granularity Hierarchy
The levels, starting from the coarsest (top) level are
• database
• area
• file
• record
31
Intention Lock Modes
• In addition to S and X lock modes, there are three additional lock modes with multiple
granularity:
• intention-shared (IS): indicates explicit locking at a lower level of the tree but only with
shared locks.
• intention-exclusive (IX): indicates explicit locking at a lower level with exclusive or shared
locks
• shared and intention-exclusive (SIX): the subtree rooted by that node is locked explicitly in
shared mode and explicit locking is being done at a lower level with exclusive-mode locks.
• intention locks allow a higher level node to be locked in S or X mode without having to check all
descendent nodes.
32
Compatibility Matrix with Intention Lock Modes
• The compatibility matrix for all lock modes is:
33
Multiple Granularity Locking Scheme
• Transaction Ti can lock a node Q, using the following rules:
1. The lock compatibility matrix must be observed.
2. The root of the tree must be locked first, and may be locked in any mode.
3. A node Q can be locked by Ti in S or IS mode only if the parent of Q is currently
locked by Ti in either IX or IS mode.
4. A node Q can be locked by Ti in X, SIX, or IX mode only if the parent of Q is currently
locked by Ti in either IX or SIX mode.
5. Ti can lock a node only if it has not previously unlocked any node (that is, Ti is two-
phase).
6. Ti can unlock a node Q only if none of the children of Q are currently locked by Ti.
• Observe that locks are acquired in root-to-leaf order, whereas they are released in leaf-to-root order.
• Lock granularity escalation: in case there are too many locks at a particular level, switch to higher
granularity S or X lock
34
Insert/Delete Operations and
Predicate Reads
• Locking rules for insert/delete operations
1. An exclusive lock must be obtained on an item before it is deleted
2. A transaction that inserts a new tuple into the database is automatically
given an X-mode lock on the tuple
• Ensures that
• reads/writes conflict with deletes
• Inserted tuple is not accessible by other transactions until the transaction
that inserts the tuple commits
35
End of Unit 7
36