On data dependency structures of relational databases

摘要

The properties of the set of all functional dependencies (which is defined to be FD sub-structure), derivable from a given set of functional dependencies (FD's) and multivalued dependencies (MVD's) for a relational database, are studied. A necessary and sufficient condition that a set of FD's is a cover for the FD sub-structure is proved, which can be tested for validity by an efficient algorithm. An algorithm of generating a cover for the FD substructure is presented. It can be shown, however, that in at least one instance, the number of FD's in the cover may actually increase more than exponentially as the number of MVD's increases.