Query Evaluation in Recursive Databases
François Bry · Open access LMU (Ludwid Maxmilian's Universitat Munchen) · 1990
uucp:... /pyramid!ecrcvaxlfb It is desirable to answer queries posed to deductive databases by computing fixpoints because such computations are directly amenable to set-oriented fact processing.However, the classical fixpoint procedures based on bottom-up reasoning -the naive and semi-naive methods -are rather primitive and often inefficient.In this article, we rely on bottom-up meta-interpretation for formalizing a new fixpoint procedure that performs a different kind of reasoning: We specify a top-down query answering method, which we call the Backward Fixpoint Procedure.Then, we reconsider query evaluation methods for recursive databases.First, we show that the methods based on rewriting on the one hand, and on resolution on the other hand, implement the Backward Fixpoint Procedure.Second, we interpret the rewriting of the Alexander and Magic Set methods as a specialization of the Backward Fixpoint Procedure.Finally, we argue that this rewriting is also needed for implementing efficiently the resolution-based methods.Thus, the methods based on rewriting and the methods based on resolution implement the same top-down evaluation of the original database rules by means of auxiliary rules processed bottom-up.