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

On the Expressive Power of Datalog: Tools and a Case Study.

Phokion G. Kolaitis, Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. PODS 1990: 61-71
@inproceedings{DBLP:conf/pods/KolaitisV90,
  author    = {Phokion G. Kolaitis and
               Moshe Y. Vardi},
  title     = {On the Expressive Power of Datalog: Tools and a Case Study},
  booktitle = {Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee},
  publisher = {ACM Press},
  year      = {1990},
  isbn      = {0-89791-352-3},
  pages     = {61-71},
  ee        = {http://doi.acm.org/10.1145/298514.298542, db/conf/pods/KolaitisV90.html},
  crossref  = {DBLP:conf/pods/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We study here the language Datalog(!=), which is the query language obtained from Datalog by allowing equalities and inequalities in the bodies of the rules. We view Datalog(!=) as a fragment of an infinitary logic Lomega and show that Lomega can be characterized in terms of certain two-person pebble games. This characterization provides us with tools for investigating the expressive power of Datalog(!=). As a case study, we classify the expressibility of fixed subgraph homomorphism queries on directed graphs. Fortune et al. [FHW80] classified the computational complexity of these queries by establishing two dichotomies, which are proper only if P != NP. Without using any complexity-theoretic assumptions, we show here that the two dichotomies are indeed proper in terms of expressibility in Datalog(!=).

Copyright © 1990 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 Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee. ACM Press 1990, ISBN 0-89791-352-3
Contents BibTeX

Journal Version

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

Online Edition: ACM Digital Library

References

[AG89]
Miklós Ajtai, Yuri Gurevich: Datalog vs. First-Order Logic. FOCS 1989: 142-147 BibTeX
[AU79]
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
[Bar77]
...
[BG87]
...
[Bol79]
...
[CH80]
Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980) BibTeX
[CH82]
Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX
[CH85]
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
[Coo74]
Stephen A. Cook: An Observation on Time-Storage Trade Off. J. Comput. Syst. Sci. 9(3): 308-316(1974) BibTeX
[DeR87]
...
[FHW80]
Steven Fortune, John E. Hopcroft, James Wyllie: The Directed Subgraph Homeomorphism Problem. Theor. Comput. Sci. 10: 111-121(1980) BibTeX
[Gai82]
...
[GMSV87]
Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 BibTeX
[GS53]
...
[GS86]
...
[Imm82]
Neil Immerman: Upper and Lower Bounds for First Order Expressibility. J. Comput. Syst. Sci. 25(1): 76-98(1982) BibTeX
[Imm86]
Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX
[Kei71]
...
[Kol85]
...
[KV89]
Phokion G. Kolaitis, Moshe Y. Vardi: 0-1 Laws for Infinitary Logics (Preliminary Report). LICS 1990: 156-167 BibTeX
[LM89]
V. S. Lakshmanan, Alberto O. Mendelzon: Inductive Pebble Games and the Expressive Power of Datalog. PODS 1989: 301-310 BibTeX
[Mos74]
...
[Pap85]
...
[Shm87]
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX
[Ull88]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
[Ull89]
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
[Var82]
Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

Referenced by

  1. Jerzy Tyszkiewicz: Fine Hierarchies of Generic Computation. ICDT 1997: 125-139
  2. Piero A. Bonatti, Thomas Eiter: Querying Disjunctive Database Through Nonmonotonic Logics. ICDT 1995: 68-81
  3. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
    Contents
  4. Thomas Eiter, Georg Gottlob, Heikki Mannila: Adding Disjunction to Datalog. PODS 1994: 267-278
  5. Surajit Chaudhuri, Phokion G. Kolaitis: Can Datalog be Approximated? PODS 1994: 86-96
  6. Foto N. Afrati: Bounded Arity Datalog (!=) Queries on Graphs. PODS 1994: 97-106
  7. Guozhu Dong: Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations. PODS 1992: 81-90
  8. Stéphane Grumbach: A Paradox in Database Theory. ICDT 1992: 312-325
  9. Serge Abiteboul, Moshe Y. Vardi, Victor Vianu: Computing with Infinitary Logic. ICDT 1992: 113-123
  10. Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis: On Datalog vs. Polynomial Time. PODS 1991: 13-25
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:33:58 2009