Tuesday, November 21, 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]

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










5 comments:

  1. This comment has been removed by a blog administrator.

    ReplyDelete
  2. This comment has been removed by a blog administrator.

    ReplyDelete
  3. Draw the precedence graph for the following expression:

    S1: x:=0
    S2: x:=x+1
    S3: y:=2
    S4: z:=y
    S5: x:x+2
    S6: y:=x+z
    S7: z:=4


    Please ans this question
    And also explain it please.

    ReplyDelete

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery