Disjunctive Datalog.

@article{DBLP:journals/tods/EiterGM97,
  author    = {Thomas Eiter and
               Georg Gottlob and
               Heikki Mannila},
  title     = {Disjunctive Datalog},
  journal   = {ACM Trans. Database Syst.},
  volume    = {22},
  number    = {3},
  year      = {1997},
  pages     = {364-418},
  ee        = {http://doi.acm.org/10.1145/261124.261126, db/journals/tods/EiterGM97.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1997 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.

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An4-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

Online Edition: ACM Digital Library

References

[Abiteboul et al. 1990]

Serge Abiteboul, Eric Simon, Victor Vianu: Non-Deterministic Languages to Express Deterministic Transformations. PODS 1990: 218-229 BibTeX

[Abiteboul et al. 1995]

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX

[Balcázar et al. 1992]

...

[Baral and Gelfond 1994]

Chitta Baral, Michael Gelfond: Logic Programming and Knowledge Representation. J. Log. Program. 19/20: 73-148(1994) BibTeX

[Baral and Subrahmanian 1992]

Chitta Baral, V. S. Subrahmanian: Stable and Extension Class Theory for Logic Programs and Default Logics. J. Autom. Reasoning 8(3): 345-366(1992) BibTeX

[Bell et al. 1994]

Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Mixed Integer Programming Methods for Computing Nonmonotonic Deductive Databases. J. ACM 41(6): 1178-1215(1994) BibTeX

[Bell et al. 1996]

Colin Bell, Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Implementing Deductive Databases by Mixed Integer Programming. ACM Trans. Database Syst. 21(2): 238-269(1996) BibTeX

[Ben-Eliyahu and Dechter 1994]

...

[Ben-Eliyahu and Palopoli 1994]

Rachel Ben-Eliyahu, Luigi Palopoli: Reasoning with Minimal Models: Efficient Algorithms and Applications. KR 1994: 39-50 BibTeX

[Bidoit and Froidevaux 1987]

Nicole Bidoit, Christine Froidevaux: Minimalism subsumes Default Logic and Circumscription in Stratified Logic Programming. LICS 1987: 89-97 BibTeX

[Bidoit and Froidevaux 1991]

Nicole Bidoit, Christine Froidevaux: General Logical Databases and Programs: Default Logic Semantics and Stratification. Inf. Comput. 91(1): 15-54(1991) BibTeX

[Bonatti and Eiter 1995]

Piero A. Bonatti, Thomas Eiter: Querying Disjunctive Databases Through Nonmonotonic Logics. Theor. Comput. Sci. 160(1&2): 321-363(1996) BibTeX

[Borgida 1995]

Alexander Borgida: Description Logics in Data Management. IEEE Trans. Knowl. Data Eng. 7(5): 671-682(1995) BibTeX

[Brass and Dix 1995]

Stefan Brass, Jürgen Dix: Disjunctive Semantics based upon Partial and Bottom-Up Evaluation. ICLP 1995: 199-213 BibTeX

[Brass and Dix 1997]

...

[Brass et al. 1996b]

...

[Brass et al. 1996a]

Stefan Brass, Jürgen Dix, Teodor C. Przymusinski: Super Logic Programs. KR 1996: 529-540 BibTeX

[Cadoli et al. 1994]

Marco Cadoli, Thomas Eiter, Georg Gottlob: Default Logic as a Query Language. IEEE Trans. Knowl. Data Eng. 9(3): 448-463(1997) BibTeX

[Ceri et al. 1990]

Stefano Ceri, Georg Gottlob, Letizia Tanca: Logic Programming and Databases. Springer 1990, ISBN 3-540-51728-6
BibTeX

[Chandra and Harel 1982]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[Chandra and Harel 1985]

Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX

[Chen 1993]

Jianhua Chen: Minimal Knowledge + Negation as Failure = Only Knowing (Sometimes). LPNMR 1993: 132-150 BibTeX

[Cholewinski 1995]

Pawel Cholewinski: Reasoning with Stratified Default Theories. LPNMR 1995: 273-286 BibTeX

[Chomicki and Subrahmanian 1990]

Jan Chomicki, V. S. Subrahmanian: Generalized Closed World Assumptions is Pi^0_2-Complete. Inf. Process. Lett. 34(6): 289-291(1990) BibTeX

[Cullum and Willoughby 1985]

...

[Dawar 1995]

Anuj Dawar: A Restricted Second Order Logic for Finite Structures. LCC 1994: 393-413 BibTeX

[Dix 1992]

Jürgen Dix: Classifying Semantics of Disjunctive Logic Programs. JICSLP 1992: 798-812 BibTeX

[Dix and Müller 1993]

Martin Müller, Jürgen Dix: Implementing Semantics of Disjunctive Logic Programs Using Fringes and Abstract Properties (Extended Abstract). LPNMR 1993: 43-59 BibTeX

[Dix et al. 1996]

...

[Doyle and Patil 1991]

Jon Doyle, Ramesh S. Patil: Two Theses of Knowledge Representation: Language Restrictions, Taxonomic Classification, and the Utility of Representation Services. Artif. Intell. 48(3): 261-297(1991) BibTeX

[Eiter and Gottlob 1995a]

...

[Eiter and Gottlob 1995b]

...

[Eiter et al. 1996]

...

[Eiter et al. 1994]

Thomas Eiter, Georg Gottlob, Heikki Mannila: Adding Disjunction to Datalog. PODS 1994: 267-278 BibTeX

[Eiter et al. 1996]

Thomas Eiter, Nicola Leone, Domenico Saccà: The Expressive Power of Partial Models in Disjunctive Deductive Databases. Logic in Databases 1996: 245-264 BibTeX

[Fagin 1974]

...

[Gelfond and Lifschitz 1988]

Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX

[Gelfond and Lifschitz 1991]

Michael Gelfond, Vladimir Lifschitz: Classical Negation in Logic Programs and Disjunctive Databases. New Generation Comput. 9(3/4): 365-386(1991) BibTeX

[Gottlob 1995]

Georg Gottlob: Translating Default Logic into Standard Autoepistemic Logic. J. ACM 42(4): 711-740(1995) BibTeX

[Gottlob et al. 1995]

Georg Gottlob, Nicola Leone, Helmut Veith: Second Order Logic and the Weak Exponential Hierarchies. MFCS 1995: 66-81 BibTeX

[Gurevich 1988]

...

[Imielinski and Lipski 1984]

Tomasz Imielinski, Witold Lipski Jr.: The Relational Model of Data and Cylindric Algebras. J. Comput. Syst. Sci. 28(1): 80-102(1984) BibTeX

[Immerman 1986]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX

[Kanellakis 1990]

...

[Kifer et al. 1995]

Michael Kifer, Georg Lausen, James Wu: Logical Foundations of Object-Oriented and Frame-Based Languages. J. ACM 42(4): 741-843(1995) BibTeX

[Kolaitis 1991]

Phokion G. Kolaitis: The Expressive Power of Stratified Programs. Inf. Comput. 90(1): 50-66(1991) BibTeX

[Kolaitis and Papadimitriou 1991]

Phokion G. Kolaitis, Christos H. Papadimitriou: Why not Negation by Fixpoint? J. Comput. Syst. Sci. 43(1): 125-144(1991) BibTeX

[Kolaitis and Vardi 1992]

Phokion G. Kolaitis, Moshe Y. Vardi: Fixpoint Logic vs. Infinitary Logic in Finite-Model Theory. LICS 1992: 46-57 BibTeX

[Kolaitis and Vardi 1995]

Phokion G. Kolaitis, Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. J. Comput. Syst. Sci. 51(1): 110-134(1995) BibTeX

[Krentel 1988]

Mark W. Krentel: The Complexity of Optimization Problems. J. Comput. Syst. Sci. 36(3): 490-509(1988) BibTeX

[Leone et al. 1995]

...

[Lifschitz and Turner 1993b]

...

[Lifschitz and Turner 1994]

Vladimir Lifschitz, Hudson Turner: Splitting a Logic Program. ICLP 1994: 23-37 BibTeX

[Lloyd 1984]

John W. Lloyd: Foundations of Logic Programming, 1st Edition. Springer 1984, ISBN 3-540-13299-6
BibTeX

[Lobo et al. 1992]

...

[Maier and Vance 1993]

David Maier, Bennet Vance: A Call to Order. PODS 1993: 1-16 BibTeX

[McCarthy 1986]

John McCarthy: Applications of Circumscription to Formalizing Common-Sense Knowledge. Artif. Intell. 28(1): 89-116(1986) BibTeX

[Minker 1982]

Jack Minker: On Indefinite Databases and the Closed World Assumption. CADE 1982: 292-308 BibTeX

[Minker 1994]

...

[Moore 1985]

Robert C. Moore: Semantical Considerations on Nonmonotonic Logic. Artif. Intell. 25(1): 75-94(1985) BibTeX

[Nerode et al. 1995]

Anil Nerode, Raymond T. Ng, V. S. Subrahmanian: Computing Circumscriptive Databases: I. Theory and Algorithms. Inf. Comput. 116(1): 58-80(1995) BibTeX

[Papadimitriou 1984]

Christos H. Papadimitriou: On the complexity of unique solutions. J. ACM 31(2): 392-400(1984) BibTeX

[Papadimitriou 1994]

...

[Papadimitriou and Yannakakis 1985]

Christos H. Papadimitriou, Mihalis Yannakakis: A Note on Succinct Representations of Graphs. Information and Control 71(3): 181-185(1986) BibTeX

[Przymusinski 1988]

Teodor C. Przymusinski: On the Declarative Semantics of Deductive Databases and Logic Programs. Foundations of Deductive Databases and Logic Programming. 1988: 193-216 BibTeX

[Przymusinski 1991]

Teodor C. Przymusinski: Stable Semantics for Disjunctive Programs. New Generation Comput. 9(3/4): 401-424(1991) BibTeX

[Przymusinski 1994]

Teodor C. Przymusinski: A Knowledge Representation Framework Based on Autoepistemic Logic of Minimal Beliefs. AAAI 1994: 952-958 BibTeX

[Przymusinski 1995]

...

[Reiter 1980]

Raymond Reiter: A Logic for Default Reasoning. Artif. Intell. 13(1-2): 81-132(1980) BibTeX

[Ross 1994]

Kenneth A. Ross: Modular Stratification and Magic Sets for Datalog Programs with Negation. J. ACM 41(6): 1216-1266(1994) BibTeX

[Saccà 1997]

Domenico Saccà: The Expressive Powers of Stable Models for Bound and Unbound DATALOG Queries. J. Comput. Syst. Sci. 54(3): 441-464(1997) BibTeX

[Saccà and Zaniolo 1990]

Domenico Saccà, Carlo Zaniolo: Stable Models and Non-Determinism in Logic Programs with Negation. PODS 1990: 205-217 BibTeX

[Sakama and Inoue 1993]

Chiaki Sakama, Katsumi Inoue: Relating Disjunctive Logic Programs to Default Theories. LPNMR 1993: 266-282 BibTeX

[Sakama and Inoue 1994]

Chiaki Sakama, Katsumi Inoue: An Alternative Approach to the Semantics of Disjunctive Logic Programs and Deductive Databases. J. Autom. Reasoning 13(1): 145-172(1994) BibTeX

[Sakama and Inoue 1995]

Chiaki Sakama, Katsumi Inoue: Paraconsistent Stable Semantics for Extended Disjunctive Programs. J. Log. Comput. 5(3): 265-285(1995) BibTeX

[Schlipf 1987]

...

[Schlipf 1995a]

...

[Schlipf 1995b]

John S. Schlipf: The Expressive Powers of the Logic Programming Semantics. J. Comput. Syst. Sci. 51(1): 64-86(1995) BibTeX

[Seipel 1994]

...

[Stewart 1991]

Iain A. Stewart: Complete Problems Involving Boolean Labelled Structures and Projection Transactions. J. Log. Comput. 1(6): 861-882(1991) BibTeX

[Stockmeyer 1977]

Larry J. Stockmeyer: The Polynomial-Time Hierarchy. Theor. Comput. Sci. 3(1): 1-22(1976) BibTeX

[Turner 1996]

...

[Ullman 1989]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[Van Gelder et al. 1991]

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

[Vardi 1982]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[Veith 1994]

...

[Veith 1996]

...

[Wolfinger 1994]

...

[Yahya and Henschen 1985]

Adnan H. Yahya, Lawrence J. Henschen: Deduction in Non-Horn Databases. J. Autom. Reasoning 1(2): 141-160(1985) BibTeX

[You and Yuan 1993]

Li-Yan Yuan, Jia-Huai You: Autoepistemic Circumscription and Logic Programming. J. Autom. Reasoning 10(2): 143-160(1993) BibTeX

[You and Yuan 1995]

Li-Yan Yuan, Jia-Huai You: On the Extension of Logic Programming with Negation through Uniform Proofs. LPNMR 1995: 231-244 BibTeX

Referenced by

1. Sergio Greco: Binding Propagation in Disjunctive Databases. VLDB 1998: 287-298
2. Marco Cadoli, Luigi Palopoli, Maurizio Lenzerini: Datalog and Description Logics: Expressive Power. DBPL 1997: 281-298