On the desirability of acyclic database schemes. (English) Zbl 0624.68087

A class of database schemes, called acyclic, was recently introduced. It is shown that this class has a number of desirable properties. In particular, several desirable properties that have been studied by other researchers in very different terms are all shown to be equivalent to acyclicity. In addition, several equivalent characterizations of the class in terms of graphs and hypergraphs are given, and a simple algorithm for determining acyclicity is presented. Also given are several equivalent characterizations of those sets M of multivalued dependencies such that M is the set of multivalued dependencies that are the consequences of a given join dependency. Several characterizations for a conflict-free (in the sense of Lien) set of multivalued dependencies are provided.


68P20 Information storage and retrieval of data
05C65 Hypergraphs
Full Text: DOI