RANGE NESTING: A FAST METHOD TO EVALUATE QUANTIFIED QUERIES

Abstract

Database queries explicitly containing existential and universal quantification become increasingly important in a number of areas such as integrity checking, interaction of databases, and statistical databases. Using a concept of range nesting in relational calculus expressions, the paper describes evaluation algorithms and transformation methods for an important class of quantified relational calculus queries called perfect expressions. This class includes well-known classes of "easy" queries such as tree queries (with free and existentially quantified variables only), and complacent (disconnected) queries.