Recursive query answering with non-Horn clauses

Shan Chi, Lawrence Joseph Henschen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


In this paper, an algorithm is presented for answering recursive queries under the Generalized Closed World Assumption (GCWA) in a database with positive non-Horn ground clauses. It is proved that the algorithm generates all the answers under the GCWA. We consider only the transitive closure recursions in which only one base relation is involved. The set of ground clauses is stored as one relation so that a modified join operator can be applied to the clauses. The relation can be visualized as a directed graph with each tuple representing an edge. A query (only closed queries are considered in this paper) is answered by extracting the paths from the relation, forming the negative clauses from these paths, and sending the negative clauses together with the non-Horn clauses to a theorem prover. We proved that if the empty clause is derived then the answer to the query is true. This algorithm is efficient for two reasons: 1) facts (positive unit ground clauses) are processed by the modified join operator, and 2) the theorem prover handles only the non-Horn ground clauses and some negative ground clauses.

Original languageEnglish (US)
Title of host publication9th International Conference on Automated Deduction, Proceedings
EditorsEwing Lusk, Ross Overbeek
PublisherSpringer Verlag
Number of pages19
ISBN (Print)9783540193432
StatePublished - 1988
Event9th International Conference on Automated Deduction, CADE 1988 - Argonne, United States
Duration: May 23 1988May 26 1988

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume310 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th International Conference on Automated Deduction, CADE 1988
Country/TerritoryUnited States

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Recursive query answering with non-Horn clauses'. Together they form a unique fingerprint.

Cite this