Practical algorithms for finding prime attributes and testing normal forms

Abstract

Several decision problems for relational schemas with functional dependencies are computationally hard. Such problems include determining whether an attribute is prime and testing if a schema is in normal form. Algorithms for these problems are needed in database design tools. The problems can be solved by trivial exponential algorithms. Although the size of the instance is usually given by the number of attributes and hence is fairly small, such exponential algorithms are not usable for all design tasks. We give algorithms for these problems whose running time is polynomial in the number of maximal sets not determining an attribute or, equivalently, the number of generators of the family of closed attribute sets. There is theoretical and practical evidence that this quantity is small for the schemas occurring in practice and exponential only for pathological schemas. The algorithms are simple to implement and fast in practice. They are in use in the relational database design tool Design-By-Example.