On the multiple-query optimization problem

The complexity of the multiple-query optimization problem in database management systems is examined. It is shown that the problem is NP-hard. Then the authors examine the performance of a heuristic algorithm to solve the multiple-query optimization problem and suggest some heuristics for query ordering which improve the efficiency of the algorithm considerably. Some experimental results on the performance of various heuristics are also presented.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>