# How to solve multiple minimal covers for functional dependencies?

I have the schema: `a,b,c,d,e,g` and the following functional dependencies:

`b->c, dg->ce, bc->dg, e->a, g->bd`

for which I want to find the minimal cover. It seems that more than one scenario is possible.

First I represent the dependencies by splitting the right-hand side:

`b->c, dg->c, dg->e, bd->d, bc->g, e->a, g->b, g->d`

For `dg->c` there's one extraneous attribute`d`. Same goes for `dg->e`.

For `bc->d` the attribute `c` is extraneous as well as for `bc->g`.

For `g->bd` the attribute `d` is extraneous because if we have `g->b` then `g+ = {gbcd}` which contains `d`.

So we have 4 possible minimal covers:

`b->c, g->c OR g->e, b->d OR b->g, g->b, e->a`.

The correct answer is `g-->c; g-->e; b-->g; e-->a; g-->b; g-->d` according to this tool.

I cannot get the same answer from simplifying my minimal cover. What am I doing wrong?

Starting from the dependencies:

``````b->c, dg->ce, bc->dg, e->a, g->bd
``````

and splitting the right hand side, one obtain:

``````b->c, dg->c, dg->e, bc->d, bc->g, e->a, g->b, g->d
``````

(Note that you have written `bd->d` instead of `bc->d`).

Then you have correctly found that the attribute `d` is extraneous both in `dg->c` and `dg->e`, while `c` is extraneous both in `bc->d` and in `bc->g`. So that the set of dependencies is now:

``````b->c, g->c, g->e, b->d, b->g, e->a, g->b, g->d
``````

Then you say:

For `g->bd` the attribute `d` is extraneous because if we have `g->b` then `g+ = {gbcd}` which contains `d`

but no dependency `g->bd` exists (it has already been split in the two dependencies `g->d` and `g->b`).

The last step is to find the superfluous dependencies in:

``````b->c, g->c, g->e, b->d, b->g, e->a, g->b, g->d
``````

that are `b->d` and `b->c`. So at the end we have:

``````g->c, g->e, b->g, e->a, g->b, g->d
``````

which is exactly the answer given by the tool.

Finally, consider that actually a set of functional dependencies could have more than one minimal cover: this depends on the order in which the attributes and the dependencies are considered for the elimination.

• I'm not sure what you meant in the last paragraph: "Finally, consider that actually a set of functional dependencies could have more than one minimal cover: this depends on the order in which the attributes and the dependencies are considered for the elimination.". If for example I first discover that in `bc->d` and `bc->g` `c` is extraneous first and then I discover that `d` is extraneous in `dg->c` and `dg->e` the set of dependencies will still be the same. – Yos Aug 17 '18 at 10:00
• @Yos, consider the following dependencies: ab->c, a->b, b->a. This has two different minimal covers: a->c, a->b, b->a and b->c, a->b, b->a. You obtain the first if you first remove b from the left part of the first dependency, the second if you remove a from the left part of the first dependency (both removals are possible). – Renzo Aug 17 '18 at 10:30
• But in the OP there're not such choices to be made as in your example. In both `dg->c` and `dg->e` `d` is extraneous. Same goes for `bc->d` and `bc->g`, `c` is extraneous. – Yos Aug 17 '18 at 12:11
• In fact in your example there is only one minimal cover. I was just noting that in general there can be more than one canonical (or minimal) cover. – Renzo Aug 17 '18 at 16:50
• @Yos & Renzo The fact that no choice arises in applying an algorithm doesn't mean that there are no other minimal covers. It just means that that algorithm can't find any other minimal covers. – philipxy May 5 at 4:46