GRAMMARS AND AUTOMATA TO OPTIMIZE CHAIN LOGIC QUERIES
Sergio Greco, Domenico Saccà, Carlo Zaniolo · International Journal of Foundations of Computer Science · 1999
The critical problem of finding efficient implementations for recursive queries with bound arguments offers many open challenges of practical and theoretical import. In particular, there is a need to find methods that are effective for the general case, such as non-linear programs, as well as for specialized cases, such as left-recursive linear programs. In this paper, we propose a novel approach that solves this problem for chain queries, i.e., for queries where bindings are propagated from arguments in the head to arguments in the tail of the rules, in a chain-like fashion. The method, called pushdown method, is based on the fact that a chain query can have associated a context-free language and a pushdown automaton recognizing this language can be emulated by rewriting the query as a particular factorized left-linear program. The proposed method generalizes and unifies previous techniques such as the 'counting' and 'right-, left-, mixed-linear' methods. It also succeeds in reducing many non-linear programs to query-equivalent linear ones.