{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T16:46:13Z","timestamp":1749573973654},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540414568"},{"type":"electronic","value":"9783540445036"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44503-x_1","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T04:25:32Z","timestamp":1186892732000},"page":"1-21","source":"Crossref","is-referenced-by-count":3,"title":["Expressive Power of SQL"],"prefix":"10.1007","author":[{"given":"Leonid","family":"Libkin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,10,12]]},"reference":[{"key":"1_CR1","unstructured":"S. Abiteboul, R. Hull and V. Vianu. Foundations of Databases, Addison Wesley, 1995."},{"key":"1_CR2","doi-asserted-by":"crossref","unstructured":"A. V. Aho and J. D. Ullman. Universality of data retrieval languages. In POPL\u201979, pages 110\u2013120.","DOI":"10.1145\/567752.567763"},{"key":"1_CR3","first-page":"274","volume":"41","author":"D.M. Barrington","year":"1990","unstructured":"D.M. Barrington, N. Immerman, H. Straubing. On uniformity within NC 1. JCSS, 41:274\u2013306, 1990.","journal-title":"JCSS"},{"key":"1_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(95)00024-Q","volume":"149","author":"P. Buneman","year":"1995","unstructured":"P. Buneman, S. Naqvi, V. Tannen, L. Wong. Principles of programming with complex objects and collection types. TCS, 149 (1995), 3\u201348.","journal-title":"TCS"},{"key":"1_CR5","unstructured":"J. Celko. SQL for Smarties: Advanced SQL Programming. Morgan Kaufmann, 2000."},{"key":"1_CR6","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(93)90221-E","volume":"116","author":"M. Consens","year":"1993","unstructured":"M. Consens and A. Mendelzon. Low complexity aggregation in GraphLog and Datalog, TCS 116 (1993), 95\u2013116. Extended abstract in ICDT\u201990.","journal-title":"TCS"},{"key":"1_CR7","unstructured":"C. J. Date and H. Darwen. A Guide to the SQL Standard. Addison Wesley, 1997."},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/S0304-3975(99)00223-6","volume":"239","author":"G. Dong","year":"2000","unstructured":"G. Dong, L. Libkin and L. Wong. Local properties of query languages. TCS 239 (2000), 277\u2013308. Extended abstract in ICDT\u201997.","journal-title":"TCS"},{"key":"1_CR9","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1145\/343369.343386","volume":"1","author":"M. Grohe","year":"2000","unstructured":"M. Grohe and T. Schwentick. Locality of order-invariant first-order formulas. ACM TOCL, 1 (2000), 112\u2013130.","journal-title":"ACM TOCL"},{"key":"1_CR10","first-page":"400","volume":"54","author":"K. Etessami","year":"1997","unstructured":"K. Etessami. Counting quantifiers, successor relations, and logarithmic space, JCSS, 54 (1997), 400\u2013411.","journal-title":"JCSS"},{"key":"1_CR11","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/inco.1995.1100","volume":"120","author":"R. Fagin","year":"1995","unstructured":"R. Fagin, L. Stockmeyer and M. Vardi, On monadic NP vs monadic co-NP, Information and Computation, 120 (1995), 78\u201392.","journal-title":"Information and Computation"},{"key":"1_CR12","unstructured":"S. Finkelstein, N. Mattos, I.S. Mumick, and H. Pirahesh. Expressing recursive queries in SQL. ANSI Document X3H2-96-075r1, 1996."},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"H. Gaifman. On local and non-local properties, Proceedings of the Herbrand Symposium, Logic Colloquium\u2019 81, North Holland, 1982.","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"1_CR14","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1006\/inco.1997.2675","volume":"140","author":"E. Gr\u00e4del","year":"1998","unstructured":"E. Gr\u00e4del and Y. Gurevich. Metafinite model theory. Information and Computation 140 (1998), 26\u201381.","journal-title":"Information and Computation"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"W. Hanf. Model-theoretic methods in the study of elementary logic. In J.W. Addison et al, eds, The Theory of Models, North Holland, 1965, pages 132\u2013145.","DOI":"10.1016\/B978-0-7204-2233-7.50020-4"},{"key":"1_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1996.0070","volume":"129","author":"L. Hella","year":"1996","unstructured":"L. Hella. Logical hierarchies in PTIME. Information and Computation, 129 (1996), 1\u201319.","journal-title":"Information and Computation"},{"key":"1_CR17","doi-asserted-by":"publisher","first-page":"1751","DOI":"10.2307\/2586810","volume":"64","author":"L. Hella","year":"1999","unstructured":"L. Hella, L. Libkin and J. Nurmonen. Notions of locality and their logical characterizations over finite models. J. Symb. Logic, 64 (1999), 1751\u20131773.","journal-title":"J. Symb. Logic"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"L. Hella, L. Libkin, J. Nurmonen and L. Wong. Logics with aggregate operators. In LICS\u201999, pages 35\u201344.","DOI":"10.1109\/LICS.1999.782583"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive Complexity. Springer Verlag, 1998.","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"1_CR20","doi-asserted-by":"publisher","first-page":"699","DOI":"10.1145\/322326.322332","volume":"29","author":"A. Klug","year":"1982","unstructured":"A. Klug. Equivalence of relational algebra and relational calculus query languages having aggregate functions. J. ACM 29 (1982), 699\u2013717.","journal-title":"J. ACM"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"L. Libkin. On the forms of locality over finite models. In LICS\u201997, pages 204\u2013215.","DOI":"10.1109\/LICS.1997.614948"},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/343369.343376","volume":"1","author":"L. Libkin","year":"2000","unstructured":"L. Libkin. Logics with counting and local properties. ACM TOCL, 1 (2000), 33\u201359. Extended abstract in LICS\u201998.","journal-title":"ACM TOCL"},{"key":"1_CR23","first-page":"241","volume":"55","author":"L. Libkin","year":"1997","unstructured":"L. Libkin, L. Wong. Query languages for bags and aggregate functions. JCSS 55 (1997), 241\u2013272. Extended abstract in PODS\u201994.","journal-title":"JCSS"},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"L. Libkin and L. Wong. On the power of aggregation in relational query languages. In DBPL\u201997, pages 260\u2013280.","DOI":"10.1007\/3-540-64823-2_15"},{"key":"1_CR25","unstructured":"P. O\u2019Neil. Database: Principles, Programming, Performance. Morgan Kaufmann, 1994."},{"key":"1_CR26","first-page":"278","volume":"36","author":"I. Parberry","year":"1988","unstructured":"I. Parberry and G. Schnitger. Parallel computation and threshold functions. JCSS 36 (1988), 278\u2013302.","journal-title":"JCSS"},{"key":"1_CR27","first-page":"24","volume":"55","author":"A. Razborov","year":"1997","unstructured":"A. Razborov and S. Rudich. Natural proofs. JCSS 55 (1997), 24\u201335.","journal-title":"JCSS"},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1017\/S0960129500001560","volume":"2","author":"P. Wadler","year":"1992","unstructured":"P. Wadler. Comprehending monads. Mathematical Structures in Computer Science 2 (1992), 461\u2013493.","journal-title":"Mathematical Structures in Computer Science"}],"container-title":["Lecture Notes in Computer Science","Database Theory \u2014 ICDT 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44503-X_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T23:39:54Z","timestamp":1556753994000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44503-X_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540414568","9783540445036"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-44503-x_1","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}