On the multiple-query optimization problem
Timos Sellis, Subrata Kumar Ghosh · IEEE Transactions on Knowledge and Data Engineering · 1990
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.>