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

Stable Models and Non-Determinism in Logic Programs with Negation.

Domenico Saccà, Carlo Zaniolo: Stable Models and Non-Determinism in Logic Programs with Negation. PODS 1990: 205-217
@inproceedings{DBLP:conf/pods/SaccaZ90,
  author    = {Domenico Sacc{\`a} and
               Carlo Zaniolo},
  title     = {Stable Models and Non-Determinism in Logic Programs with Negation},
  booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
  publisher = {ACM Press},
  year      = {1990},
  isbn      = {0-89791-352-3},
  pages     = {205-217},
  ee        = {http://doi.acm.org/10.1145/298514.298572, db/conf/pods/SaccaZ90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Previous researchers have proposed generalizations of Horn clause logic to support negation and nondeterminism as two separate extensions. In this paper, we show that the stable model semantics for logic programs provides a unified basis for the treatment of both concepts. First, we introduce the concepts of partial models, stable models, strongly founded models and deterministic models and other interesting classes of partial models and study their relationships. We show that the maximal deterministic model of a program is a subset of the intersection of all its stable models and that the well-founded model of a program is a subset of its maximal deterministic model. Then, we show that the use of stable models subsumes the use of the non-deterministic choice construct in LDL and provides an alternative definition of the semantics of this construct. Finally, we provide a constructive definition for stable models with the introduction of a procedure, called backtracking fixpoint, that nondeterministically constructs a total stable model, if such a model exists.

Copyright © 1990 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 Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee. ACM Press 1990, ISBN 0-89791-352-3
Contents BibTeX

Online Edition: ACM Digital Library


References

[AV]
Serge Abiteboul, Victor Vianu: Fixpoint Extensions of First-Order Logic and Datalog-Like Languages. LICS 1989: 71-79 BibTeX
[ABW]
...
[CH]
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
[GL]
Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[KN]
Ravi Krishnamurthy, Shamim A. Naqvi: Non-Deterministic Choice in Datalog. JCDKB 1988: 416-424 BibTeX
[KP]
Phokion G. Kolaitis, Christos H. Papadimitriou: Why Not Negation by Fixpoint? PODS 1988: 231-239 BibTeX
[L]
John W. Lloyd: Foundations of Logic Programming, 2nd Edition. Springer 1987, ISBN 3-540-18199-7
BibTeX
[N]
...
[NT]
Shamim A. Naqvi, Shalom Tsur: A Logical Language for Data and Knowledge Bases. Computer Science Press 1989, ISBN 0-7167-8200-6
BibTeX
[P1]
...
[P2]
...
[P3]
Teodor C. Przymusinski: Perfect Model Semantics. ICLP/SLP 1988: 1081-1096 BibTeX
[P4]
Teodor C. Przymusinski: Every Logic Program Has a Natural Stratification And an Iterated Least Fixed Point Model. PODS 1989: 11-21 BibTeX
[P5]
...
[PP]
Halina Przymusinska, Teodor C. Przymusinski: Weakly Perfect Model Semantics for Logic Programs. ICLP/SLP 1988: 1106-1120 BibTeX
[R]
Kenneth A. Ross: A Procedural Semantics for Well Founded Negation in Logic Programs. PODS 1989: 22-33 BibTeX
[SZ]
...
[U1]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[U2]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[V1]
Allen Van Gelder: Negation as Failure Using Tight Derivations for General Logic Programs. SLP 1986: 127-138 BibTeX
[V2]
Allen Van Gelder: The Alternating Fixpoint of Logic Programs with Negation. PODS 1989: 1-10 BibTeX
[VRS]
Allen Van Gelder, Kenneth A. Ross, John S. Schlipf: Unfounded Sets and Well-Founded Semantics for General Logic Programs. PODS 1988: 221-230 BibTeX
[Z]
Carlo Zaniolo: Object Identity and Inheritance in Deductive Databases - an Evolutionary Approach. DOOD 1989: 7-21 BibTeX

Referenced by

  1. Li-Yan Yuan, Jia-Huai You: Coherence Approach to Logic Program Revision. IEEE Trans. Knowl. Data Eng. 10(1): 108-119(1998)
  2. Thomas Eiter, Georg Gottlob, Heikki Mannila: Disjunctive Datalog. ACM Trans. Database Syst. 22(3): 364-418(1997)
  3. Marco Cadoli, Thomas Eiter, Georg Gottlob: Default Logic as a Query Language. IEEE Trans. Knowl. Data Eng. 9(3): 448-463(1997)
  4. Weidong Chen, David Scott Warren: Computation of Stable Models and Its Integration with Logical Query Processing. IEEE Trans. Knowl. Data Eng. 8(5): 742-757(1996)
  5. V. S. Subrahmanian, Dana S. Nau, Carlo Vago: WFS + Branch and Bound = Stable Models. IEEE Trans. Knowl. Data Eng. 7(3): 362-377(1995)
  6. Jan Paredaens, Peter Peelman, Letizia Tanca: G-Log: A Graph-Based Query Language. IEEE Trans. Knowl. Data Eng. 7(3): 436-453(1995)
  7. Domenico Saccà: Deterministic and Non-Deterministic Stable Model Semantics for Unbound DATALOG Queries. ICDT 1995: 353-367
  8. Sergio Greco, Domenico Saccà, Carlo Zaniolo: DATALOG Queries with Stratified Negation and Choice: from P to DP. ICDT 1995: 82-96
  9. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  10. Marco Schaerf: Negation and Minimality in Non-Horn Databases. PODS 1993: 147-157
  11. Anthony J. Bonner, Michael Kifer, Mariano P. Consens: Database Programming in Transaction Logic. DBPL 1993: 309-337
  12. Sergio Greco, Carlo Zaniolo, Sumit Ganguly: Greedy by Choice. PODS 1992: 105-113
  13. Jan Van den Bussche, Dirk Van Gucht: Semi-determinism. PODS 1992: 191-201
  14. Catriel Beeri, Raghu Ramakrishnan, Divesh Srivastava, S. Sudarshan: The Valid Model Semantics for Logic Programs. PODS 1992: 91-104
  15. Serge Abiteboul, Allen Van Gelder: Optimizing Active Databases using the Split Technique. ICDT 1992: 171-187
  16. Yeh-Heng Sheng: A Non-deterministic Deductive Database Language. SIGMOD Conference 1991: 188-197
  17. Sumit Ganguly, Sergio Greco, Carlo Zaniolo: Minimum and Maximum Predicates in Logic Programming. PODS 1991: 154-163
  18. Els Laenens, Dirk Vermeir: On the Relationship between Well-Founded and Stable Partial Models. MFDBS 1991: 59-73
  19. Filippo Cacace, Stefano Ceri, Letizia Tanca: Consistency and Non-determinism in a Database Programming Language. MFDBS 1991: 325-341
  20. Els Laenens, Domenico Saccà, Dirk Vermeir: Extending Logic Programming. SIGMOD Conference 1990: 184-193
  21. Carlo Zaniolo: Deductive Databases - Theory Meets Practice. EDBT 1990: 1-15
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:34:00 2009