Efficient processing of complex recursive queries

Abstract

Efficient evaluation of recursive queries is an important issue in deductive database systems, since it may often require many costly join operations. In this thesis, we study on processing recursive queries focused on two optimization approaches: minimizing the temporary relations created in the evaluation without causing duplicate computation and maximizing the effect of each rule application. Deductive queries can be represented by graphs, and the evaluation of them starts with identification of strongly connected components (SCCs) in the graphs. Then each SCC can be processed bottomup in a partial order between SCCs. The graphs for recursive queries have at least one non-trivial SCC that has at least one cycle, and we call such a non-trivial SCC the recursion. Two optimization approaches mainly concern the recursive queries that have SCCs with more than one cycle. We call those recursive queries complex recursive queries. For complex recursive queries, we may have to create many temporary relations in their evaluation. Since creating many temporary relations causes an adverse effect on the performance, we should minimize the number of temporary relations created in the evaluation. In this thesis, we identify the lower bound on the number of temporary relations that are absolutely needed in the evaluation of queries. The evaluation with only the minimum number of temporary relations, however, may involve duplicate computation. We develop a technique to reduce the number of temporary relations so that there is no duplicate computation in the evaluation. Conventional fixed point evaluation techniques process recursions by applying all rules repeatedly over an initial set of tuples (i.e., a given extensional database instance) until no new tuples are generated, but there is no specific order in which rules are applied. One can speed up the evaluation by applying rules in an appropriate order. In this thesis, we propose a new fixed point evaluation technique, ca...