Search code examples
databasefunctional-dependencies

Functional dependency - Left hand side with three attributes

Assuming we have the following functional dependencies : 

AB -> C 
DEG -> H
A -> B
DG -> H

We can see that B can be removed due to the closure of B+, which is (G-(AB ->C) U (A -> C) = ACB

In order to find the minimal cover, how do I approach the other left hand redundancies in regards to DEG -> H, DG -> H - can these be reduced, and if so can you explain using the closures!

Many thanks, Matthew

Solution

  • There are a small set of rules to do this. It is really easy. A functional dependency set is minimal;

    1. If there are only single attributes on the right sides of the depencencies. And...
    2. There is no functional dependency that can be removed, a way by keeping the original cover. And...
    3. You can't remove attribute from the left side of the dependency and keep the original cover

    So if you are finding a minimal cover you must make these sure. Of course you must keep the closure equivalent.

    If you take a look at:

    AB -> C 
DEG -> H
A -> B
DG -> H

    You can easily find redundancy. There is no point to include both DEG → H and DG → H because DG → H already covers all that DEG → H covers. So you can remove it.

    Still equivalent:

    AB -> C 
A -> B
DG -> H

    You can still see that from the first line you can remove B because it depends funcitonally from A.

    Still equivalent:

    A -> C 
A -> B
DG -> H

    We have found a minimal cover. No dependencies can be removed to keep the closure, and there are only single attributes on the right side, and DG is the only double attribute on the left side, that must be kept. We cannot remove neither D or G and keep the origninal closure.

    We can proove this using Armstrong axioms. If we can get the original set, then this is truely an equivalent minimal set. (I will post it later - I hope it is correct.)