Showing posts with label Solved Exercises. Show all posts
Showing posts with label Solved Exercises. Show all posts

Monday, 16 April 2018

Check for conflict serializability solved example in dbms

Check for conflict serializability solved example in dbms

Question:
Consider a schedule S with two transactions T1 and T2 as follows;
S: R1(x);W2(x);R1(x);W1(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)

R(x)
W(y)
Commit

W(x)



Commit

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.

Let us construct a precedence graph;
Ins. 1 and 2: Transaction T2 executes w(x) after T1 executed r(x). [These two instructions are conflict]. We insert an edge from T1 to T2 as follows;

Ins. 2 and 3: Transaction T1 executes a r(x) after T2 executed w(x). [These two are conflicting instructions.] We insert an edge from T2 to T1 as follows;

Insertion of new edge forms a cycle. If there is a cycle in the precedence graph, then the schedule cannot be a conflict serializable schedule.

In other words, if you observe the schedule S carefully you can find that neither of the following can occur;
  • Instruction 1 cannot be swapped with instruction 2 due to conflict (Read-Write conflict).
  • Instruction 2 cannot be swapped with instruction 3 due to conflict (Write-Read conflict)
Hence, the schedule S cannot be serialized.
Schedule S is not 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, 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

Thursday, 12 April 2018

Lossless join decomposition solved example in normalization

Lossless join decomposition solved example in normalization

Question:

Consider a relation R(A, B, C, D) with the set of functional dependencies F = {AB C, BC D, CD A}. Assume that R is decomposed into R1(A, B, C) and R2(A, C, D). Find whether the given decomposition is lossless or not.

Solution:

Lossless join decomposition implies that the result of joining all the decomposed relations will create the base relation again without any loss/gain in data.
If one of the following is true, then the decomposition is said to be lossless;

  • (R1 ∩ R2) R1
  • (R1 ∩ R2) R2
If we apply intersection between R1 and R2, we shall get,
(R1 ∩ R2) = {A, B, C} ∩ {A, C, D} = AC.
There is no functional dependency in F such that the AC is alone on the left hand side. Hence, this decomposition is lossless.

Example:

Let us populate R with sample data and try the experiment;

A
B
C
D
a1
a2
a3
a4
a1
a4
a3
a2

According to the decomposition, we shall get R1 and R2 as follows;

R1
A
B
C
a1
a2
a3
a1
a4
a3

R2
A
C
D
a1
a3
a4
a1
a3
a2

Join back R1 and R2 must result in R if the decomposition is lossless.
 
R1
R2
=
R’

A
B
C
a1
a2
a3
a1
a4
a3



A
C
D
a1
a3
a4
a1
a3
a2


=

A
B
C
D
a1
a2
a3
a4
a1
a2
a3
a2
a1
a4
a3
a2
a1
a4
a3
a4

R’ is the result of natural join of R1 and R2, and R’ is not equal to R the base relation. Hence, the decomposition is not lossless join decomposition.

***********





 



Normalization solved examples
normalization exercises solved
what is lossless decomposition
rules for lossless join decomposition
lossless decomposition example
how to find whether a decomposition is lossless or not


SQL exercises for beginners one

SQL Exercises for Beginners / Simple SQL Exercises with Answers / Solved SQL exercises / SQL solved exercises with simple conditions / So...