ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Hypothetical Datalog: Negation and Linear Recursion.

Anthony J. Bonner: Hypothetical Datalog: Negation and Linear Recursion. PODS 1989: 286-300
@inproceedings{DBLP:conf/pods/Bonner89,
  author    = {Anthony J. Bonner},
  title     = {Hypothetical Datalog: Negation and Linear Recursion},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {286-300},
  ee        = {http://doi.acm.org/10.1145/73721.73750, db/conf/pods/Bonner89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper examines an extension of Horn logic in which rules can add entries to a database hypothetically. Several researchers have developed logical systems along these lines, but the complexity and expressibility of such logics is only now being explored. It has been shown, for instance, that the data-complexity of these logics is PSPACE-complete in the function-free, predicate case. This paper extends this line of research by developing syntactic restrictions with lower complexity. These restrictions are based on two ideas from Horn-clause logic: linear recursion and stratified negation. In particular, a notion of stratification is developed in which negation-as-failure alternates with linear recursion. The complexity of such rulebases depends on the number of layers of stratification. The result is a hierarchy of syntactic classes which corresponds exactly to the polynomial-time hierarchy of complexity classes. In particular, rulebases with k strata are data-complete for SigmaPk. Furthermore, these rulebases provide a complete characterization of the relational queries in SigmaPk. That is, any query whose graph is in SigmaPk can be represented as a set of hypothetical rules with k strata. Unlike other expressibility results in the literature, this result does not require the data domain to be linearly ordered.

Copyright © 1989 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents BibTeX

Online Edition: ACM Digital Library

References

[1]
...
[2]
François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52 BibTeX
[3]
Anthony J. Bonner: A Logic for Hypothetical Reasoning. AAAI 1988: 480-484 BibTeX
[4]
Anthony J. Bonner: Hypothetical Datalog: Complexity and Expressiblity. ICDT 1988: 144-160 BibTeX
[5]
Anthony J. Bonner: Hypothetical Datalog: Complexity and Expressibility. Theor. Comput. Sci. 76(1): 3-51(1990) BibTeX
[6]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[7]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. FOCS 1980: 333-347 BibTeX
[8]
Dov M. Gabbay: N-Prolog: An Extension of Prolog with Hypothetical Implication II - Logical Foundations, and Negation as Failure. J. Log. Program. 2(4): 251-283(1985) BibTeX
[9]
Dov M. Gabbay, Uwe Reyle: N-Prolog: An Extension of Prolog with Hypothetical Implications I. J. Log. Program. 1(4): 319-355(1984) BibTeX
[10]
M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX
[11]
...
[12]
John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
BibTeX
[13]
Neil Immerman: Relational Queries Computable in Polynomial Time (Extended Abstract). STOC 1982: 147-152 BibTeX
[14]
...
[15]
...
[16]
L. Thorne McCarty: Clausal Intuitionistic Logic I - Fixed-Point Semantics. J. Log. Program. 5(1): 1-31(1988) BibTeX
[17]
L. Thorne McCarty: Clausal Intuitionistic Logic II - Tableau Proof Procedures. J. Log. Program. 5(2): 93-132(1988) BibTeX
[18]
...
[19]
Dale Miller: A Theory of Modules for Logic Programming. SLP 1986: 106-114 BibTeX
[20]
...
[21]
Larry J. Stockmeyer: The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3(1): 1-22(1976) BibTeX
[22]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
[23]
David Scott Warren: Database Updates in Pure Prolog. FGCS 1984: 244-253 BibTeX

Referenced by

  1. Thomas Eiter, Georg Gottlob: On the Complexity of Propositional Knowledge Base Revision, Updates, and Counterfactuals. PODS 1992: 261-273
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:33:57 2009