A performance comparison of top-down recursive query evaluation strategies on Datalog benchmarks

A performance comparison is given, using Datalog benchmarks, of top-down strategies for the evaluation of recursive queries. The top-down strategies that are compared include S.W. Dietrich and D.S. Warren´s extension tables (see Tech. Rep., 85-31, Dept. of Computer Science, SUNY at Stony Brook (1985)), H. Tamaki and T. Sato´s multistage depth-first (see Third Int. Conf. Logic Prog., p.84-98 (1986)) and L. Vielle´s query subquery (see Fourth Int. Conf. on Logic Prog., p.74-103 (1987)). These top-down strategies apply the dynamic programming principle to computations in which intermediate results are saved and subsequently used to avoid redundant computations. The performance comparisons show that extension tables´ eager evaluation improves the naive demand-driven evaluation of multistage depth-first and QSQR/SLD and query/subquery