Program to find canonical cover or minimum number of functional dependencies

Question

I would like to find the canonical cover or minimum number of functional dependencies in a database.

For example:

If you have: Table = (A,B,C) <-- these are columns: A,B,C

And dependencies:

A → BC

B → C

A → B

AB → C

The canonical cover (or minimum number of dependencies) is:

A → B

B → C

Is there a program that can accomplish this? If not, any code/pseudocode to help me write one would be appreciated. Prefer in Python or Java.

Answer 1

Looking at your dependencies, it looks like you can view them as a partial order on A, B, C. What you want sounds a lot like (but not entirely) a topological sort (a partial order sort on a directed acyclic graph).

Answer 2

Looks to me like you can refactor any rules of the form:

   A ->  BC

into

 A -> B

and

  A -> C

and any rules of the form:

  AB -> C

into

  A -> C

and

  B -> C

After this refactoring, you should have a set of rules of the singleton pairs:

  X -> Y

(Likely with lots of redundant copies you can immediately remove). This forms the partial order that rlotun seemed to referring to.

For the example so far, you end up with:

 A -> B
 B -> C
 A -> C

If you then minimize the partial order (e.g., remove any redundant links, any data structure books on partial should tell you how to do that), you'll have a minimal partial order, and I think that's the answer you want. Minimizing the partial order in the example, you'd delete A -> C from the partial order, ending with your answer.