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

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents