Duality for goal-driven query processing in disjunctive deductive databases

Abstract

Bottom-up query answering procedures tend to explore a much larger search space than is strictly needed. Top-down processing has a more focused search space which can result in more e cient query answering. We establish a strong connection between model generation and clause derivability that allows us to use a bottom-up procedure for evaluating queries in a top-down fashion. The approach requires no extensive rewriting of the input theory and introduces no new predicates. Rather, it is based on a certain duality principle for interpreting logical connectives. It is achieved by reversing the direction of implication arrows in the clauses representing both the theory and the negation of the query. The application of a generic bottom-up procedure to the transformed clause set results in top-down query answering. We give meaning to this transformation and show how it can be utilized for re ned query answering by specifying the minimal conditions (weakest updates) under which the query becomes derivable from the theory.