Showing posts with label Serializability. Show all posts
Showing posts with label Serializability. Show all posts

Wednesday, April 1, 2020

Given schedule is conflict serializable or not - exercise

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:
Consider a schedule S with two transactions T1, T2, T3 and T4 as follows;
S: R2(x); W3(x); W1(x); W2(y); R2(y); R4(x); R4(y);
Is the schedule S conflict serializable?

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.

The schedule S given in questions is as follows;
Instruction
T1
T2
T3
T4
1
2
3
4
5
6
7


W(x)

R(x)


W(y)
R(Z)

W(x)









R(x)
R(y)

We can construct a precedence graph to decide whether the given schedule is conflict serializable or not.
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.

Conflicting instruction and
the edge to be inserted
   
Precedence graph
R2(x) and W3(x);
T2 → T3


R2(X) and W1(X);
T2 → T1


W3(X) and W1(X);
T3 → T1


W3(X) and R4(X);
T3 → T4


W1(X) and R4(X);
T1 → T4


W2(Y) and R4(Y);
T2 → T4


From the precedence graph, it is clear that no cycle has been formed through the conflicting instructions. Hence, the schedule is a 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




Saturday, April 14, 2018

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 T1 and T2 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 T1 does not conflict with R(x) of T2 because they both read x and hence not conflict.
Ins. 2 and 3: R(x) of T2 does not conflict with W(y) of T1. Both are not conflicting instructions because T2 and T1 are trying on different data items x and y not same data items.
Ins. 3 and 4: W(y) of T1 conflicts with W(y) of T1. 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 T1;T2, that is, all instructions from T1 first followed by all instructions from T2.
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

***********








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

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

data recovery