Computing Covers for Embedded Functional Dependencies

摘要

A reduction by resolution algorithm for computing covers for the functional dependencies embedded in a subset of a given relation schema is presented. Although the problem of computing covers for embedded dependencies is inherently exponential, the algorithm behaves polynomially for several classes of inputs. It can be used for the solution of related problems in the theory of data base design, such as deciding whether a given data base scheme is in Boyce-Codd Normal Form or decomposing a scheme into Boyce-Codd Normal Form.