## TOPICS (Click to Navigate)

`  I request GUEST WRITERS for this web site. Anyone interested please contact me at saravu2k2013@gmail.com Thanks  `
Showing posts with label Serializability. Show all posts
Showing posts with label Serializability. Show all posts

## 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

## 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]

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

### Simple introduction to Naive Bayes classifier

Simple introduction to Naive Bayes classifier What is Naive Bayes Classifier? A Naive Bayes classifier is a probabilistic classifier ...