Adding Disjunction to Datalog.

Thomas Eiter, Georg Gottlob, Heikki Mannila: Adding Disjunction to Datalog. PODS 1994: 267-278
  author    = {Thomas Eiter and
               Georg Gottlob and
               Heikki Mannila},
  title     = {Adding Disjunction to Datalog},
  booktitle = {Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 24-26, 1994, Minneapolis,
  publisher = {ACM Press},
  year      = {1994},
  isbn      = {0-89791-642-5},
  pages     = {267-278},
  ee        = {, db/conf/pods/pods94-267.html},
  crossref  = {DBLP:conf/pods/94},
  bibsource = {DBLP,}


We study the expressive power and complexity of disjunctive datalog, i.e., datalog with disjunctive rule heads, under three different semantics: the minimal model semantics, the perfect models semantics, and the stable model semantics. We show that the brave variants of these semantics express the same set of queries. In fact, they precisely capture the complexity class \Sigmap2. The combined complexity of disjunctive datalog is shown to be NEXPTIMENP-complete.

Copyright © 1994 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 Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota. ACM Press 1994, ISBN 0-89791-642-5
Contents BibTeX

Online Edition: ACM Digital Library

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


Serge Abiteboul, Eric Simon, Victor Vianu: Non-Deterministic Languages to Express Deterministic Transformations. PODS 1990: 218-229 BibTeX
Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991) BibTeX
Nicole Bidoit, Christine Froidevaux: Minimalism subsumes Default Logic and Circumscription in Stratified Logic Programming. LICS 1987: 89-97 BibTeX
Marco Cadoli, Thomas Eiter, Georg Gottlob: Default Logic as a Query Language. KR 1994: 99-108 BibTeX
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
Jürgen Dix: Classifying Semantics of Disjunctive Logic Programs. JICSLP 1992: 798-812 BibTeX
Thomas Eiter, Georg Gottlob: Complexity Aspects of Various Semantics for Disjunctive Databases. PODS 1993: 158-167 BibTeX
Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
Richard Hull, Jianwen Su: On the Expressive Power of Database Queries with Intermediate Types. J. Comput. Syst. Sci. 43(1): 219-267(1991) BibTeX
Phokion G. Kolaitis, Christos H. Papadimitriou: Why not Negation by Fixpoint? J. Comput. Syst. Sci. 43(1): 125-144(1991) BibTeX
Phokion G. Kolaitis, Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. PODS 1990: 61-71 BibTeX
Phokion G. Kolaitis, Moshe Y. Vardi: Fixpoint Logic vs. Infinitary Logic in Finite-Model Theory. LICS 1992: 46-57 BibTeX
James F. Lynch: Complexity Classes and Theories of Finite Models. Mathematical Systems Theory 15(2): 127-144(1982) BibTeX
Jack Minker: On Indefinite Databases and the Closed World Assumption. CADE 1982: 292-308 BibTeX
David Maier, Bennet Vance: A Call to Order. PODS 1993: 1-16 BibTeX
Teodor C. Przymusinski: Stable Semantics for Disjunctive Programs. New Generation Comput. 9(3/4): 401-424(1991) BibTeX
Christos H. Papadimitriou, Mihalis Yannakakis: A Note on Succinct Representations of Graphs. Information and Control 71(3): 181-185(1986) BibTeX
John S. Schlipf: The Expressive Powers of the Logic Programming Semantics. J. Comput. Syst. Sci. 51(1): 64-86(1995) BibTeX
Iain A. Stewart: Complete Problems Involving Boolean Labelled Structures and Projection Transactions. J. Log. Comput. 1(6): 861-882(1991) BibTeX
Larry J. Stockmeyer: The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3(1): 1-22(1976) BibTeX
Dirk Van Gucht: On the Expressive Power of the Extended Relational Algebra for the Unnormalized Relational Model. PODS 1987: 302-312 BibTeX
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX
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
Jan Van den Bussche, Dirk Van Gucht, Marc Andries, Marc Gyssens: On the Completeness of Object-Creating Query Languages (Extended Abstract). FOCS 1992: 372-379 BibTeX
Adnan H. Yahya, Lawrence J. Henschen: Deduction in Non-Horn Databases. J. Autom. Reasoning 1(2): 141-160(1985) BibTeX

Referenced by

  1. Thomas Eiter, Georg Gottlob, Heikki Mannila: Disjunctive Datalog. ACM Trans. Database Syst. 22(3): 364-418(1997)
  2. Marco Cadoli, Thomas Eiter, Georg Gottlob: Default Logic as a Query Language. IEEE Trans. Knowl. Data Eng. 9(3): 448-463(1997)
  3. Domenico Saccà: Deterministic and Non-Deterministic Stable Model Semantics for Unbound DATALOG Queries. ICDT 1995: 353-367
  4. Piero A. Bonatti, Thomas Eiter: Querying Disjunctive Database Through Nonmonotonic Logics. ICDT 1995: 68-81
  5. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:34:11 2009