Please use this identifier to cite or link to this item: http://hdl.handle.net/20.500.11889/2089
Title: A goal-driven approach to efficient query processing in disjunctive databases
Authors: Yahya, Adnan
Issue Date: Aug-1996
Publisher: ResearchGate
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.
URI: http://hdl.handle.net/20.500.11889/2089
Appears in Collections:Fulltext Publications

Files in This Item:
File Description SizeFormat
A_Goal-Driven_Approach_to_Efficient_Query_Processi.pdf449.51 kBAdobe PDFView/Open
Show full item record

Download(s)

1
checked on Nov 13, 2019

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.