Functional Dependency algorithm
Date: Sat, 29 Dec 2007 16:02:30 -0800 (PST)
Message-ID: <d620a7b2-6ae0-4b3e-924c-17456e21a739_at_1g2000hsl.googlegroups.com>
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
end while
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+?
Regards,
Jeff Davis Received on Sun Dec 30 2007 - 01:02:30 CET