A performance comparison of top-down recursive query evaluation strategies on Datalog benchmarks
S.W. Dietrich · 2003
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.>