minimal cover for functional dependencies

Question

I have the following problem:

AB -> CD
H->B
G ->DA
CD-> EF
A -> HJ
J>G

I understand the first step (break down right hand side) and get the following results:

AB -> C
AB -> D
H -> B
G -> D
G -> A
CD -> E
CD -> F
A -> H
A -> J
J -> G

I understand that A -> h and h -> b, therefore I can remove the B from AB -> c and ab -> D, to get:

A -> C
A -> D
H -> B
G -> D
G -> A
CD -> E
CD -> F
A -> H
A -> J
J -> G

The step that follows is what I can't compute (reduce the left hand side)

Any help will be greatly appreciated.

Answer 1

You have already reduced the left hand side of each FD in the cover. The next step is to reduce the number of FD's in that cover to a minimum.

Do this by ignoring one FD at a time, then see if you can still come up with the same set of dependent attributes (closure) using the other FD's in the cover using the ignored FD's LHS as a starting point. If you can, then the FD you ignored is redundant and may be dropped from the cover. Do this for each remaining FD. What is left is a minimal cover.

First, using all the FD's in the starting cover, derive the set of attributes determined by the LHS of the FD you will ignore. For A the closure is:

A, B, C, D, E, F, G, H, J

Try remvoving A -> D and recompute the closure...

initial   closure: A
use A -> C    closure: A, C
use A -> H    closure: A, C, H
use A -> J    closure: A, C, H, J
use J -> D    closure: A, C, D, H, J
use J -> G    closure: A, C, D, G, H, J
use H -> B    closure: A, B, C, D, G, H, J
use CD -> E   closure: A, B, C, D, E, G, H, J
use CD -> F   closure: A, B, C, D, E, F, G, H, J

It is possible to derive the same set of attributes without ever referencing the FD A -> D so this FD is redundant and may be dropped from the cover. Acutally we could have stopped the process once D showed up in the derived set of attributes - but for completness the process was continued to prove exactly the same attribute set could be achieved with or without A -> D.

Note that a minimal cover for a given set of FD's need not be unique. However, any given minimal cover must embody the same set of dependencies as the original cover such that removing any one dependency from the minimal cover fails to yield the same closure.