Succinct database schemes

Abstract

Efficient algorithms are known for finding a database scheme that is in Boyce-Codd normal form (BCNF) with respect to a set of functional dependencies. A disadvantage of these algorithms is that they produce overly-fragmented database schemes, resulting in inefficient query processing. We investigate the problem of finding succinct database schemes and prove that this problem is NP-hard. Our method of proof is of interest, firstly because it involves an extremely simple class of sets of functional dependencies and secondly, becaue the encoding of the known NP-complete problem is “two-way”, allowing us to exploit approximation algorithms. We discuss the applicability of these results to third normal form (3NF) database schemes.

Keywords:

• Relational database
• normalization
• complexity

To whom all correspondence should be addressed

To whom all correspondence should be addressed

Notes

To whom all correspondence should be addressed