A mathematical programming approach to data base normalization

A critical step in the process of creating a relational database is normalization, whereby a series of tables is created in order to avoid redundancy problems and insertion and deletion anomalies. Several important normalization decision problems are NP-Complete. In this paper the authors develop a unified approach to data base normalization using linear integer programming. These linear integer programming formulations result from structuring normalization problems as gainfree Leontief substitution flow problems on hypergraphs. The authors provide a sufficient condition based on the structural properties of the hypergraph which yields a strongly polynomial algorithm for testing whether or not a given decomposition is in third normal mode. They also show that under these conditions the key of a relation is unique and a relation in third normal form is also in Boyce-Codd normal form. The authors also provide linear integer programming formulations for solving normalization decision problems when no special structure is present. They test three linear integer programming models for normalization against existing normalization algorithms and find the mathematical programming approach is several orders of magnitude faster. The present results suggest that the mathematical programming approach is practical for normalizing actual large scale data bases.