Search This Blog

Tuesday, 21 November 2017

Testing for conflict serializablity using precedence graph

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)].

Figure 1 - Construction of precedence graph for example 1
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)];
Figure 2 - Construction of precedence graph for example 2
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]

*******************










Followers