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 (T₁, T₂, T₃, …, T_n) and set of directed edges E (E₁, E₂, ..., E_m).

• 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 T_i and T_j and will look something like T_i à T_j. Only tricky point here is that the link head (arrow) will be included if one of the following is True;

• Create a directed edge T_i → T_j, if T_j reads the value of an item Q written by T_i. [Read-Write conflict]

• Create a directed edge T_i → T_j, if T_j writes a value into an item Q after it has been read by T_i. [Write-Read conflict]

• Create a directed edge T_i → T_j, if T_j writes a value into an item Q after it has been written by T_i. [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]

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

Go to Conflict serializability page

Go to Transactions management in DBMS page