Transaction and

Concurrency Control
UNIT-4

-Navjot Kaur
Concurrency
• When more than one transactions are executing at a time
What are the advantages of having concurrency
Waiting Time
Response Time
Resource Utilization
Efficiency
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.
 Why Concurrency Control is needed
• The Lost Update Problem.
This occurs when two transactions that access the same database items have their
operations interleaved in a way that makes the value of some database item
incorrect.
• The Temporary Update (or Dirty Read) Problem.
This occurs when one transaction updates a database item and then the
transaction fails for some reason. The updated item is accessed by another
transaction before it is changed back to its original value.
• The Incorrect Summary Problem .
If one transaction is calculating an aggregate summary function on a number of
records while other transactions are updating some of these records, the
aggregate function may calculate some values before they are updated and others
after they are updated.
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.
Serializability
• Different forms of schedule equivalence give rise to the notions of:
1. conflict serializability
2. view serializability
• 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.
Serializability
1. Conflict
2. View

Conflict Serializable: A schedule is called conflict serializable if it can be

transformed into a serial schedule by swapping non-conflicting operations.

A schedule is said to be View-Serializable if it is view equivalent to a Serial

Schedule (where no interleaving of transactions is possible).
Conflict Pairs
Non conflict pair Conflict pairs
read(A) read(A) read(A) write(A)
write(A) read(A)
Non conflict pair: write(A) write(A)
read(B) read(A)
write(B) read(A)
read(B) write(A)
write(A) write(B)
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

• 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.
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 a conflict serializable if it is conflict
equivalent to a serial schedule.
 T1 T2
Example: Find Serial Schedule: Read(A)
Write(A)
Step 1: Read(B)
Read(A)
T1 T2
Read(A) Write(B)
Write(A)
Write(A)
Read(A) Read(B)
Write(B)
Read(B)
Write(A)

Write(B)
Read(B)
Write(B)

Check Read(B) of T1 and Read(A) of T2

Conflict?? No So SWAP.
Example: Find Serial Schedule:
T1 T2
Read(A)
Write(A)
Read(B)
Step 2: Read(A)

Write(B)

Write(A)
Read(B)
Write(B)

Check write(A) of T2 and Write(B) of T2

Conflict?? No So SWAP.
Example: Find Serial Schedule:
Step 3:
T1 T2 T1 T2
Read(A) Read(A)
Write(A) Write(A)
Read(B) Read(B)
Read(A) Write(B)

Write(B) Read(A)
Write(A)
Write(A) Read(B)
Read(B) Write(B)
Write(B)

Check write(B) of T1 and Read(A) of T2 Final Serial Schedule

Conflict?? No So SWAP.
Example4: If schedule is conflict serializable? Also find correct order of execution
of the instructions.

Consider a schedule:

T1 T2 T3
R(X)
R(Y)
R(X)
R(Y)
R(Z)
W(Y)
W(Z)
R(Z)
W(X)
W(Z)
Example4: is the schedule conflict serializable? Also find correct order of execution
of the instructions.

Consider a schedule:

T1 T2 T3
R(X)
R(Y)
R(X)
R(Y)
R(Z)
W(Y)
W(Z)
R(Z)
W(X)
W(Z)
Example 1: conflict equivalent
Consider a schedule:
S S1
T1 T2 T1 T2
Read(A) Read(A)
Write(A) Write(A)
Read(A) Read(A)
Write(A) Write(A)
Read(B) Read(B)
schedule S

Check whether S and S1 are conflict equivalent

Sol: check adjacent non conflicting pairs
Example3: If schedule is conflict serializable?
Consider a schedule:
T1 T2 T3
R(A)
W(A)
W(A)
W(A)
Question: Consider the
following schedules
involving two transactions.
Which one of the following
statement is true?
S1: R1(X) R1(Y) R2(X) R2(Y)
W2(Y) W1(X)
S2: R1(X) R2(X) R2(Y) W2(Y)
R1(Y) W1(X)
•Both S1 and S2 are conflict
serializable
•Only S1 is conflict serializable
•Only S2 is conflict serializable
•None
[GATE 2007]
Solution: Two transactions of
given schedules are:
T1: R1(X) R1(Y) W1(X) T2: R2(X)
R2(Y) W2(Y)
Let us first check serializability of
S1:
S1: R1(X) R1(Y) R2(X) R2(Y) W2(Y)
W1(X)
Question: Consider the
following schedules
involving two transactions.
Which one of the following
statement is true?
S1: R1(X) R1(Y) R2(X) R2(Y)
W2(Y) W1(X)
S2: R1(X) R2(X) R2(Y) W2(Y)
R1(Y) W1(X)
•Both S1 and S2 are conflict
serializable
•Only S1 is conflict serializable
•Only S2 is conflict serializable
•None
[GATE 2007]
Solution: Two transactions of
given schedules are:
T1: R1(X) R1(Y) W1(X) T2: R2(X)
R2(Y) W2(Y)
Let us first check serializability of
S1:
S1: R1(X) R1(Y) R2(X) R2(Y) W2(Y)
W1(X)
To convert it to a serial schedule, we have to swap non-conflicting
operations so that S1 becomes equivalent to serial schedule T1->T2 or T2-
>T1. In this case, to convert it to a serial schedule, we must have to swap
R2(X) and W1(X) but they are conflicting. So S1 can’t be converted to a
serial schedule.
Now, let us check serializability of S2:
S2: R1(X) R2(X) R2(Y) W2(Y) R1(Y) W1(X)
Swapping non conflicting operations R1(X) and R2(X) of S2, we get
S2’: R2(X) R1(X) R2(Y) W2(Y) R1(Y) W1(X)
Again, swapping non conflicting operations R1(X) and R2(Y) of S2’, we get
S2’’: R2(X) R2(Y) R1(X) W2(Y) R1(Y) W1(X)
Again, swapping non conflicting operations R1(X) and W2(Y) of S2’’, we get
S2’’’: R2(X) R2(Y) W2(Y) R1(X) R1(Y) W1(X)
which is equivalent to a serial schedule T2->T1.
So, correct option is C. Only S2 is conflict serializable.
 View Serializability
• A schedule is said to be view-serializable if it is view-
equivalent to some serial schedule.
• Any schedule that is conflict-serializable is also view-
serializable, but not vice versa.
• Below is a schedule which is view-serializable but not conflict
serializable.

• Every view serializable schedule that is not conflict serializable

has blind writes.
T1 T2 T3
R(A)
W(A)
W(A)
W(A)
1.Initial read must be same.

S1 : T1 reads A from Database.

S2 : T1 reads A from T2.
∴ S1 ≠ S2.
2. There are two transactions say  Ti and Tj, The schedule S1 and S2 are view
equivalent if in schedule S1, Ti reads A that has been updated by Tj, and  in
schedule S2,  Ti must read A from Tj. i.e. write-read(WR) sequence must be
same between S1 and S2.

• S1 : T3 reads value of A from T2.

S2 : T3 reads value of A from T1.
∴ S1 ≠ S2.
i.e. write-read sequence is not same between S1 and S2.
• 3. Final write operations should be same
between S1 and S2.

• S1 : A is finally updated by T3.

S2 : A is finally updated by T1.
∴ S1 ≠ S2.
• What is a Blind Write ??
• If there is no read operation before writing any value then it is Blind
Write. For Example :
Testing of Serializability Read(A): In T1, no subsequent writes to A, so no
new edges
Read(B): In T2, no subsequent writes to B, so no
new edges
Read(C): In T3, no subsequent writes to C, so no
new edges
Write(B): B is subsequently read by T3, so add
edge T2 → T3
Write(C): C is subsequently read by T1, so add
edge T3 → T1
Write(A): A is subsequently read by T2, so add
edge T1 → T2
Write(A): In T2, no subsequent reads to A, so no
new edges
Write(C): In T1, no subsequent reads to C, so no
new edges
Write(B): In T3, no subsequent reads to B, so no
new edges
Testing of Serializability
Ex: 2Testing of Serializability
Ex: 2Testing of Serializability
Read(A): In T4,no subsequent writes to A, so no
new edges
Read(C): In T4, no subsequent writes to C, so
no new edges
Write(A): A is subsequently read by T5, so add
edge T4 → T5
Read(B): In T5,no subsequent writes to B, so no
new edges
Write(C): C is subsequently read by T6, so add
edge T4 → T6
Write(B): A is subsequently read by T6, so add
edge T5 → T6
Write(C): In T6, no subsequent reads to C, so
no new edges
Write(A): In T5, no subsequent reads to A, so
no new edges
Write(B): In T6, no subsequent reads to B, so no
new edges
Ex: 2Testing of Serializability
Example: Find Serial Schedule:
Example :
T1 T2
Read(A)
Write(A)

Read(A)
Write(A)

Read(B)
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 >.
View Serializability
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. 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.
2. 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 .
3. 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’.
As can be seen, view equivalence is also based purely on reads and
writes alone.
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.

• 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.
Any view serializable schedule that is not conflict serializable must contain
a blind write.
Example: View Serializable:
Example :
Other Notions of Serializability
• The schedule below produces same outcome as the
serial schedule < T1, T5 >, yet is not conflict equivalent
or view equivalent to it.

• Determining such equivalence requires analysis of

operations other than read and write.
Conflict Serializability
Example:
Consider the following example and find whether schedule is conflict serializable or
not?
T1 T2 T3
R(A)
W(A)
W(A)
W(A)

Check conflict pairs:

Conflict Serializability
Check conflict pairs: T1 T2 T3
T1: R(A)
a) R(A) AND W(A) : CONFLICT W(A)

b) R(A) of T1 and W(A) of T3 : conflict W(A)

W(A)
T2:
T2 with T1
W(A) and R(A) : conflict
T2 with T3
W(A) and W(A) : conflict
Conflict Serializability
Check conflict pairs: T1 T2 T3
Now check for W(A) R(A)
It makes a cycle W(A)
W(A)
Note: if cycle/loop exists
W(A)
Then it is conflict serializable. It means
Serial schedule exists
View Serializability
Check conflict pairs: T1 T2 T3
Now check for W(A) R(A)
It makes a cycle W(A)
W(A)
Note: if cycle/loop exists
W(A)
Then it is conflict serializable. It means
Serial schedule exists
 Recoverable Schedules
• Need to address the effect of transaction failures on concurrently
running transactions.
• Recoverable schedule — if a transaction Tj reads a data item
previously written by a transaction Ti , then the commit
operation of Ti appears before the commit operation of Tj.
• The following schedule is not recoverable if T9 commits
immediately after the read

• If T8 should abort, T9 would have read an inconsistent database

state. Hence, database must ensure that schedules are
recoverable.
 Recoverable Schedules
• Schedule1 is recoverable because T2 reads the value of A
updated by T1 and also T1 commits before T2 which makes
the value read by T2 correct. Then T2 can commit itself.
• In schedule2, if T1 is aborted, T2 has to abort because the
value A it read is incorrect.
• In both cases, the database is in consistent state.
Cascading Rollbacks