Testing for conflict serializability

A schedule is serializable or not, we need to test it. Now I show you how to easily determine conflict serializability of any schedule. To do this at first we need to clear understand about precedence graph. We know a graph consists of a pair G=(V,E), where V is a set of vertices and E is a set of edges. In this precedence  graph

V= V means vertices, all transaction in a schedule consider as a vertices such that T1 and T2 is two vertices for a schedule S.

E= E is edge, an edge consists T1 to T2 if the schedule fulfill the three condition :

              1. T1 executes write (A) before T2 executes read (A)

              2. T1 executes read (A) before T2 executes write (A)

              3. T1 executes write (A) before T2 executes write (A)

Now consider the following picture. In that picture we see there are three schedule S1, S2 and S3.

At first we sketch precedence graph for S1. S1 has two vertices T1 and T2 and also has one edge  T1 to T2 because all the instructions of T1 are executed before the first instruction of T2 is executed.

Secondly we sketch precedence graph for S2. S2 has two vertices T2 and T1 and also has one edge T2 to T1 because all the instructions of T2 are executed before the first instruction of T1 is executed. So the graph is:

Thirdly we sketch precedence graph for S3. S3 has two vertices T1 and T2. It contains the edge T1 -> T2 because T1 executes read (A) before T2 executes write (A). It also contains the edge T2 -> T1 because T2 executes read (B) before T1 executes write (B). So the precedence graph is :

If the precedence graph has any cycle, then the schedule is not conflict serializable. If the graph contains no cycles, then the schedule is conflict serializable. In our example schedule S1 and S2 are conflict serializable but S3 is not conflict serializable.

Testing for view serializability is rather complicated because there exists no efficient algorithm to test for view serializability.