Database Management System 20: Concurrent Execution

Concurrent Execution

Chittaranjan Pradhan

Database Management Concurrent Execution

Schedules
System 20 Serial Schedule

Concurrent Schedule
Serializability
Concurrent Execution Conflict Serializability

Testing for Conflict
Serializability
View Serializability
School of Computer Engineering,
KIIT University
20.1
Schedules
Concurrent execution of transactions means executing more Serial Schedule
Concurrent Schedule
than one transaction at the same time Serializability
Conflict Serializability
In the serial execution, one transaction can start executing only Serializability
after the completion of the previous
The advantages of using concurrent execution of transactions

are:
• Improved throughput and resource utilization
• Reduced waiting time
The database system must control the interaction among the
concurrent transactions to prevent them from destroying the
consistency of the database. It does this through a variety of
mechanisms called concurrency control schemes
20.2
Concurrent Execution...
T1 transfers Dollar $100 from account A to account B Schedules
T1 Serial Schedule
Concurrent Schedule
Read(A);
Serializability
A:=A-100; Conflict Serializability
Write(A); Testing for Conflict

Serializability
Read(B); View Serializability
B:=B+100;
Write(B);
T2 transfers 20% of balance from account A to account B

T2
Read(A);
Temp=0.2*A;
A:=A-Temp;
Write(A);
Read(B);
B:=B+Temp;
Write(B);
20.3
Schedules
Schedules
Serial Schedule
Concurrent Schedule
Schedules Serializability
A schedule is a sequence that indicates the chronological order Testing for Conflict
Serializability
in which instructions of concurrent transactions are executed View Serializability
A schedule for a set of transactions must consist of all

instructions of those transactions
We must preserve the order in which the instructions appear in

each individual transaction
20.4
Serial Schedule
Schedules
Serial Schedule
Concurrent Schedule
Serial Schedule Serializability
A serial schedule is a schedule where all the instructions Testing for Conflict
Serializability
belonging to each transaction appear together View Serializability
There is no interleaving of transaction operations. A serial

schedule has no concurrency and therefore it does not
interleave the actions of different transactions
For n transactions, there are exactly n! different serial

schedules possible
20.5
Serial Schedule...
T1 T2
Read(A);
A:=A-100; Concurrent Execution
Write(A); Schedules
Read(B); Serial Schedule
B:=B+100; Concurrent Schedule
Write(B);
Schedule1 (T1 followed by T2 ) Read(A);
Serializability
Temp=0.2*A; Testing for Conflict
Serializability
A:=A-Temp;
Write(A);
Read(B);
B:=B+Temp;
Write(B);
T1 T2
Read(A);
Temp=0.2*A;
A:=A-Temp;
Write(A);
Read(B);
B:=B+Temp;
Schedule2 (T2 followed by T1 ) Write(B);
Read(A);
A:=A-100;
Write(A);
Read(B);
B:=B+100;
Write(B);
20.6
Concurrent Schedule
Concurrent Schedule Concurrent Execution
Schedules
In concurrent schedule, operations from different concurrent Serial Schedule
transactions are interleaved Concurrent Schedule
Serializability
The number of possible schedules for a set of n transactions is Testing for Conflict
Serializability
much larger than n! View Serializability
T1 T2
Read(A);
A:=A-100;
Write(A);
Read(A);
Temp=0.2*A;
A:=A-Temp;
Schedule3 Write(A);
Read(B);
B:=B+100;
Write(B);
Read(B);
B:=B+Temp;
Write(B);
20.7
Concurrent Schedule...
T1 T2
Read(A);
A:=A-100; Concurrent Execution
Read(A); Schedules
Temp=0.2*A; Serial Schedule
A:=A-Temp; Concurrent Schedule
Write(A);
Schedule4 Read(B);
Serializability
Write(A); Testing for Conflict
Serializability
Read(B);
B:=B+100;
Write(B);
B:=B+Temp;
Write(B);
T1 T2
Read(A);
A:=A-100;
Write(A);
Read(A);
Temp=0.2*A;
A:=A-Temp;
Schedule5 Read(B);
B:=B+100;
Write(A);
Read(B);
B:=B+Temp;
Write(B);
Write(B);
20.8
Serializability
Serializability Schedules
Serial Schedule
A concurrent schedule is serializable if it is equivalent to a Concurrent Schedule
Serializability
serial schedule Conflict Serializability
Serializability
Serial schedules preserve consistency as we assume each View Serializability
transaction individually preserves consistency
The database system must control concurrent execution of

transactions to ensure that the database state remains
consistent
Since the modifications are done in the local buffer, we can

ignore the operations other than Read and Write instructions
for easier understanding of the serializability
20.9
Serializability...
T1 T2 T1 T2
Read(A); Read(A); Schedules
Serial Schedule
Write(A); Write(A); Concurrent Schedule
Read(B); Read(B);
Serializability
Write(B); Write(B); Conflict Serializability
Read(A); Read(A); Testing for Conflict
Write(A); Write(A); Serializability
Read(B); Read(B);
Write(B); Write(B);
Schedule1 Schedule2
T1 T2 T1 T2 T1 T2
Read(A); Read(A); Read(A);
Write(A); Read(A); Write(A);
Read(A); Write(A); Read(A);
Write(A); Read(B); Read(B);
Read(B); Write(A); Write(A);
Write(B); Read(B); Read(B);
Read(B); Write(B) Write(B);
Write(B); Write(B); Write(B);
Schedule3 Schedule4 Schedule5
20.10
Conflict Serializability consists of conflicting operations
Schedules
Let us consider a schedule S in which there are two Serial Schedule
consecutive instructions, Ii and Ij of transactions Ti and Tj Concurrent Schedule
Serializability
respectively (i6=j) Conflict Serializability
Serializability
If Ii and Ij access different data items, then we can swap Ii and View Serializability
Ij without affecting the results of any transactions in the

schedule. However, if Ii and Ij access the same data item Q,
then the order of the two instructions may matter:
• Case-1: Ii =Read(Q) and Ij =Read(Q):
• Order of Ii and Ij does not matter
• Case-2: Ii =Read(Q) and Ij =Write(Q):
• Order of Ii and Ij matters in a schedule
• Case-3: Ii =Write(Q) and Ij =Read(Q):
• Case-1: Ii =Write(Q) and Ij =Write(Q):
20.11
Conflict Serializability...
Thus, Ii and Ij conflict if they are the instructions by different Schedules
transactions on the same data item, and at least one of these Serial Schedule
Concurrent Schedule
instructions is a write operation Serializability

Let Ii and Ij be consecutive instructions of a schedule S. If Ii Serializability
and Ij are instructions of different transactions and they do not
conflict, then we can swap the order of Ii and Ij to produce a
new schedule S’. Here, we expect S to be equivalent to S’
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
A concurrent schedule S is conflict serializable if it is

conflict equivalent to a serial schedule
20.12
Schedules
Serial Schedule
Concurrent Schedule
Serializability
T1 T2 T1 T2 T1 T2 Testing for Conflict
Serializability
Read(A); Read(A); Read(A); View Serializability
Write(A); Read(A); Write(A);
Read(B); Write(A); Read(B);
Write(B); Write(A); Read(A);
Read(A); Read(B); Write(A);
Write(A); Read(B); Read(B);
Read(B); Write(B) Write(B);
Write(B); Write(B); Write(B);
Schedule3 Schedule4 Schedule5
20.13
It is possible to have two schedules that produce the same
outcome, but that are not conflict equivalent
T1 T5
Schedules
Read(A); Serial Schedule
A:=A-100; Concurrent Schedule
Write(A); Serializability
Read(B); Conflict Serializability
B:=B-200; Testing for Conflict
Serializability
Write(B);
Read(B);
B:=B+100;
Write(B);
Read(A);
A:=A+200;
Write(A);
Schedule6
T1 T5
Read(A);
Write(A);
Read(B);
Write(B);
Read(B);
Write(B);
Read(A);
Write(A);
Schedule6
20.14
Testing for Conflict Serializability
Testing for Conflict Serializability Concurrent Execution
Schedules
Construct a directed graph, called a precedence graph from S. Serial Schedule
Concurrent Schedule
This graph consists of a pair G = (V, E), where V is a set of Serializability
vertices and E is a set of edges Conflict Serializability
Serializability
The set of vertices consists of all the transactions participating
in the schedule
The set of edges consists of all edges Ti → Tj for which one of

three conditions holds:
• Ti executes write(Q) before Tj executes read(Q)
• Ti executes read(Q) before Tj executes write(Q)
• Ti executes write(Q) before Tj executes write(Q)
If an edge Ti → Tj exists in the precedence graph, then in any
serial schedule S’ equivalent to S, Ti must appear before Tj
20.15
Testing for Conflict Serializability...
If the precedence graph for a concurrent schedule S has a
cycle, then that schedule is not conflict serializable. If the
graph contains no cycles, then the schedule S is conflict
Schedules
serializable Serial Schedule
Concurrent Schedule
Serializability
Serializability
20.16
The schedules S and S1 are said to be view equivalent if the Schedules

Serial Schedule
following three conditions are met: Concurrent Schedule
• For each data item Q, if transaction Ti reads the initial Serializability

value of Q in schedule S, then it must also read the initial Testing for Conflict
Serializability
value of Q in schedule S1 View Serializability
• For each data item Q, the transaction that performs the

final Write(Q) operation in schedule S must also perform
the final Write(Q) operation in schedule S1
• For each data item Q, if transaction Ti executes Read(Q)
in schedule S, and if that value was produced by a
Write(Q) operation executed by transaction Tj ; then in
schedule S1 , the Read(Q) operation of Ti must also read
the value of Q that was produced by the same Write(Q)
operation of transaction Tj
A schedule S is view serializable if it is view equivalent to
a serial schedule
20.17
View Serializability...
Schedules
T1 T2 T3 Serial Schedule
Concurrent Schedule
Read(Q);
Serializability
Schedule7 Write(Q); Conflict Serializability
Write(Q); Testing for Conflict
Serializability
Write(Q); View Serializability
• This schedule is view serializable

• This schedule is not conflict serializable
• Every conflict serializable schedule is also view
serializable, whereas all view serializable schedules are
not conflict serializable
• Every view serializable schedule, which is not conflict
serializable, has blind writes
20.18

Database Management System 20: Concurrent Execution

Uploaded by

Copyright:

Available Formats

Database Management System 20: Concurrent Execution

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Database Management System 20: Concurrent Execution

Uploaded by

Copyright:

Available Formats

Concurrent Execution

Database Management Concurrent Execution

System 20 Serial Schedule

Concurrent Execution Conflict Serializability

The advantages of using concurrent execution of transactions

Write(A); Testing for Conflict

Read(B); View Serializability

T2 transfers 20% of balance from account A to account B

in which instructions of concurrent transactions are executed View Serializability

A schedule for a set of transactions must consist of all

We must preserve the order in which the instructions appear in

There is no interleaving of transaction operations. A serial

For n transactions, there are exactly n! different serial

Concurrent Schedule Concurrent Execution

transactions are interleaved Concurrent Schedule

much larger than n! View Serializability

A concurrent schedule is serializable if it is equivalent to a Concurrent Schedule

Serial schedules preserve consistency as we assume each View Serializability

transaction individually preserves consistency

The database system must control concurrent execution of

Since the modifications are done in the local buffer, we can

consecutive instructions, Ii and Ij of transactions Ti and Tj Concurrent Schedule

Ij without affecting the results of any transactions in the

instructions is a write operation Serializability

If a schedule S can be transformed into a schedule S’ by a

A concurrent schedule S is conflict serializable if it is

Testing for Conflict Serializability Concurrent Execution

The set of edges consists of all edges Ti → Tj for which one of

The schedules S and S1 are said to be view equivalent if the Schedules

• For each data item Q, if transaction Ti reads the initial Serializability

• For each data item Q, the transaction that performs the

• This schedule is view serializable

You might also like