Chapter 18 (TCDS)

Concurrency
Control
Sukarna Barua
Associate Professor, CSE, BUET
03/20/2024
 

Concurrency Control

 Concurrent transactions accessing same elements cause inconsistent database state

 Transaction T1: Read(X,t); A := A + 100; WRITE(X,t)
 Transaction T2: Read(X,t); A := A + 100; WRITE(X,t)
 Say initially X = 1000. After successful execution of T1 and T2, X should be 1200.
 What happens in a concurrent execution of T1 and T2 when READ(X,t) of T1
happens after READ(X,t) of T2?
 Final value of X become 1100! [An inconsistent state]

03/20/2024
 Control

 Prevention of inconstancy: Need some control to prevent inconsistent state

 DBMS Scheduler ensures that database remains consistent during concurrent
execution of transaction.
 This is called concurrency control.

03/20/2024
 

Role of Scheduler

 Every request for read and write of database elements are passed to scheduler.
 Two cases arise:
 Case 1: Schedule execute read/write
immediately when it is safe to do so using
memory buffers.
 Case 2: Scheduler delays the read/write as
it is not safe due to other transactions
accessing the same elements and can
cause inconsistent database state.

03/20/2024
 Schedule
 A schedule is a sequence of database actions
 Actions come from one ore more transactions.
 Database actions are same as the actions taken by a transaction.
 Database actions of the transactions occur in the order as determined by a schedule
 Purpose of schedule is safe execution of concurrent transactions.

 Some assumptions
 Read and write take place in main memory buffers.
 A database element brought to a buffer by some transaction T may be read or
written not only by T but by other transactions.

03/20/2024
 

Schedule

 Consider the transactions T1 and T2 shown below.

 Before the transactions A = B.

 If both T1 and T2 happen successfully, then consistency requirement is A = B.
 Since T1 adds 100 to both A and B, and T2 multiplies both A and B with 2.
 A schedule of T1 and T2 should ensure database in consistent state.
03/20/2024
 

Serial Schedule

 A schedule is serial if its actions consist of

- all the transactions of one transaction
- then all actions of another transaction
- and so on.
 In a serial schedule:
 Database actions happen by transaction order.
 No mixing of actions from different
transactions are allowed.

03/20/2024
 

Serial Schedule

 Example of serial schedule: A serial schedule shown

where T1 precedes T2.
 For this example, two serial schedules
are possible:
 Schedule 1 (T1,T2): T1 precedes T2
 Schedule 2 (T2,T1): T2 precedes T1.

03/20/2024
 

Serial Schedule

 Consider the two serial schedules. Assume initially A = B = 1000. Are the values of A
and B same at the end of the two schedules?
 NO! Final values of database elements are dependent on the order of transactions.

03/20/2024
 

Serializable Schedule

 Every serial schedule preserve database consistency. [Why? ]

 Are there other schedules that preserve database consistency?
 Serializable: A schedule S is serializable if there is a serial schedule S' such that
for every initial database state, the effect of S and S' are the same.
 Consider the schedule shown right.
 We can show that A=B is preserved by this
schedule.
 It is serializable schedule as its effects are
equivalent to the serial schedule (T1,T2)

03/20/2024
 

Serializable Schedule

 Consider the schedule shown below. Is this serializable?

 We can show that will not be preserved for this schedule
 Thus, it is not serializable!

03/20/2024
 

Serializable Schedule

 Consider another schedule shown below. Is this serializable?

 We can show that will be preserved for this schedule
 Thus, it is serializable!
 The order of operations are same as
the previous schedule except that
operations differs!
 Thus, serializable depends on actual
business operation!

 However, DBMS scheduler does not care

what individual transactions are doing with
the database elements!

03/20/2024
 

Serializable Schedule

 DBMS schedule only takes into account the READ and WRITE requests and
determine a schedule that is serializable.
 For DBMS scheduler, a transaction is represented by following actions:
 : Transaction T reads database element .
 : Transaction T writes database element .

 Transactions may be described as below:

:
:

 A serializable schedule is:

03/20/2024
 

Notations for Schedule

 An action is an expression of the form or meaning:

 Transaction reads or writes X.

 A transaction is a sequence of actions.

 A schedule S of a set of transactions is a sequence of actions, in which

 For each transaction the actions of appear in S in the same order that they appear
in . [schedule cannot violate the order of action-sequence of a transaction ]

03/20/2024
 Conflict Serializable Schedule

 Usually, a stronger condition "conflict serializability" is ensured in database.

 It is stronger than the general notion of serializability.

 Conflict: A pair of conservative actions is a conflict such that

 If their order is interchanged, then the behavior of at least one of the transactions
can change.

03/20/2024
 

Conflicts

 Assume and are different transactions. The following pair of actions are not
conflicting:

 is never a conflict even if .

- Reason is neither steps change database element.
 ; is not a conflict if .
- If write and then read , is not changed.
- If read and write , 's action does not change .
 is not a conflict if .
- Same reason as above.
 is not a conflict if .

03/20/2024
 Conflicts

 The following pairs are conflicting:

 always conflict.
- The order of actions in a transaction are fixed and cannot be changed.

 always conflict.
- Two writes of the same element by different transactions conflict.
- Swapping order changes the final value of .

 always conflict.
- A read and a write of the same element by different transactions conflicts.
- Swapping order changes the value read by .

03/20/2024
 

Conflicts

 Summarize:
 Any two actions of different transactions may be swapped unless
- They involve same database element, and
- At least one is a write.

 Note the word "and" above.

03/20/2024
 Conflict Serializable
 Conflict-equivalent: Two schedules are conflict equivalent if one schedule can be
turned into other schedule by a sequence of nonconflicting swaps of adjacent actions.
- Swapping only adjacent actions are allowed.

 Conflict-serializable: A schedule is conflict-serializable if it is conflict-equivalent of a

serial schedule.

03/20/2024
 Conflict Serializable
 A conflict-serializable schedule is also a serializable schedule.
 Conflict-serializability is a sufficient condition for serializability.

 A serializable schedule is not always conflict-serializable.

 Conflict-serializability is not required for serializability.

 DBMS usually use conflict-serializability for concurrency control.

03/20/2024
 Conflict Serializable
 Consider the schedule below. Is it conflict-serializable?

 The schedule can be converted to a serial schedule by the sequence of nonconflicting

swaps shown below.

 Thus, the given schedule is conflict-serializable!

03/20/2024
 Test for Conflict-serializability
 Precedence: Given a schedule S, involving transactions and , we say takes
precedence over , written if there are actions of and of such that:
- is ahead of in S,
- Both and involve same database element, and
- At least one of and is a write action.

 and are conflicting actions. Thus they cannot be swapped.

 will appear before in any schedule that is conflict-serializable to S!
 A conflict-equivalent serial schedule of S must have before . [ Why? ]

03/20/2024
 Test for Conflict-serializability
 Precedence graph:
 All precedence's between transactions can be summarized using a graph.
- Nodes are transactions of S.
- There is a directed edge from to if .
 Known as precedence graph.

 Example: Consider the following schedule involving three transactions , , and

 Here, due to . due to .

 The corresponding precedence graph is shown below.

03/20/2024
 Test for Conflict-serializability
 Construct the precedence graph for schedule S.

 If there is a cycle in the precedence graph, then the schedule is not conflict-
serializable.

 If the graph is acyclic, then it is conflict-serializable.

 Any topological order of transactions is the conflict-equivalent serial schedule.

 For the shown precedence graph below, a conflict-equivalent serial schedule is (T1,
T2, T3).

03/20/2024
 Test for Conflict-serializability
 Consider the following schedule.

 The precedence graph for the schedule is shown below.

 [ ]
 [ ]
 : [ ]

 As the graph has a cycle, it is not conflict-serializable!

03/20/2024
 Why Precedence Graph Test Work
 Show that if there is a cycle in precedence graph, then the schedule is not conflict-
serializable.

 Proof: Say there is a cycle of transactions .

According to the cycle:
 Actions of must precede those of , those of , and those of .
 Hence, actions of must precede actions of . However, arc from enforces actions of
must precede actions of .
 The above two constraints cannot be made possible in any schedule. Thus, the
schedule is not conflict-serializable.

03/20/2024
 Why Precedence Graph Test Work
 Converse: Show that if there is no cycle in precedence graph, then the schedule is
conflict-serializable.

 Proof by induction on the number of transactions :

 For , it is serializable as there is only one transaction [trivial].

 Induction step: Assume the statement is true for a schedule involving transactions.
 We show that it is also true for schedule involving transactions.

03/20/2024
 Why Precedence Graph Test Work
 Induction step:
 Consider the schedule involving transactions and its precedence graph that has no
cycle.
 As the graph is acrylic, there is a node which does not have any arc in. Let the
node be and corresponding transaction .
 Since there are no arcs into node no action in any other transaction conflicts with
actions of . [why?]
 Hence, all actions of can be moved to the front of the schedule by swapping with
other interleaving actions.
 This results in the following schedule:

03/20/2024
 Why Precedence Graph Test Work
 Induction step:
…

 Consider the partial schedule specified by actions of the other transactions.

 The precedence graph for this partial schedule is acyclic [Why?]
 It involves transactions.
 Thus it is conflict-serializable by induction hypothesis.
 Thus can be converted to a conflict-serializable schedule as:
 Placing actions of first
 Placing actions of other transactions in serial order [according to induction
hypothesis this can be done]
[ Proof is complete ]
03/20/2024
 Enforcing Serializability by Locks
 Locks: Locks on database elements are used to enforce conflict-serializability.
 Locks are requested by transactions before reading or writing database elements.
 A locking scheduler enforces conflict-serializable.
 A lock table is used to manage locks of database elements.

03/20/2024
 Enforcing Serializability by Locks
 Rules for appropriate uses of locking: Following two rules must be preserved.

 R1 - Consistency of transactions: Actions and locks must relate.

- A transaction can read or write an element if it previously was granted a lock on
that element and hasn't yet released the lock.
- If a transaction locks an element, it must unlock that element

 R2 - Legality of schedules: Locks must have their intended meaning.

- No two transactions may have locked the same element without one having
first released the lock.

03/20/2024
 Enforcing Serializability by Locks
 New actions for locking and unlocking by transactions:
- Transaction request a lock on
- : Transaction releases its lock on

 R1 - Consistency of transactions: When a transaction has an action or , then

- There is a previous action with no intervening action .
- There is a subsequent

 R2 - Legality of schedule: If there are actions followed by in a schedule, then

somewhere between these actions there must be an action .
 Note a legal schedule is not necessarily a conflict-serializable schedule!

03/20/2024
 Enforcing Serializability by Locks
 Consider the schedule with lock instructions added.
 Each transactions is consistent according to lock principle. [ why? ]
 The schedule is legal according to lock principle. [ why? ]

03/20/2024
 Locking scheduler
 Locking schedule grants locks if and only if the request will result in a legal schedule.

 If a request is not granted, the requesting transaction is delayed.

 Transactions waits until lock can be granted.
 As locks are available (unlocked), transaction resumes execution with locks
granted.

 Locking is maintained using a lock table.

 Simply lock table has entry of the form meaning transaction currently holds locks
on

03/20/2024
 Locking scheduler
 Consider the following schedule.
 Note why lock is denied for [ T2 is kept waiting for the lock ]

03/20/2024
 Locking and Conflict Serializability: Two-
phase locking
 Two-phase locking:
 Condition: In every transaction, all locks precede all unlock actions.

 The above is known as two-phase locking (or 2PL) condition.

 First phase (growing phase): Obtain all locks
 Second phase (shrinking phase): Release all locks.

 A transaction obeying 2PL is called two-phase-locked (or 2PL) transaction.

 Surprisingly, a schedule satisfying 2PL condition is conflict-serializable!

03/20/2024
 Two-phase locking
 Example of 2PL: The following schedule satisfies 2PL condition. [ why? ]

03/20/2024
 2PL Schedule Is Conflict
Serializable
 Prove that a schedule satisfying 2PL condition is conflict serializable.
 Proof by induction:
 For , this is trivial [a schedule involving a single transaction is always conflict
serializable]
 Induction hypothesis: Assume, a schedule of transactions satisfying 2PL conditions is
conflict serializable.
 We have to show that statement is true for .

03/20/2024
 2PL Schedule Is Conflict
 Induction step:
Serializable
 Consider .
 Consider the first unlock action in schedule . This action is from transaction .
 There is no unlock action preceding . [ why? ]
 No actions of any other transaction can conflict with actions of . [ why? ]
 As per 2PL, is holding all locks, and thus no other transaction has locks on
elements accessed by
 Thus, actions of can be moved forward to the front of the schedule.
 We get a new schedule as follows:

03/20/2024
 2PL Schedule Is Conflict
 Induction step:
Serializable
…

 As per induction hypothesis, the partial schedule of transactions is conflict-

serializable as it obeys 2PL condition.
 Thus can be converted to a conflict-serializable schedule as:
 Placing actions of first
 Placing actions of other transactions in serial order [according to induction
hypothesis this can be done]

[Proof is complete]

03/20/2024
 2PL: Potential for Deadlock
 Consider the schedule below that satisfying 2PL [no unlock before locks].

 At this position, no transactions can proceed as one is waiting for the other by the
locking schedule.
 This condition is known as deadlock!
03/20/2024