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 five
transactions T_{1}, T_{2}, T_{3} T_{4} and T_{5}
as follows;
Sl.No.

T_{1}

T_{2}

T_{3}

T_{4}

T_{5}

1

R(x)


2

W(x)


3

R(x)


4

R(y)


5

R(z)


6

W(y)


7

R(v)


8

W(v)


9

R(v)


10

W(y)


11

W(y)


12

W(z)

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 nonconflicting instructions.
Two instructions conflict if
they involve the same data item and at least one of them is a WRITE.

To find whether the given schedule
is conflict serializable or not, we can draw precedence graph. 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
instructions and
the edge to be
inserted

Precedence graph


Sl. No.: 1, 2
R_{1}(x)
and W_{2}(x);
T_{1} → T_{2}

➔


Sl. No.: 4, 6
R_{1}(y) and
W_{2}(y);
T_{1} → T_{2}

➔


Sl. No.: 7, 8
R_{1}(v) and
W_{3}(v);
T_{1} → T_{3}

➔


Sl. No.: 8, 9
W_{3}(v) and
R_{4}(v);
T_{3} →
T_{4}

➔


Sl. No.: 6, 10
W_{2}(y) and
W_{4}(y);
T_{2} → T_{4}

➔


Sl. No.: 10, 11
W_{4}(y) and
W_{5}(y);
T_{4} → T_{5}

➔


Sl. No.: 5, 12
R_{4}(z) and
W_{5}(z);
T_{4} → T_{5}

➔


Sl. No.: 4, 11
R_{1}(y) and
W_{5}(y);
T_{1} → T_{5}

➔


Sl. No.: 6, 11
W_{2}(y) and
W_{5}(y);
T_{2} → T_{5}

➔


Sl. No.: 4, 10
R_{1}(y) and
W_{4}(y);
T_{1} → T_{4}

➔


Sl. No.: 2, 3
W_{2}(x) and
R_{3}(x);
T_{2} → T_{3}

➔

As per the complete (last one) precedence graph, there
exists no cycles. Hence, the given schedule S is conflict serializable.
***********
Go to Define Serializability 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
No comments:
Post a Comment