Multiple Query Processing in Deductive Databases using Query Graphs

Abstract

Research activity on query evaluation and optimization has been centered around processing one query at a time. Query processing systems. in general. attempt to minimize the cost of processing a set of queries by minimizing the processing cost of each query separately. A separate plan is generated and executed for each query. The cost of processing (that is the CPU cost + Input/Oulput cost) a set of queries evaluated in the above manner is equal to the sum of the processing cost for each query. In this paper we extend the connection graph decomposition algorithm to generate a single plan for evaluating a set of queries. The approach presented in this paper is aimed at generating a single plan. exploiting the common subexpressions that can be detected using heuristics. We assume. for the purposes of this paper. that we are answering queries over a deductive database. although the approach is equally applicable to a group of independent queries. 1.