Computing covers for embedded functional dependencies

Abstract

This paper deals with the problem of computing covers for the functional dependencies embedded in a subset of a given relation schema. We show how this problem can be simplified and present a new and efficient algorithm “Reduction. By Resolution” (RBR) for its solution. Though the problem of computing covers for embedded dependencies is inherently exponential, our algorithm behaves polynomially for several classes of inputs. RBR can be used for the solution of some related problems in the theory of database design, such as deciding whether a given database scheme is in Boyce-Codd Normal Form or decomposing a scheme into Boyce-Codd Normal Form.