Efficient implementation of loops in bottom-up evaluation of logic queries
Juhani Kuittinen, Otto Nurmi · 1990
Abstract. We consider the efficient implementa-tion of the bottom-up evaluation method for recursive queries in logic databases. In the bottom-up evalu-ation algorithms the non-mutually-recursive rules are evaluated in certain order, whereas the evaluation or-der within a set of the mutually recursive rules is free. However, significant savings in join operations can be achieved by arranging the mutually recursive rules appropriately. We present an algorithm for split-ting the evaluation loop for mutually recursive rules into subloops and for determining the order in which the rules should be evaluated within a loop. The semi-naive evaluation algorithm is modified accordingly to gain advantage from the evaluation order and to work with the incremental relations (“deltas”) appearing at different levels in the loop structure. The computa-tion within a subloop is optimized by identifying loop-invariant factors in the rules to be evaluated. Using an experimental logic database system we demonstrate the usefulness of our algorithm in implementing data-log queries optimized by the “magic sets ” and related term rewriting strategies. *The work was supported by the Academy of Finland.