# Functional Dependency Solving Algorithm for Minimal Cover

• Comp Sci
• chopnhack
In summary, after reducing RHS into singletons, reducing LHS redundant attributes, and removing redundant functional dependencies, the minimal set of functional dependencies for F is {AB->C, C->A, BC->D, D->E, D->G, BE->C, CG->B, CE->G}. It is not possible to further refine this solution set.
chopnhack
Homework Statement
Solve the minimal cover of F={AB-->C, C-->A, BC-->D, ACD-->B, D-->EG, BE-->C, CG-->BD, CE-->G}
Relevant Equations
1st - Reduce RHS to singletons
2nd - Reduce LHS redundant attributes where permitted using closure of attributes where desired
attribute is in the closure
3rd - Reduce redundant functional dependencies using closure of attributes
Step 1: Reduce RHS into singletons
F = {AB->C, C->A, BC->D, ACD->B, D->E, D->G, BE->C, CG->B, CG->D, CE->G}
Step 2: Reduce LHS redundant attributes
ACD->B has closure of A: A, C: C,A and D: D,E,G since A is in the closure of C we can remove A from ACD->B making it CD->B no other LHS could be reduced.
Step 3: Remove redundant functional dependencies
ACD closure = ACDEGB since B is in the closure and also in the functional dependency ACD->B , we can remove it from the list of fd's
CG closure = CGBD since D is in the closure and also in the functional dependency CG->D, we can also remove it from the list of fd's

This leaves F'={AB->C, C->A, BC->D, D->E, D->G, BE->C, CG->B, CE->G}
Can I use transitivity to reduce this further, i.e. - AB->C and C->A becomes AB->A which can be removed since it becomes trivial?
Is {BC->D, D->EG, BE->C, CG->B, CE->G} the minimal set? If not, can you give me some advice on how to further refine the solution set?
Thank you.

chopnhack said:
3rd - Reduce redundant functional dependencies using closure of attributes
ACD closure = ACDEGB since B is in the closure and also in the functional dependency ACD->B , we can remove it from the list of fd's
CG closure = CGBD since D is in the closure and also in the functional dependency CG->D, we can also remove it from the list of fd's
Neither of these is valid. What rule are you trying to use here? The way you've written it cannot be a rule since by definition, an item that is in the RHS of a fd is always in the closure of the LHS of that fd.
In fact you can remove either of the two rules you have removed, but not both.

## What is a functional dependency solving algorithm?

A functional dependency solving algorithm is a method used to determine the minimal cover of a given set of functional dependencies. It is used in database design to simplify and optimize the structure of a database.

## What is a minimal cover?

A minimal cover is the smallest set of functional dependencies that can express the same information as a given set of functional dependencies. It eliminates any redundant or extraneous dependencies and ensures that the database is in a normalized form.

## Why is it important to find the minimal cover?

Finding the minimal cover is important because it helps to reduce the size and complexity of a database, making it more efficient and easier to maintain. It also ensures that the database is free from any data anomalies, such as insertion, deletion, and update anomalies.

## What is the process of solving for a minimal cover using a functional dependency solving algorithm?

The process involves identifying all the functional dependencies in a given set, eliminating any redundant or extraneous dependencies, and then combining the remaining dependencies to form the minimal cover. This is done by applying a set of rules, such as the Armstrong's axioms, to determine the closure of each attribute and check for dependencies that can be eliminated.

## Are there any limitations to using a functional dependency solving algorithm?

Yes, there are some limitations to using a functional dependency solving algorithm. It may not always produce the most optimal minimal cover, as there can be multiple minimal covers for a given set of functional dependencies. Additionally, the process can be time-consuming and complex for large databases with many functional dependencies.

• Engineering and Comp Sci Homework Help
Replies
4
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
626
• General Math
Replies
7
Views
1K
• General Math
Replies
0
Views
733
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Engineering and Comp Sci Homework Help
Replies
3
Views
1K
• Special and General Relativity
Replies
16
Views
2K
• Chemistry
Replies
7
Views
1K