A goal-driven approach to efficient query processing in disjunctive databases

Abstract

Generally, proof procedures based on model generation perform bottom-up processing of clauses. Several algorithms for generating (minimal) models for disjunctive theories were advanced in the literature. Used for query answering, bottom-up procedures tend to explore a much larger search space than is strictly needed. On the other hand, top-down processing usually has a more focused search space which can result in more e cient query answering. In this paper we establish a strong connection between model generation and clause derivability that allows us to use a (minimal) model generating procedure for evaluating queries in a top-down fashion. In contrast to other methods our 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 achieved by reversing the direction of implication connectives in the clauses representing both the theory and the negation of the query. The application of a generic (minimal) model generating procedure to the transformed clause set results in top-down query answering. We explain the reasoning behind the transformation and show how the duality approach can be utilized for re ned query answering by specifying the conditions under which the query becomes derivable from the theory. Our initial testing points to a clear e ciency advantage of the advanced approach as compared to traditional bottom-up processing for the class of positive queries against a disjunctive database.