Minimal Cover
Functional Dependencies
Functional Dependency
A -> B
B is functionally dependent on A (or)
A functionally determines B
Eg : Customer_Id -> Customer_Name
Customer_Name is identified by Customer_Id.
i.e Customer_Name is functionally dependent on
Customer_Id.
Steps to Find Minimal Cover
Singleton attributes in Right Hand Side [RHS]
Identify Extraneous Attributes and remove it
Remove redundant dependencies
Singleton in RHS
AB -> CD
The above functional dependency should be
decomposed to singleton attributes in the RHS as
below.
AB -> C and
AB -> D
Attribute Closure
Example 1: Attribute Closure for one key attribute
Consider the Functional Dependencies for R(A, B, C)
A -> B
B -> C
A+ = Step1: AB [Since A -> B]
Step 2: ABC [Since B -> C]
B+ = Step1: BC [Since B -> C]
So,
A+ = ABC
B+ = BC
Note: If an attribute closure gives all the Attributes in the given
relation, that attribute will be a Candidate Key.
From the given set of functional dependencies,
A is a Candidate Key.
Attribute Closure
Example 2 : Attribute Closure for more than one
key attribute.
Consider the Functional Dependencies for R(A, B,
C,D,E,F) AB +
= ABCDE [Since AB->C, B->D, AD-
>E]
AB -> C
AD -> E AD+ = ADE [Since AD->E]
B -> D
AF -> B B+
= BCD [Since B->C, B->D]
B -> C
AF+ = AFBCDE [Since AF->B, B->C,B->D,
AB->C, AD->E]
From the given set of functional dependencies, AF is a
Candidate Key.
Attribute Closure
Example 3: Key Attribute closure without candidate
Key
Consider the Functional Dependencies for R(A, B, C,D,E)
A+ = ACB [Since A->C, C->B]
A -> C C+ = CB [Since C->B]
D+ = DE [Since D->E]
C-> B Since none of the key attribute closure have
D -> E issued all the attributes, try finding some other
closure by combining the key attributes which
may issue all the attributes in the
AD+ = ADCEB [Since A->C, D->E, C->B]
From the given set of functional dependencies, AD is a
Candidate Key.
Attribute Closure
Example 4: Key Attribute closure without candidate Key
Consider the Functional Dependencies for R(A, B, C,D,E)
A+ = AB [Since A->B]
C+ = CD [Since C->D]
A -> B BC+ = BCED [Since BC->E, C->D]
Since none of the key attribute closure have
C-> D issued all the attributes, try finding some other
BC -> E closure by combining the key attributes which
may issue all the attributes in the
AC+ = ACBDE [Since A->B, C->D, BC->E]
From the given set of functional dependencies, AC is a
Candidate Key.
Extraneous Attributes
If an attribute doesn’t any meaning to the functional dependency, we
say it is extraneous and remove it
Consider the functional dependencies
If an LHS has more than one attribute, check whether
there exists an extraneous (Extra/Unwanted) attribute. If
A -> B so, remove it.
AB -> C LHS which have 2 attributes is AB -> C
D -> AC A+ = ABC [Since A->B, AB-> C]
D -> E B+ = B [Reflexivity]
If an attribute Closure gives only its own attribute by
satisfying Reflexivity, that attribute in the functional
dependency is Extraneous.
So, B is Extraneous in AB-> C Implies A->C
New FDs are A->B, A->C, D-AC, D->E
Finding Redundancy Dependency and Minimal
Cover – Ex 1
New FDs 1. Remove A->B and find the attribute closure for A
A->B A+ = AC [Since A->C] – Here if we don’t consider A->B, B
cannot be found in A+. So A->B cannot be a redundant
A->C
dependency.
D-AC
D->E 2. Remove A->C and find the attribute closure for A
A+ = AB [Since A->B] – Here if we don’t consider A->C, C
cannot be found in A+. So A->C cannot be a redundant
dependency.
A->B
A->C 3. Remove D->A and find the attribute closure for D
D->A D+ = DCE [Since D->C, D->E] – Here if we don’t consider D-
D->C >A, A cannot be found in D+. So D->A cannot be a redundant
D->E dependency.
4. Remove D->C and find the attribute closure for D
Applying
D+ = DAEBC [Since D->C, ] – Here if we don’t consider D->C,
Singleton to
Could be found in D+. So D->C is the redundant dependency
RHS
and should be removed.
Finding Redundancy Dependency and Minimal
Cover
A->B 5. Remove D->E and find the attribute closure for D
A->C D+ = DACB [Since D->A, A->C, A->B] – Here if we don’t
consider D->E, E cannot be found in D+. So D->E cannot be a
D->A
redundant dependency.
D->C
D->E So, Minimal Cover will be after removing
a) Extraneous Attributes
A->B b) Redundant Dependencies
A->C
D->A
D->E
Minimal Functional Dependencies are
New FD’s A -> B
after A -> C
removing D -> A
Redundancy D -> E
Finding Redundancy Dependency and
Minimal Cover – Ex 2
Consider the Functional Dependencies
A -> B
B -> C
A -> C
Remove A -> B and find attribute Closure for A
A+ = AC [B is not issued – Not redundant]
Remove B -> C and find attribute Closure for B.
B+ = B [C is not issued – Not redundant]
Remove A -> C and find attribute Closure for A.
A+ = ABC [A->B, B->C. C is issued – So, Redundant]
Final FDs without redundancy are
A->B and B->C
Finding Extraneous, Redundant
Dependency, Minimal Cover
R(A,B,C,D,E)
F = {A->D, BC->AD, C->B, E->A, E->D}
Step1: Singleton RHS
Step2: Remove Extraneous Attribute
Step3: Redundant Dependency
Step1: Singleton RHS
A->D
BC->A
BC->D
C->B
E->A
E->D
Finding Extraneous, Redundant
Dependency, Minimal Cover
Step2: Remove Extraneous Attribute
A->D
Consider BC->A and BC->D
BC->A +
B =B
BC->D +
C =BCAD so B is Extraneous in BC->A and
C->B
BC->D. Remove it.
E->A
E->D
After removing Extraneous in LHS, F =>
A->D
C->A
C->D
C->B
E->A
E->D
Finding Extraneous, Redundant
Dependency, Minimal Cover
Step3: Remove Redundant Dependency
A->D Remove A->D, A+ = A – Not Redundant [D not arrived]
C->A
C->D Remove C->A, C+ = CDB – Not Redundant [A not
C->B arrived]
E->A
Remove C->D, C+ = CABD – Redundant [D arrived]
E->D
New
F= {A->D,
C->A,
C->B,
E->A,
E->D}
Finding Extraneous, Redundant
Dependency, Minimal Cover
Step3: Remove Redundant Dependency
A->D Remove C->B, C+ = CAD – Not Redundant [B not
C->A arrived]
C->B
E->A Remove E->A, E+ = ED – Not Redundant [A not
E->D arrived]
Remove E->D, E+ = EAD – Redundant [D arrived]
Final – Minimal Cover
F= {A->D,
C->A,
C->B,
E->A,}
EC+ = ECADB
Thank You
