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.
***********
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