Recursive queries evaluation: a constraint based top-down/bottom-up method

The paper presents an evaluation method for recursive queries based on an integration of the bottom-up and the top-down evaluation strategies. The proposal tries to eliminate the major drawbacks of the top-down Prolog-like evaluation strategies. Namely, repetition of identical accesses to the EDB and the exploration of resolution branches that lead to the same answer substitution. Forward reasoning (bottom-up phase) is performed by keeping memory of (some) demonstrated "lemmas" while the introduction of constraints avoids visiting already inspected portions of the search space when backtracking (top-down phase).