Extension tables for recursive query evaluation
Suzanne Wagner Dietrich · 1987
This dissertation presents one of the first top-down demand-driven strategies for the evaluation of recursive queries in logic programs, along with proofs of soundness and completeness. A performance evaluation shows that the strategy performs well in comparison to related methods. The ET* algorithm for evaluating pure logic programs is described. The algorithm uses an extension table to save the results of computations for selected predicates. The ET* algorithm repeatedly evaluates a given query using the extension table until it completes an entire iteration without finding any new answers. A clear and straightforward implementation of the ET* algorithm is developed in Prolog. The dissertation investigates optimizations that may lead to a more efficient evaluation of a logic program using extension tables. These optimizations are supported by performance comparisons. One particular optimization, called the ET algorithm, can be used if a single pass of the ET* algorithm finds all the answers for a given query. In addition to evaluating recursive queries, the ET algorithm is a caching mechanism that can be used to improve the performance of a logic program, when saving and retrieving the results of certain predicates is less expensive than recomputing these answers. In particular, the ET algorithm can be effectively applied to predicates that retrieve tuples from an external relational database management system. This dissertation compares the performance of the top-down demand-driven strategies for recursive query evaluation, including Earley Deduction, Tamaki and Sato's Multistage Depth-first, Vieille's Query/Subquery and Extension Tables. This study shows that the extension table algorithms are, in general, more efficient than the other strategies. The ET* algorithm, which eagerly evaluates a program using all of the answers stored in the extension table, outperforms its iterative recursive counterparts, such as Multistage Depth-first (MSDF) and Query/Subquery (QSQR/SLD), which do not use answers computed on the current iteration. When the ET algorithm finds all the answers for a query, the comparisons indicate that, for such cases, its performance is superior to all its rivals.