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 F_{c}.
Solution:
Minimal cover:
Definition 1:
A minimal cover
of a set of FDs F is a minimal set of functional dependencies F_{min}
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.

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].
[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
Go back to Online Quizzes home page
find canonical cover of F
what is minimal cover? how to find minimal cover
minimal cover solved exercise
find extraneous attributes
No comments:
Post a Comment