How to test for conflict serializability of a schedule? Testing conflict serializability using precedence graph, How to draw a precedence graph, What is precedence graph, testing conflict serializability examples
Testing for conflict serializability
Whether a schedule is conflict
serializable or not can be determined using a directed graph called precedence
graph.
What is precedence graph? It is a
directed graph (also called as serialization graph) G with set of nodes N (T1,
T2, T3, …, Tn) and set of directed edges E (E1,
E2, ..., Em).
- the set of nodes N = the transactions of a schedule S that are trying to access same data item.
- the set of edges E = the set of directed links between two nodes (transactions).
How to construct precedence graph?
Nodes
The total numbers of transactions in
a schedule S will be the number of nodes in the precedence graph. For example,
if the schedule S has three transactions, then there will be three nodes in the
precedence graph.
Edges
An edge is a directed link between
two different transactions Ti and Tj and will look
something like Ti à Tj. Only tricky point
here is that the link head (arrow) will be included if one of the following is
True;
- Create a directed edge Ti → Tj, if Tj reads the value of an item Q written by Ti. [Read-Write conflict]
- Create a directed edge Ti → Tj, if Tj writes a value into an item Q after it has been read by Ti. [Write-Read conflict]
- Create a directed edge Ti → Tj, if Tj writes a value into an item Q after it has been written by Ti. [Write-Write conflict]
Example
1
Let us construct the precedence
graph for the schedule S given below;
Time
|
Transaction T1
|
Transaction T2
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
read(A);
A := A – 50;
write(A);
read(B);
B := B + 50;
write(B);
|
read(A);
temp := A * 0.1;
A := A – temp;
write(A);
read(B);
B := B + temp;
write(B);
|
We have two transactions, hence two
nodes namely, T1 and T2 [see figure 1(a)].
A Write(A) instruction
(instruction 3) of T1 comes before Read(A) instruction (instruction 7)
of T2. That is, T2 reads A that was written by T1. Here, instruction of T1
happens first then T2. So include an edge from T1 to T2 (Green color) [see figure 1(b)].
A Write(B) instruction
(instruction 6) of T1 comes before Read(B) instruction (instruction 11)
of T2. That is, T2 reads B that was written by T1. Here, instruction of T1
happens first then T2. So include an edge from T1 to T2 (Blue color) [see figure 1(c)].
In the precedence graph, both the
edges are directed towards T2. Hence, the final graph is the one given in figure 1(d).
How do we conclude whether schedule
S is conflict serializable or not?
Very simple.
- If your precedence graph has no cycle, then the schedule is conflict serializable.
- If your precedence graph has formed a cycle, then the schedule is not conflict serializable.
Our precedence graph above has no
cycle in it. Hence, schedule S is conflict serializable and the serial order is
T1-T2. That is, concurrent schedule S is equivalent to a serial schedule T1-T2.
Example 2
Is the following schedule S serializable
or not?
Time
|
Transaction
T1
|
Transaction
T2
|
1
2
3
4
5
6
7
8
9
10
11
12
|
read(A);
A := A – 50;
write(A);
read(B);
B := B + 50;
write(B);
|
read(A);
temp := A * 0.1;
A := A – temp;
write(A);
read(B);
B := B + temp;
write(B);
|
We have two transactions in schedule
S, so two nodes in the precedence graph as follows [see figure 2(a)];
T1 reads A before T2 writes A. Hence
include an edge from T1 to T2 (Green color) [figure 2(b)].
T2 reads B before T1 writes B. Hence
include an edge from T2 to T1 (Red color) [figure 2(c)].
Observe from the figure that a cycle has
formed. Hence the schedule S is not conflict serializable.
[You can include edges for the other
conflicts also. An edge from T2 to T1 for write A of T2 comes before write A of
T1. Another edge from T1 to T2 for write B of T1 occurs before write B of T2. Anyhow,
we have included the edges already. So, no need to specify for multiple times]
*******************
Go to Conflict serializability page
Go to Transactions management in DBMS page