A Goal-Driven Approach to Efficient Query Processing in Disjunctive Databases
Adnan H. Yahya · 1996
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 efficient 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...