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

Complexity Aspects of Various Semantics for Disjunctive Databases.

Thomas Eiter, Georg Gottlob: Complexity Aspects of Various Semantics for Disjunctive Databases. PODS 1993: 158-167
@inproceedings{DBLP:conf/pods/EiterG93,
  author    = {Thomas Eiter and
               Georg Gottlob},
  title     = {Complexity Aspects of Various Semantics for Disjunctive 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     = {158-167},
  ee        = {http://doi.acm.org/10.1145/153850.153864, db/conf/pods/EiterG93.html},
  crossref  = {DBLP:conf/pods/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

This paper addresses complexity issues for important problems arising with disjunctive databases. In particular, the complexity of inference of a literal and a formula from a propositional disjunctive database under a variety of well-known disjunctive database semantics is investigated, as well deciding whether a disjunctive database has a model under a particular semantics. The problems are located in appropriate slots of the polynomial hierarchy.

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

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 839 KB]

References

[1]
...
[2]
Nicole Bidoit, Christine Froidevaux: Negation by Default and Unstratifiable Logic Programs. Theor. Comput. Sci. 78(1): 86-112(1991) BibTeX
[3]
Marco Cadoli, Maurizio Lenzerini: The Complexity of Closed World Reasoning and Circumscription. AAAI 1990: 550-555 BibTeX
[4]
Marco Cadoli, Marco Schaerf: A Survey of Complexity Results for Nonmonotonic Logics. J. Log. Program. 17(2/3&4): 127-160(1993) BibTeX
[5]
Edward P. F. Chan: A Possible World Semantics for Disjunctive Databases. IEEE Trans. Knowl. Data Eng. 5(2): 282-292(1993) BibTeX
[6]
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
[7]
Thomas Eiter, Georg Gottlob: Propositional Circumscription and Extended Closed-World Reasoning are IIp2-Complete. Theor. Comput. Sci. 114(2): 231-245(1993) BibTeX
[8]
...
[9]
José Alberto Fernández, Jack Minker: Semantics of Disjunctive Deductive Databases. ICDT 1992: 21-50 BibTeX
[10]
Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[11]
...
[12]
Michael Gelfond, Halina Przymusinska, Teodor C. Przymusinski: On the Relationship Between Circumscription and Negation as Failure. Artif. Intell. 38(1): 75-94(1989) BibTeX
[13]
...
[14]
...
[15]
V. Wiktor Marek, Miroslaw Truszczynski: Autoepistemic Logic. J. ACM 38(3): 588-619(1991) BibTeX
[16]
Jack Minker: On Indefinite Databases and the Closed World Assumption. CADE 1982: 292-308 BibTeX
[17]
...
[18]
Christos H. Papadimitriou, Mihalis Yannakakis: The Complexity of Facets (and Some Facets of Complexity). J. Comput. Syst. Sci. 28(2): 244-259(1984) BibTeX
[19]
...
[20]
Teodor C. Przymusinski: Stable Semantics for Disjunctive Programs. New Generation Comput. 9(3/4): 401-424(1991) BibTeX
[21]
Arcot Rajasekar, Jorge Lobo, Jack Minker: Weak Generalized Closed World Assumption. J. Autom. Reasoning 5(3): 293-307(1989) BibTeX
[22]
...
[23]
Kenneth A. Ross, Rodney W. Topor: Inferring Negative Information from Disjunctive Databases. J. Autom. Reasoning 4(4): 397-424(1988) BibTeX
[24]
Chiaki Sakama: Possible Model Semantics for Disjunctive Databases. DOOD 1989: 369-383 BibTeX
[25]
...
[26]
Marco Schaerf: Negation and Minimality in Non-Horn Databases. PODS 1993: 147-157 BibTeX
[27]
...
[28]
...
[29]
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
[30]
Adnan H. Yahya, Lawrence J. Henschen: Deduction in Non-Horn Databases. J. Autom. Reasoning 1(2): 141-160(1985) BibTeX

Referenced by

  1. Marco Cadoli, Thomas Eiter, Georg Gottlob: Default Logic as a Query Language. IEEE Trans. Knowl. Data Eng. 9(3): 448-463(1997)
  2. Thomas Eiter, Georg Gottlob, Heikki Mannila: Adding Disjunction to Datalog. PODS 1994: 267-278
  3. Marco Schaerf: Negation and Minimality in Non-Horn Databases. PODS 1993: 147-157
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