A non-magical set-oriented method for Datalog

This paper presents a new algorithm for query evaluation for datalog. The algorithm is set-oriented as it uses sets to constraint the arguments of the related rules and the subgoals generated. The nature of the algorithm is top-down with memorization, which captures the fixed-point idea behind the bottom-up approach. We show that the algorithm is computationally efficient, it generates only relevant facts as in the top-down approach, but always terminates and avoids repeated derivation of the same facts. It achieves equal or better performance than the generalized magic sets method in frequently quoted examples, and typically uses less storage. 1 Introduction Deductive databases have been investigated for quite a number of years and general overviews can be found in [GMN84, RU95]. One of the major tasks of a deductive database is query answering. Many query evaluation methods have been proposed. These evaluation methods can be divided into three categories: top-down approaches, bottom..