On Datalog vs. Polynomial Time.

Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis: On Datalog vs. Polynomial Time. PODS 1991: 13-25
  author    = {Foto N. Afrati and
               Stavros S. Cosmadakis and
               Mihalis Yannakakis},
  title     = {On Datalog vs. Polynomial Time},
  booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
               Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
  publisher = {ACM Press},
  year      = {1991},
  isbn      = {0-89791-430-9},
  pages     = {13-25},
  ee        = {, db/conf/pods/AfratiCY91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP,}


We show that certain monotonic polynomial time queries are not expressible in variants of Datalog. The proof techniques include lower bounds for monotone circuit size and a "Pumping Lemma" for Datalog queries.

Copyright © 1991 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 Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado. ACM Press 1991, ISBN 0-89791-430-9
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1125 KB]


Foto N. Afrati, Stavros S. Cosmadakis: Expressiveness of Restricted Recursive Queries (Extended Abstract). STOC 1989: 113-126 BibTeX
Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX
Miklós Ajtai, Yuri Gurevich: Datalog vs. First-Order Logic. FOCS 1989: 142-147 BibTeX
Esther M. Arkin, Christos H. Papadimitriou, Mihalis Yannakakis: Modularity of Cycles and Paths in Graphs. J. ACM 38(2): 255-274(1991) BibTeX
Ashok K. Chandra, David Harel: Horn Clauses Queries and Generalizations. J. Log. Program. 2(1): 1-15(1985) BibTeX
Steven Fortune, John E. Hopcroft, James Wyllie: The Directed Subgraph Homeomorphism Problem. Theor. Comput. Sci. 10: 111-121(1980) BibTeX
M. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1(3): 237-267(1976) BibTeX
Neil Immerman: Upper and Lower Bounds for First Order Expressibility. J. Comput. Syst. Sci. 25(1): 76-98(1982) BibTeX
Phokion G. Kolaitis, Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. PODS 1990: 61-71 BibTeX
V. S. Lakshmanan, Alberto O. Mendelzon: Inductive Pebble Games and the Expressive Power of Datalog. PODS 1989: 301-310 BibTeX
Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX
Sven Skyum, Leslie G. Valiant: A Complexity Theory Based on Boolean Algebra. J. ACM 32(2): 484-502(1985) BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX
Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX
Leslie G. Valiant: Completeness Classes in Algebra. STOC 1979: 249-261 BibTeX

Referenced by

  1. Phokion G. Kolaitis: Combinatorial Games In Database Theory. PODS 1995: 231-232
  2. Phokion G. Kolaitis: Languages for Polynomial-Time Queries - An Ongoing Quest. ICDT 1995: 38-39
  3. Sergio Greco, Domenico Saccà, Carlo Zaniolo: DATALOG Queries with Stratified Negation and Choice: from P to DP. ICDT 1995: 82-96
  4. Luca Cabibbo: On the Power of Stratified Logic Programs with Value Invention for Expressing Database Transformations. ICDT 1995: 208-221
  5. Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
  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
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:02 2009