Showing posts with label Normalization. Show all posts
Showing posts with label Normalization. Show all posts

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


Monday, 9 April 2018

Find the candidate keys from the given relation for normalization

Find the candidate keys from the given relation for normalization

Question:
Consider a relation with schema R(A,B,C,D) with functional dependencies (FD’s):
BC → A, AD → B, CD → B, AC → D.
Find all the candidate keys of R.
Solution:

Let us find the closure for the left hand side (LHS) attributes of given set of functional dependencies.

Let us take the FD BC A to check whether the LHS BC forms a candidate key or not.

We know
Result =
How?
Description
BC
BC
Given

BC
BCA
BC A
If we know BC, then we can derive A uniquely as per the reflexivity rule, hence result = BCA
BCA
BCAD
AC D
From the previous step we know attribute A, and by the FD AC D the result becomes ABCD which is equal to R. Hence, BC is a candidate key

We derived all the other candidate keys in the same way as stated above and given in the table below;
LHS
Closure
Due to the FDs
Result becomes
Description
(BC)+
BC → A
AC → D
= ABC (Reflexive)
= ABCD (Pseudo-transitive)
The result of (BC)+ is equivalent to R.
Hence BC is a candidate key.
(AD)+
AD B
= ABD (Reflexive)
(AD)+ ≠ R.
Hence AD does not form candidate key.
(CD)+
CD B
BC A
= BCD (Reflexive)
= ABCD (Pseudo-transitive)
(CD)+ is equivalent to R.
Hence CD forms a candidate key.
(AC)+
AC D
AD B
or
CD B
= ACD (Reflexive)
= ABCD (Pseudo-transitive)
(AC)+ = R hence is a candidate key.

BC, AC, and CD are the candidate keys for the given relation.


********

Go to - 1NF,    2NF,    3NF,    BCNF





find the candidate keys
find the keys of a relation
how to find the closure
armstrong's axioms
reflexive rule in database design
normalization solved exercises
normalization solved examples




Important properties of two phase locking protocol and its variants

Important properties of two phase locking protocol and its variants Properties of     2PL Serializability  2PL ensures co...