I must discover the canonical cover or minimum quantity of functional dependencies inside a database.
For those who have: Table = (A,B,C) <-- they are posts: A,B,C
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
A -> B
A -> C
and then any rules from the form:
AB -> C
A -> C
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.