Check for conflict serializability solved example in dbms

Check for conflict serializability solved example in dbms

Question:

Consider a schedule S with two transactions T₁ and T₂ as follows;

S: R₁(x);W₂(x);R₁(x);W₁(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) R(x) W(y) Commit	W(x) Commit

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.

Let us construct a precedence graph;

Ins. 1 and 2: Transaction T₂ executes w(x) after T₁ executed r(x). [These two instructions are conflict]. We insert an edge from T₁ to T₂ as follows;

Ins. 2 and 3: Transaction T₁ executes a r(x) after T₂ executed w(x). [These two are conflicting instructions.] We insert an edge from T₂ to T₁ as follows;

Insertion of new edge forms a cycle. If there is a cycle in the precedence graph, then the schedule cannot be a conflict serializable schedule.

In other words, if you observe the schedule S carefully you can find that neither of the following can occur;

• Instruction 1 cannot be swapped with instruction 2 due to conflict (Read-Write conflict).

• Instruction 2 cannot be swapped with instruction 3 due to conflict (Write-Read conflict)

Hence, the schedule S cannot be serialized.

Schedule S is not conflict serializable schedule.

***********

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