Preserving Functional Dependencies
Catriel Beeri, Peter Honeyman · SIAM Journal on Computing · 1981
We show that functional dependency preservation can be tested in polynomial time. We show further that while finding a cover for all embedded dependencies is NP-complete, such a cover can be found in polynomial time if dependencies are preserved.