Database Design – How to Solve Multiple Minimal Covers for Functional Dependencies

database-designnormalization

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?

Best Answer

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.

Related Question