On Datalog vs. Polynomial Time.

@inproceedings{DBLP:conf/pods/AfratiCY91,
  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        = {http://doi.acm.org/10.1145/113413.113415, db/conf/pods/AfratiCY91.html},
  crossref  = {DBLP:conf/pods/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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.

• 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
• UNIX/LINUX/Mac: use mount point /pods8298/... 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
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[AC89]

Foto N. Afrati, Stavros S. Cosmadakis: Expressiveness of Restricted Recursive Queries (Extended Abstract). STOC 1989: 113-126 BibTeX

[AH79]

Alfred V. Aho, Jeffrey D. Ullman: The Universality of Data Retrieval Languages. POPL 1979: 110-120 BibTeX

[AG89]

Miklós Ajtai, Yuri Gurevich: Datalog vs. First-Order Logic. FOCS 1989: 142-147 BibTeX

[AB87]

...

[APY86]

Esther M. Arkin, Christos H. Papadimitriou, Mihalis Yannakakis: Modularity of Cycles and Paths in Graphs. J. ACM 38(2): 255-274(1991) BibTeX

[BS90]

...

[CH85]

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

[FHW80]

Steven Fortune, John E. Hopcroft, James Wyllie: The Directed Subgraph Homeomorphism Problem. Theor. Comput. Sci. 10: 111-121(1980) BibTeX

[GJS76]

M. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1(3): 237-267(1976) BibTeX

[Imm82]

Neil Immerman: Upper and Lower Bounds for First Order Expressibility. J. Comput. Syst. Sci. 25(1): 76-98(1982) BibTeX

[Ko89]

...

[KV90]

Phokion G. Kolaitis, Moshe Y. Vardi: On the Expressive Power of Datalog: Tools and a Case Study. PODS 1990: 61-71 BibTeX

[LM89]

V. S. Lakshmanan, Alberto O. Mendelzon: Inductive Pebble Games and the Expressive Power of Datalog. PODS 1989: 301-310 BibTeX

[LP84]

...

[LP81]

...

[NZ67]

...

[Pa85]

...

[Ra85a]

...

[Ra85b]

...

[Shm87]

Oded Shmueli: Decidability and Expressiveness of Logic Queries. PODS 1987: 237-249 BibTeX

[SV85]

Sven Skyum, Leslie G. Valiant: A Complexity Theory Based on Boolean Algebra. J. ACM 32(2): 484-502(1985) BibTeX

[Ull89a]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[Ull89b]

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

[Va79]

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 D^P. 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
   Contents
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