Fast algorithms for universal quantification in large databases

• Published in: ACM transactions on database systems 1995-06, Vol.20 (2), p.187-236
• Main Authors: Graefe, Goetz, Cole, Richard L.
• Format: Article
• Language: English
• Subjects: Algebra; Algorithms; Applied sciences; Computer science; control theory; systems; Contextual software domains; Data management systems; Data structures design and analysis; Database management system engines; Database query languages (principles); Database query processing; Database query processing and optimization (theory); Database theory; Design and analysis of algorithms; Exact sciences and technology; File systems management; Information storage systems; Information systems; Information systems. Data bases; Memory organisation. Data processing; Operating systems; Programming languages; Query languages; Record storage systems; Software; Software and its engineering; Software engineering; Software organization and properties; Sorting and searching; Theory and algorithms for application domains; Theory of computation
• ISSN: 0362-5915; 1557-4644
• DOI: 10.1145/210197.210202

Universal quantification is not supported directly in most database systems despite the fact that it adds significant power to a system's query processing and inference capabilities, in particular for the analysis of many-to-many relationships and of set-valued attributes. One of the main reasons for this omission has been that universal quantification algorithms and their performance have not been explored for large databases. In this article, we describe and compare three known algorithms and one recently proposed algorithm for relational division, the algebra operator that embodies universal quantification. For each algorithm, we investigate the performance effects of explicit duplicate removal and referential integrity enforcement, variants for inputs larger than memory, and parallel execution strategies. Analytical and experimental performance comparisons illustrate the substantial differences among the algorithms. Moreover, comparisons demonstrate that the recently proposed division algorithm evaluates a universal quantification predicate over two relations as fast as hash (semi-) join evaluates an existential quantification predicate over the same relations. Thus, existential and universal quantification can be supported with equal efficiency by adding the recently proposed algorithm to a query evaluation system. A second result of our study is that universal quantification should be expressed directly in a database query language, because most query optimizers do not recognize the rather indirect formulations available in SQL as relational division and therefore produce very poor evaluation plans for many universal quantification queries.