Preserving Functional Dependencies

Abstract

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.