Query Compilation under the disjunctive well-founded semantics

Article type: Research Article

Authors: Johnson, Chris A.

Affiliations: School of Computing, Portland Square, University of Plymouth, Plymouth, PL4 8AA, England

Abstract: A top-down method is presented for compiling queries in unstratified propositional disjunctive deductive databases under the disjunctive well-founded semantics. Compilation entails the construction of a set of compilation trees, and the run-time processing of the compiled query then amounts to checking that some such tree can be extended within the extensional database to yield a tree that encapsulates a proof of the original query. Issues surrounding the extension of our techniques to the first order level are discussed.

Keywords: disjunctive deductive databases, disjunctive well-founded semantics, query compilation, top-down computation

Journal: Fundamenta Informaticae, vol. 62, no. 3-4, pp. 343-368, 2004