Languages for Polynomial-Time Queries - An Ongoing Quest.

@inproceedings{DBLP:conf/icdt/Kolaitis95,
  author    = {Phokion G. Kolaitis},
  editor    = {Georg Gottlob and
               Moshe Y. Vardi},
  title     = {Languages for Polynomial-Time Queries - An Ongoing Quest},
  booktitle = {Database Theory - ICDT'95, 5th International Conference, Prague,
               Czech Republic, January 11-13, 1995, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {893},
  year      = {1995},
  isbn      = {3-540-58907-4},
  pages     = {38-39},
  ee        = {http://dx.doi.org/10.1007/3-540-58907-4_4},
  crossref  = {DBLP:conf/icdt/95},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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/An2-2 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/aDVD1 or /dvd

References

[1]

Serge Abiteboul, Victor Vianu: Generic Computation and Its Complexity. STOC 1991: 209-219

[2]

Foto N. Afrati, Stavros S. Cosmadakis, Mihalis Yannakakis: On Datalog vs. Polynomial Time. PODS 1991: 13-25

[3]

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

[4]

Jin-yi Cai, Martin Fürer, Neil Immerman: An Optimal Lower Bound on the Number of Variables for Graph Identification. FOCS 1989: 612-617

[5]

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

[6]

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

[7]

...

[8]

Ronald Fagin: Finite-Model Theory - A Personal Perspective. Theor. Comput. Sci. 116(1&2): 3-31(1993)

[9]

...

[10]

...

[11]

...

[12]

Lauri Hella: Logical Hierarchies in PTIME. LICS 1992: 360-368

[13]

Lauri Hella, Phokion G. Kolaitis, Kerkko Luosto: How to Define a Linear Order on Finite Models. LICS 1994: 40-49

[14]

...

[15]

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

[16]

...

[17]

Phokion G. Kolaitis, Jouko A. Väänänen: Generalized Quantifiers and Pebble Games on Finite Structures. LICS 1992: 348-359

[18]

...

[19]

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