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 T₁ and T₂ 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 T₁ does not conflict with R(x) of T₂ because they both read x and hence not conflict.

Ins. 2 and 3: R(x) of T₂ does not conflict with W(y) of T₁. Both are not conflicting instructions because T₂ and T₁ are trying on different data items x and y not same data items.

Ins. 3 and 4: W(y) of T₁ conflicts with W(y) of T₁. 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 T₁;T₂, that is, all instructions from T₁ first followed by all instructions from T₂.

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

***********

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