On the Kolmogorov Expressive Power of Boolean Query Languages.

@inproceedings{DBLP:conf/icdt/Tyszkiewicz95,
  author    = {Jerzy Tyszkiewicz},
  editor    = {Georg Gottlob and
               Moshe Y. Vardi},
  title     = {On the Kolmogorov Expressive Power of Boolean Query Languages},
  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     = {97-110},
  ee        = {http://dx.doi.org/10.1007/3-540-58907-4_9},
  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

[ACV]

Serge Abiteboul, Kevin J. Compton, Victor Vianu: Queries Are Easier Than You Thought (Probably). PODS 1992: 23-32

[AG]

Serge Abiteboul, Allen Van Gelder: Optimizing Active Databases using the Split Technique. ICDT 1992: 171-187

[AV1]

Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991)

[AV2]

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

[Ch]

Ashok K. Chandra: Programming Primitives for Database Languages. POPL 1981: 50-62

[CH]

Ashok K. Chandra, David Harel: Computable Queries for Relational Data Bases. J. Comput. Syst. Sci. 21(2): 156-178(1980)

[D]

...

[GS]

...

[I]

Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987)

[LV1]

Ming Li, Paul M. B. Vitányi: Kolmogorov Complexity and its Applications. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 187-254

[LV2]

...

[V]

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