Schedules that are conflict serializable - solved examples

Given schedule is conflict serializable or not exercise, Conflict serializability exercise, how to find whether a schedule is conflict serializable? conflict serializability example

 

Conflict Serializable Schedule - Solved Exercise

Question:

For the following schedule S, draw the precedence graph and decide if the schedule is conflict serializable.

r2(Y), w2(Y), r3(Y), r1(X), w1(X), w3(Y), r2(X), r1(Y), w1(Y)

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.

 

Is the schedule a conflict serializable schedule?

NO. The precedence graph of S consists of a cycle.

The precedence graph consists of the following edges (conflicting instructions) and a cycle;

• T₂ to T₃ – W₂(Y), and R₃(Y) are the conflicting instructions causes this edge.

• T₁ to T₂ – W₁(X), and R₂(X) are the conflicting instructions causes this edge.

• T₃ to T₁ – W₃(Y), and W₁(Y) are the conflicting instructions causes this edge.

These three edges together formed a cycle. There is one more edge as follows;

• T₂ to T₁ – W₂(Y), and R₁(Y) are the conflicting instructions causes this edge.

 

As per the precedence graph, the schedule S has cycle in it. Hence, the schedule S is not conflict serializable.

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

 

Go to Define Serializability page

Go to Conflict Serializability explained with example page

Go to Solved exercises in DBMS page

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