Monday, 16 April 2018

Check for conflict serializability solved example in dbms

Check for conflict serializability solved example in dbms

Question:
Consider a schedule S with two transactions T1 and T2 as follows;
S: R1(x);W2(x);R1(x);W1(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 T2 executes w(x) after T1 executed r(x). [These two instructions are conflict]. We insert an edge from T1 to T2 as follows;

Ins. 2 and 3: Transaction T1 executes a r(x) after T2 executed w(x). [These two are conflicting instructions.] We insert an edge from T2 to T1 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.

***********









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

No comments:

Post a Comment

SQL exercises for beginners one

SQL Exercises for Beginners / Simple SQL Exercises with Answers / Solved SQL exercises / SQL solved exercises with simple conditions / So...