Succinct database schemes

Publisher Website
Google Scholar
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.

This publication has 5 references indexed in Scilit: