Negation and Minimality in Non-Horn Databases.
Marco Schaerf:
Negation and Minimality in Non-Horn Databases.
PODS 1993: 147-157@inproceedings{DBLP:conf/pods/Schaerf93,
author = {Marco Schaerf},
title = {Negation and Minimality in Non-Horn Databases},
booktitle = {Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium
on Principles of Database Systems, May 25-28, 1993, Washington,
DC},
publisher = {ACM Press},
year = {1993},
isbn = {0-89791-593-3},
pages = {147-157},
ee = {http://doi.acm.org/10.1145/153850.153863, db/conf/pods/Schaerf93.html},
crossref = {DBLP:conf/pods/93},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
Two main approaches have been followed in the literature to give a semantics to non-Horn databases.
The first one is based on considering the set of rules composing the programs as inference rules and interpreting the negation in the body as failure to prove.
The other approach is based on the so-called closed-world assumption and its objective is to define a stronger notion of consequence from a theory than the classical one, where, very roughly, negative information can be inferred whenever its positive counterpart cannot be deduced from the theory.
In this work we generalize the semantics for negation in logic programs, putting together the constructive nature of the rule-based deductive databases with the syntax-independence of the closed-world reasoning rules.
These generalized semantics are shown to be a well-motivated and well-founded alternative to closed-world assumptions since they enjoy nice semantic and computational properties.
Copyright © 1993 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 Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC.
ACM Press 1993, ISBN 0-89791-593-3
Contents BibTeX
[Abstract and Index Terms]
[Full Text in PDF Format, 1100 KB]
Journal Version
Marco Schaerf:
Negation and Minimality in Disjunctive Databases.
J. Log. Program. 23(1): 63-86(1995) BibTeX
References
- [ABW88]
- ...
- [BED92]
- Rachel Ben-Eliyahu, Rina Dechter:
Propositional Sematics for Disjunctive Logic Programs.
JICSLP 1992: 813-827 BibTeX
- [BH86]
- Nicole Bidoit, Richard Hull:
Positivism vs. Minimalism in Deductive Databases.
PODS 1986: 123-132 BibTeX
- [CL90]
- Marco Cadoli, Maurizio Lenzerini:
The Complexity of Propositional Closed World Reasoning and Circumscription.
J. Comput. Syst. Sci. 48(2): 255-310(1994) BibTeX
- [CS92]
- Marco Cadoli, Marco Schaerf:
A Survey of Complexity Results for Nonmonotonic Logics.
J. Log. Program. 17(2/3&4): 127-160(1993) BibTeX
- [EG91]
- Thomas Eiter, Georg Gottlob:
Propositional Circumscription and Extended Closed-World Reasoning are IIp2-Complete.
Theor. Comput. Sci. 114(2): 231-245(1993) BibTeX
- [EG92]
- Thomas Eiter, Georg Gottlob:
Complexity Results for Disjunctive Logic Programming and Application to Nonmonotonic Logics.
ILPS 1993: 266-278 BibTeX
- [EG93]
- Thomas Eiter, Georg Gottlob:
Complexity Aspects of Various Semantics for Disjunctive Databases.
PODS 1993: 158-167 BibTeX
- [GL88]
- Michael Gelfond, Vladimir Lifschitz:
The Stable Model Semantics for Logic Programming.
ICLP/SLP 1988: 1070-1080 BibTeX
- [GL91]
- Michael Gelfond, Vladimir Lifschitz:
Classical Negation in Logic Programs and Disjunctive Databases.
New Generation Comput. 9(3/4): 365-386(1991) BibTeX
- [GPP89]
- Michael Gelfond, Halina Przymusinska, Teodor C. Przymusinski:
On the Relationship Between Circumscription and Negation as Failure.
Artif. Intell. 38(1): 75-94(1989) BibTeX
- [KN88]
- Ravi Krishnamurthy, Shamim A. Naqvi:
Non-Deterministic Choice in Datalog.
JCDKB 1988: 416-424 BibTeX
- [Min82]
- Jack Minker:
On Indefinite Databases and the Closed World Assumption.
CADE 1982: 292-308 BibTeX
- [MT91a]
- V. Wiktor Marek, Miroslaw Truszczynski:
Autoepistemic Logic.
J. ACM 38(3): 588-619(1991) BibTeX
- [MT91b]
- V. Wiktor Marek, Miroslaw Truszczynski:
Computing Intersection of Autoepistemic Expansions.
LPNMR 1991: 37-50 BibTeX
- [Prz88]
- ...
- [Prz91a]
- Teodor C. Przymusinski:
Semantics of Disjunctive Logic Programs and Deductive Databases.
DOOD 1991: 85-107 BibTeX
- [Prz91b]
- Teodor C. Przymusinski:
Stable Semantics for Disjunctive Programs.
New Generation Comput. 9(3/4): 401-424(1991) BibTeX
- [PY92]
- Christos H. Papadimitriou, Mihalis Yannakakis:
Tie-Breaking Semantics and Structural Totality.
PODS 1992: 16-22 BibTeX
- [Rei78]
- ...
- [RLM89]
- Arcot Rajasekar, Jorge Lobo, Jack Minker:
Weak Generalized Closed World Assumption.
J. Autom. Reasoning 5(3): 293-307(1989) BibTeX
- [Sch92]
- ...
- [Sto76]
- Larry J. Stockmeyer:
The Polynomial-Time Hierarchy.
Theor. Comput. Sci. 3(1): 1-22(1976) BibTeX
- [SZ90]
- Domenico Saccà, Carlo Zaniolo:
Stable Models and Non-Determinism in Logic Programs with Negation.
PODS 1990: 205-217 BibTeX
- [vEK76]
- Maarten H. van Emden, Robert A. Kowalski:
The Semantics of Predicate Logic as a Programming Language.
J. ACM 23(4): 733-742(1976) BibTeX
- [vGRS91]
- Allen Van Gelder, Kenneth A. Ross, John S. Schlipf:
The Well-Founded Semantics for General Logic Programs.
J. ACM 38(3): 620-650(1991) BibTeX
- [YH85]
- Adnan H. Yahya, Lawrence J. Henschen:
Deduction in Non-Horn Databases.
J. Autom. Reasoning 1(2): 141-160(1985) BibTeX
Referenced by
- Thomas Eiter, Georg Gottlob:
Complexity Aspects of Various Semantics for Disjunctive Databases.
PODS 1993: 158-167
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:08 2009
