Improvements on a Heuristic Algorithm for Multiple-Query Optimization

Abstract

Multiple-query processing has received a lot of attention recently. The problem arises in many areas, such as extended relational database systems and deductive systems. In this paper we describe a heuristic search algorithm for this problem. This algorithm uses an improved heuristic function that enables it to expand only a small fraction of the nodes expanded by an algorithm that has been proposed in the past. In addition, it handles implied relationships without increasing the size of the search space or the number of nodes generated in this space. We include both theoretical analysis and experimental results to demonstrate the utility of the algorithm.