Dependency-lattices, acyclic hypergraphs and relational database scheme design

Abstract

Compared to other models of data, the relational model offers several advantages:

Clear separation between logical organization and physical storage of data Ease of understanding the logical structure Use of high-level query languages that relieve users from implementation details A sound mathematical foundation for formally studying key problems in database design and maintenance

The objective of this research is to develop elegant characterizations and efficient algorithms for important issues in the design and maintenance of relational databases. The problems addressed include:

The membership problem for functional and multivalued dependencies Algorithmic characterizations of sets of multivalued dependencies with split-free and conflict-free covers (dependency theory) Characterizations of ?-acyclic and ?-acyclic database schemes (acyclicity theory)

Unifying these results, the thesis proposes a new methodology for database scheme design that concurrently targets normal forms and acyclicity. Applications of these findings are discussed in the context of scheme design, query processing, and dependency theory.