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

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




Thursday, 29 March 2018

Find whether the given decomposition is Lossless or lossy decomposition

Find whether the given decomposition is Lossless or lossy decomposition


Question:

Suppose you are given a relation R(A,B,C,D). let us assume that set of functional dependencies F = { B → C, D → A} and R is decomposed into R1(B,C), and R2(A,D).
(a) Find the candidate key(s) for R. (b) State whether or not the proposed decomposition of R into smaller relations is a good decomposition and briefly explain why or why not.

Solution:

a) To find the candidate keys, we have to find the closure of attributes of LHS (left hand side) of all functional dependencies. If the closure includes all the attributes of the given relation, then that attribute (or set of attributes) is the candidate key.
B+ = BC. It does not include all attributes of R.
D+ = DA. It does not include all attributes of R.
(BD)+ = BCDA. It includes all attributes of R, hence BD is the candidate key.

b) The decomposition of R into R1 and R2 is lossy because there is no common attribute between R1 and R2 (R1∩R2 = ). Hence, the join of R1 and R2 will result in Cartesian product of these two relations which is not the base relation R.

***********







Normalization exercises
Decompose given relation
Find whether the decomposition is lossless or lossy
lossless join decomposition exercises
lossy join decomposition exercises



Saturday, 24 February 2018

Find minimal cover/canonical cover in a set of FDs

Find minimal cover/canonical cover in a set of given functional dependencies


Question:
For a relation schema R = (A, B, C, D, E), consider the following set of functional dependencies;
F = {A BC, CD E, B D, E A}
Using the functional dependencies compute the canonical cover Fc.

Solution:
Minimal cover:
Definition 1:
A minimal cover of a set of FDs F is a minimal set of functional dependencies Fmin that is equivalent to F. There can be many such minimal covers for a set of functional dependencies F.
Definition 2:
A set of FDs F is minimum if F has as few FDs as any equivalent set of FDs.


Follow these steps to find the canonical (minimal) cover;
1. Decompose each functional dependency in F to have singleton (single) attribute on the Right Hand Side (RHS).
2. Remove extraneous (redundant) attributes from Left Hand Side of each functional dependency.
[What is extraneous attribute? Refer here].
3. Find and eliminate redundant functional dependencies.

Let us apply the above said properties to F;
F = {A BC, CD E, B D, E A}

1. RHS of all functional dependencies should be singleton. To achieve this we decompose each functional dependency that has two or more attributes in their RHS. We get the following set of functional dependencies F1;
F1 = {A B, A C, CD E, B D, E A}

2. Remove extraneous (redundant) attributes. This is applicable only for those functional dependencies that have two or more attributes on its LHS.
We need to check whether or not an attribute/set of attributes of LHS of a functional dependency is redundant or not. For checking this, we have to find the closure of each individual LHS attribute of each FD that has two or more LHS attributes.
With this property we have only one FD, CD E. We need to check whether C alone or E alone can find E uniquely.
C+ = C by reflexivity rule
D+ = D by reflexivity rule
From this we found that either C or D alone cannot determine the value of E. Hence, the FD CD E does not have any extraneous attributes.
Hence, our F1 is as follows;
F1 = {A B, A C, CD E, B D, E A}

3. Eliminate redundant functional dependencies.
To find redundant FDs, we have to find whether the RHS of a FD can be determined using other FDs.
(i) Let us check first for FD, A B. To proceed, we forget , A B from F, and use only the remaining FDs A C, CD E, B D, E A of F. That is our F becomes F1 = {A C, CD E, B D, E A}
No FD have B on RHS. Hence, A B is not redundant.
(ii) Now check for A → C. can we find C using following FDs?
F1 = {A B, CD E, B D, E A}
A+ = ABD
B+ = BD
We are not able to determine C using F1. Hence, A C is not redundant.
If we repeat this for each FD in F, we found that none of them are redundant.

Hence our Fc is as follows;
Fc = {A → BC, CD → E, B → D, E → A} which is same as F in the question.

***********


Similar topics

How to find closure of set of functional dependencies?

How to find closure of attributes?

How to find canonical cover for a set of functional dependencies?

How to find extraneous attribute?




Go back to Question/QUIZ page




find canonical cover of F
what is minimal cover? how to find minimal cover
minimal cover solved exercise
find extraneous attributes
 





SQL exercises for beginners one

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