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

Saturday, 14 April 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

Tuesday, 21 November 2017

Testing for conflict serializablity using precedence graph

How to test for conflict serializability of a schedule? Testing conflict serializability using precedence graph, How to draw a precedence graph, What is precedence graph, testing conflict serializability examples


Testing for conflict serializability

Whether a schedule is conflict serializable or not can be determined using a directed graph called precedence graph.
What is precedence graph? It is a directed graph (also called as serialization graph) G with set of nodes N (T1, T2, T3, …, Tn) and set of directed edges E (E1, E2, ..., Em).

  • the set of nodes N = the transactions of a schedule S that are trying to access same data item.
  • the set of edges E = the set of directed links between two nodes (transactions).

How to construct precedence graph?

Nodes
The total numbers of transactions in a schedule S will be the number of nodes in the precedence graph. For example, if the schedule S has three transactions, then there will be three nodes in the precedence graph.
Edges
An edge is a directed link between two different transactions Ti and Tj and will look something like Ti à Tj. Only tricky point here is that the link head (arrow) will be included if one of the following is True;
  • Create a directed edge Ti → Tj, if Tj reads the value of an item Q written by Ti. [Read-Write conflict]
  • Create a directed edge Ti → Tj, if Tj writes a value into an item Q after it has been read by Ti. [Write-Read conflict]
  • Create a directed edge Ti → Tj, if Tj writes a value into an item Q after it has been written by Ti. [Write-Write conflict]




Example 1
Let us construct the precedence graph for the schedule S given below;
Time
Transaction T1
Transaction T2
1
2
3
4
5
6
7
8
9
10
11
12
13
read(A);
A := A – 50;
write(A);
read(B);
B := B + 50;
write(B);






read(A);
temp := A * 0.1;
A := A – temp;
write(A);
read(B);
B := B + temp;
write(B);
We have two transactions, hence two nodes namely, T1 and T2 [see figure 1(a)].

Figure 1 - Construction of precedence graph for example 1
A Write(A) instruction (instruction 3) of T1 comes before Read(A) instruction (instruction 7) of T2. That is, T2 reads A that was written by T1. Here, instruction of T1 happens first then T2. So include an edge from T1 to T2 (Green color) [see figure 1(b)].
A Write(B) instruction (instruction 6) of T1 comes before Read(B) instruction (instruction 11) of T2. That is, T2 reads B that was written by T1. Here, instruction of T1 happens first then T2. So include an edge from T1 to T2 (Blue color) [see figure 1(c)].
In the precedence graph, both the edges are directed towards T2. Hence, the final graph is the one given in figure 1(d).

How do we conclude whether schedule S is conflict serializable or not?
Very simple.

  • If your precedence graph has no cycle, then the schedule is conflict serializable.
  • If your precedence graph has formed a cycle, then the schedule is not conflict serializable.
Our precedence graph above has no cycle in it. Hence, schedule S is conflict serializable and the serial order is T1-T2. That is, concurrent schedule S is equivalent to a serial schedule T1-T2.

Example 2
Is the following schedule S serializable or not?
Time
Transaction T1
Transaction T2
1
2
3
4
5
6
7
8
9
10
11
12
read(A);
A := A – 50;





write(A);
read(B);
B := B + 50;
write(B);



read(A);
temp := A * 0.1;
A := A – temp;
write(A);
read(B);




B := B + temp;
write(B);
We have two transactions in schedule S, so two nodes in the precedence graph as follows [see figure 2(a)];
Figure 2 - Construction of precedence graph for example 2
T1 reads A before T2 writes A. Hence include an edge from T1 to T2 (Green color) [figure 2(b)].
T2 reads B before T1 writes B. Hence include an edge from T2 to T1 (Red color) [figure 2(c)].
Observe from the figure that a cycle has formed. Hence the schedule S is not conflict serializable.
[You can include edges for the other conflicts also. An edge from T2 to T1 for write A of T2 comes before write A of T1. Another edge from T1 to T2 for write B of T1 occurs before write B of T2. Anyhow, we have included the edges already. So, no need to specify for multiple times]

*******************










Lossless join decomposition one more example

Lossless Join Decomposition Question: Let R = {ssn, ename, pnumber, pname, plocation, hours} and R is decomposed into three re...