Multiple-Query Optimization.

Abstract

Some recently proposed extensions to relational database systems as well as deductive database systems, require support for processing multiple queries. For example, in a database system enhanced with inference capabilities, a simple query involving a rule with multiple definitions, may expand to more than one actual query that has to be run over the database. It is an interesting problem then, to come up with algorithms that process these queries together instead of one query at a time. The main motivation for performing such an interquery optimization lies in the fact that queries may share common data. We examine the problem of multiple-query optimization in this paper. The first major contribution of this paper is a systematic look at the problem and the presentation and analysis of algorithms that can be used for multiple query optimization. The second contribution lies in the presentation of experimental results. Our results show that using multiple-query processing algorithms may reduce execution cost considerably.