Advanced Database Management System - Tutorials and Notes: How to check whether a schedule is conflict serializable?

## How to check whether a schedule is conflict serializable?

Question:
Consider a schedule S with two transactions T1 and T2 as follows;
S: R1(x);R2(x);W1(y);W2(y);commit1;commit2;
Is the schedule S conflict serializable?

Solution:

The given schedule S is as follows;
 Instruction T1 T2 1 2 3 4 5 6 R(x) W(y) Commit R(x) W(y) Commit

A schedule is conflict serializable if it can be transformed into an equivalent serial schedule by swapping pairs of non-conflicting instructions. Two instructions conflict if they involve the same data item and at least one of them is a WRITE.
Let us construct a precedence graph;
Ins. 1 and 2: R(x) of T1 does not conflict with R(x) of T2 because they both read x and hence not conflict.
Ins. 2 and 3: R(x) of T2 does not conflict with W(y) of T1. Both are not conflicting instructions because T2 and T1 are trying on different data items x and y not same data items.
Ins. 3 and 4: W(y) of T1 conflicts with W(y) of T1. They both try on same data item with conflicting instructions (write-write conflict). Hence we need an edge to be inserted in our precedence graph as follows;
 Precedence graph
There are no more instructions (either read or write). And our graph does not contain a cycle. Hence, we can conclude that the given schedule S is conflict serializable and the serialized schedule will be T1;T2, that is, all instructions from T1 first followed by all instructions from T2.
If we swap all non-conflicting instructions (swap instruction 2 with 3) in our schedule, we shall end up in the following serial schedule S’;

 Instruction T1 T2 1 2 3 4 5 6 R(x) W(y) Commit R(x) W(y) Commit

***********

Conflict serializability solved exercise
conflict serializable schedule example
how to find whether a schedule is conflict serializable or not?
how to check a schedule is serializable or not?
use precedence graph for checking serializability
serializability solved exercise
concurrency and serializability