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},
editor = {Catriel Beeri},
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, USA},
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}
}
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 ...
Printed Edition
Catriel Beeri (Ed.):
Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 25-28, 1993, Washington, DC, USA.
ACM Press 1993, ISBN 0-89791-593-3
Contents 
[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)
- [3]
- Marco Cadoli, Maurizio Lenzerini:
The Complexity of Closed World Reasoning and Circumscription.
AAAI 1990: 550-555
- [4]
- Marco Cadoli, Marco Schaerf:
A Survey of Complexity Results for Nonmonotonic Logics.
J. Log. Program. 17(2/3&4): 127-160(1993)
- [5]
- Edward P. F. Chan:
A Possible World Semantics for Disjunctive Databases.
IEEE Trans. Knowl. Data Eng. 5(2): 282-292(1993)
- [6]
- Ashok K. Chandra, David Harel:
Horn Clauses Queries and Generalizations.
J. Log. Program. 2(1): 1-15(1985)
- [7]
- Thomas Eiter, Georg Gottlob:
Propositional Circumscription and Extended Closed-World Reasoning are IIp2-Complete.
Theor. Comput. Sci. 114(2): 231-245(1993)
- [8]
- ...
- [9]
- José Alberto Fernández, Jack Minker:
Semantics of Disjunctive Deductive Databases.
ICDT 1992: 21-50
- [10]
- Michael Gelfond, Vladimir Lifschitz:
The Stable Model Semantics for Logic Programming.
ICLP/SLP 1988: 1070-1080
- [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)
- [13]
- ...
- [14]
- ...
- [15]
- V. Wiktor Marek, Miroslaw Truszczynski:
Autoepistemic Logic.
J. ACM 38(3): 588-619(1991)
- [16]
- Jack Minker:
On Indefinite Databases and the Closed World Assumption.
CADE 1982: 292-308
- [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)
- [19]
- ...
- [20]
- Teodor C. Przymusinski:
Stable Semantics for Disjunctive Programs.
New Generation Comput. 9(3/4): 401-424(1991)
- [21]
- Arcot Rajasekar, Jorge Lobo, Jack Minker:
Weak Generalized Closed World Assumption.
J. Autom. Reasoning 5(3): 293-307(1989)
- [22]
- ...
- [23]
- Kenneth A. Ross, Rodney W. Topor:
Inferring Negative Information from Disjunctive Databases.
J. Autom. Reasoning 4(4): 397-424(1988)
- [24]
- Chiaki Sakama:
Possible Model Semantics for Disjunctive Databases.
DOOD 1989: 369-383
- [25]
- ...
- [26]
- Marco Schaerf:
Negation and Minimality in Non-Horn Databases.
PODS 1993: 147-157
- [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)
- [30]
- Adnan H. Yahya, Lawrence J. Henschen:
Deduction in Non-Horn Databases.
J. Autom. Reasoning 1(2): 141-160(1985)
Referenced by
- Marco Cadoli, Thomas Eiter, Georg Gottlob:
Default Logic as a Query Language.
IEEE Trans. Knowl. Data Eng. 9(3): 448-463(1997)
- Thomas Eiter, Georg Gottlob, Heikki Mannila:
Adding Disjunction to Datalog.
PODS 1994: 267-278
- Marco Schaerf:
Negation and Minimality in Non-Horn Databases.
PODS 1993: 147-157
Last update Fri May 25 08:32:46 2012
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
