North-Holland Query evaluation in recursive databases: bottom-up and top-down reconciled

Abstract. It is desirable to answer queries ' posed to deductive databases by computing fixpoints because such computations are directly amenable to set-oriented fac processing. However, the classical fixpoint proce-dures based on bottom-up processing- 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 wecall the Backward Fixpoint Procedure. Th n, we reconsider query evaluation methods for recursive databases. First, we show that he methods based on rewriting on the one hand, and the methods based on resolution on the other hand, implement the Backward Fixpoint Procedure. Second, we i terpret the rewritings of the Alexander and Magic Set methods as specializations of the Backward Fixpoint Procedure. Finally, we argue that such a rewriting is also needed in a database context 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