1

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 attributed. 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?

1

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.

5
  • 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
  • 1
    @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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.