EVALUATION OF REGULAR NONLINEAR RECURSIONS BY DEDUCTIVE DATABASE TECHNIQUES

Nonlinear recursion is one of the most challenging classes of logic pr ograms for efficient evaluation in logic programming systems. We ident ify one popular class of nonlinear recursion, regular nonlinear recurs ion, and investigate its efficient implementation by a deductive datab ase approach. The approach performs a detailed query binding analysis based on query information, constraint information and the structure o f a recursion, selects an appropriate predicate evaluation order and g enerates an efficient query evaluation plan. Interesting query evaluat ion techniques, such as chain-following, chain-split, and constraint p ushing, are developed for the efficient evaluation of different kinds of queries. Furthermore, the technique can be extended to the evaluati on of regular nonlinear recursions in HiLog and F-logic programs. The study not only presents a method for the evaluation of regular nonline ar recursions in a declarative way but also demonstrates the power of the deductive database approach in the analysis and evaluation of soph isticated logic programs.