Comp Sci Functional Dependency Solving Algorithm for Minimal Cover

[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.

 

[andrewkirk]

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.