Program to locate canonical cover or minimum quantity of functional dependencies

I must discover the canonical cover or minimum quantity of functional dependencies inside a database.

For instance:

For those who have: Table = (A,B,C) <-- they are posts: A,B,C

And dependencies:

``````A → BC

B → C

A → B

AB → C
``````

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

``````A → B

B → C
``````

It is possible to program that may make this happen? Otherwise, any code/pseudocode that helped me to write you might be appreciated. Prefer in Python or Java.

Searching at the dependencies, it appears like you will see them like a partial order on `A, B, C`. What you would like sounds nearly the same as (although not entirely) a topological sort (an incomplete order sort on the directed acyclic graph).

Looks in my experience as if you can refactor any rules from the form:

``````   A ->  BC
``````

into

`````` A -> B
``````

and

``````  A -> C
``````

and then any rules from the form:

``````  AB -> C
``````

into

``````  A -> C
``````

and

``````  B -> C
``````

Following this refactoring, you ought to have some rules from the singleton pairs:

``````  X -> Y
``````

(Likely with a lot of redundant copies you are able to immediately remove). This forms the partial order that rlotun appeared to mentioning to.

For that example to date, you finish track of:

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

Should you then minimize the partial order (e.g., remove any redundant links, data structure books on partial should let you know how to achieve that), you'll possess a minimal partial order, and i believe this is the answer you would like. Reducing the partial order within the example, you'd remove A -> C from the partial order, ending together with your answer.