Functional Dependency algorithm - 12-29-2007 , 06:02 PM
I am trying to build a tool that calculates the canonical cover of a
set of functional dependencies, and can infer functional dependencies
from an existing database (perhaps other features too, like attribute
closure). First of all, if someone has pointers to tools that already
do this, I'd like to hear about them.
Second, I have not been able to find a very efficient looking
algorithm to calculate the canonical cover. The algorithms that I find
are something like:
let Fc = F+ /* closure of set of FDs */
while (Fc changed) do
apply union rule
remove extraneous attributes on the left
remove extraneous attributes on the right
The union rule is fairly easy and efficient to implement. Is there a
way to determine the extraneous attributes without computing F'+
(closure of functional dependencies after one potentially extraneous
attribute has been removed) for each attribute in each iteration?
What's the best algorithm to remove the extraneous attributes? What's
the best algorithm to calculate F+?