Please visit, subscribe and share 10 Minutes Lectures in Computer Science

## Conflict Serializable Schedule - Solved Exercise

Question:
Consider a schedule S with five transactions T1, T2, T3 T4 and T5 as follows;
 Sl.No. T1 T2 T3 T4 T5 1 R(x) 2 W(x) 3 R(x) 4 R(y) 5 R(z) 6 W(y) 7 R(v) 8 W(v) 9 R(v) 10 W(y) 11 W(y) 12 W(z)

### Is the schedule S conflict serializable?

Solution:
 Conflict serializable schedule: 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.
To find whether the given schedule is conflict serializable or not, we can draw precedence graph. Precedence graph can be constructed by carefully analyzing the conflicting instructions. For every conflicting instruction, an edge can be inserted into the precedence graph. At the end, if the graph has not formed a cycle, then we would say that the schedule S is conflict serializable, otherwise not.

 Conflicting instructions and the edge to be inserted Precedence graph Sl. No.: 1, 2 R1(x) and W2(x); T1 → T2 ➔ Sl. No.: 4, 6 R1(y) and W2(y); T1 → T2 ➔ Sl. No.: 7, 8 R1(v) and W3(v); T1 → T3 ➔ Sl. No.: 8, 9 W3(v) and R4(v); T3 → T4 ➔ Sl. No.: 6, 10 W2(y) and W4(y); T2 → T4 ➔ Sl. No.: 10, 11 W4(y) and W5(y); T4 → T5 ➔ Sl. No.: 5, 12 R4(z) and W5(z); T4 → T5 ➔ Sl. No.: 4, 11 R1(y) and W5(y); T1 → T5 ➔ Sl. No.: 6, 11 W2(y) and W5(y); T2 → T5 ➔ Sl. No.: 4, 10 R1(y) and W4(y); T1 → T4 ➔ Sl. No.: 2, 3 W2(x) and R3(x); T2 → T3 ➔
As per the complete (last one) precedence graph, there exists no cycles. Hence, the given schedule S is conflict serializable.

***********

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