{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T08:20:31Z","timestamp":1775809231670,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540602996","type":"print"},{"value":"9783540447887","type":"electronic"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60299-2_8","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T18:15:39Z","timestamp":1330280139000},"page":"121-136","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["First-order definability over constraint databases"],"prefix":"10.1007","author":[{"given":"St\u00e9phane","family":"Grumbach","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianwen","family":"Su","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"F. Afrati, S. Cosmadakis, S. Grumbach, and G. Kuper. Expressiveness of linear vs. polynomial constraints in database query languages. In Second Workshop on the Principles and Practice of Constraint Programming, 1994.","DOI":"10.1007\/3-540-58601-6_100"},{"key":"8_CR2","unstructured":"S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1994."},{"issue":"2","key":"8_CR3","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A. Chandra","year":"1980","unstructured":"A. Chandra and D. Harel. Computable Queries for Relational Data Bases. Journal of Computer and System Sciences, 21(2):156\u2013178, Oct. 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"J. Chomicki and G. Kuper. Measuring infinite relations. In Proc. 14th ACM Symp. on Principles of Database Systems, San Jose, May 1995.","DOI":"10.1145\/212433.212455"},{"issue":"6","key":"8_CR5","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"E.F. Codd","year":"1970","unstructured":"E.F. Codd. A relational model of data for large shared data banks. Communications of ACM, 13:6:377\u2013387, 1970.","journal-title":"Communications of ACM"},{"issue":"2","key":"8_CR6","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1137\/0213028","volume":"13","author":"A. K. Chandra","year":"1984","unstructured":"A. K. Chandra, L. Stockmeyer, and U. Vishkin. Constant depth reducibility. SIAM J. on Computing, 13(2):423\u2013439, May 1984.","journal-title":"SIAM J. on Computing"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"A. Ehrenfeucht. An application of games to the completeness problem for formalized theories. Fund. Math, 49, 1961.","DOI":"10.4064\/fm-49-2-129-141"},{"key":"8_CR8","unstructured":"H. Enderton. A Mathematical Introduction to Logic. Academic Press, 1972."},{"key":"8_CR9","first-page":"43","volume":"7","author":"R. Fagin","year":"1974","unstructured":"R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. Complexity of Computations, SIAM-AMS Proceedings 7, pages 43\u201373, 1974.","journal-title":"Complexity of Computations, SIAM-AMS Proceedings"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(93)90218-I","volume":"116","author":"R. Fagin","year":"1993","unstructured":"R. Fagin. Finite model theory \u2014 a personal perspective. Theoretical Computer Science, 116:3\u201331, 1993.","journal-title":"Theoretical Computer Science"},{"key":"8_CR11","first-page":"1","volume":"I","author":"R. Fra\u00efss\u00e9","year":"1954","unstructured":"R. Fra\u00efss\u00e9. Sur les classifications des syst\u00e8mes de relations. Publ. Sci. Univ Alger, I:1, 1954.","journal-title":"Publ. Sci. Univ Alger"},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"M. Furst, J. B. Saxe, and M. Sipser. Parity, circuits, and the polynomialtime hierarchy. Mathematical System Theory, 17:13\u201327, 1984.","journal-title":"Mathematical System Theory"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"H. Gaifman. On local and non local properties. In J. Stern, editor, Proc. Herbrand Symposium Logic Colloquium, pages 105\u2013135. North Holland, 1981.","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"S. Grumbach and J. Su. Finitely representable databases. In 13th ACM Symp. on Principles of Database Systems, pages 289\u2013300, Minneapolis, May 1994.","DOI":"10.1145\/182591.182654"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"S. Grumbach and J. Su. Dense order constraint databases. In Proc. 14th ACM Symp. on Principles of Database Systems, San Jose, May 1995.","DOI":"10.1145\/212433.212453"},{"key":"8_CR16","volume-title":"Logic and Computational Complexity Workshop","author":"S. Grumbach","year":"1994","unstructured":"S. Grumbach, J. Su, and C. Tollu. Linear constraint databases. In D. Leivant, editor, Logic and Computational Complexity Workshop, Indianapolis, 1994. Springer Verlag. to appear in LNCS."},{"key":"8_CR17","unstructured":"Y. Gurevich. Current Trends in Theoretical Computer Science, E. Borger Ed., chapter Logic and the Challenge of Computer Science, pages 1\u201357. Computer Science Press, 1988."},{"issue":"4","key":"8_CR18","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman. Languages that capture complexity classes. SIAM J. of Computing, 16(4):760\u2013778, Aug 1987.","journal-title":"SIAM J. of Computing"},{"key":"8_CR19","doi-asserted-by":"crossref","unstructured":"P. Kanellakis and D. Goldin. Constraint programming and database query languages. In Manuscript, 1994.","DOI":"10.1007\/3-540-57887-0_92"},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"P. Kanellakis, G Kuper, and P. Revesz. Constraint query languages. In Proc. 9th ACM Symp. on Principles of Database Systems, pages 299\u2013313, Nashville, 1990.","DOI":"10.1145\/298514.298582"},{"key":"8_CR21","unstructured":"G.M. Kuper. Aggregation in constraint databases. In Proc. First Workshop on Principles and Practice of Constraint Programming, 1993."},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"J. Paredaens, J. Van den Bussche, and D. Van Gucht. Towards a theory of spatial database queries. In Proc. 13th ACM Symp. on Principles of Database Systems, pages 279\u2013288, 1994.","DOI":"10.1145\/182591.182640"},{"key":"8_CR23","unstructured":"J. Paredaens, J. Van den Bussche, and D. Van Gucht. First-order queries on finite structures over the reals. In Proc. IEEE Symposium on Logic In Computer Science, 1995."},{"issue":"1","key":"8_CR24","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0304-3975(93)90222-F","volume":"116","author":"P. Revesz","year":"1993","unstructured":"P. Revesz. A closed form for datalog queries with integer (gap)-order constraints. Theoretical Computer Science, 116(1):117\u2013149, 1993.","journal-title":"Theoretical Computer Science"},{"key":"8_CR25","doi-asserted-by":"crossref","unstructured":"P. Revesz. Datalog queries of set constraint databases. In Proc. Int. Conf. on Database Theory, 1995.","DOI":"10.1007\/3-540-58907-4_32"},{"key":"8_CR26","doi-asserted-by":"crossref","first-page":"98","DOI":"10.2307\/2266510","volume":"14","author":"J. Robinson","year":"1949","unstructured":"J. Robinson. Decidability and decision problems in arithmetic. Journal of Symbolic Logic, 14:98\u2013114, 1949.","journal-title":"Journal of Symbolic Logic"},{"key":"8_CR27","doi-asserted-by":"crossref","DOI":"10.1525\/9780520348097","volume-title":"A Decision method for elementary algebra and geometry","author":"A. Tarski","year":"1951","unstructured":"A. Tarski. A Decision method for elementary algebra and geometry. Univ. of California Press, Berkeley, California, 1951."},{"key":"8_CR28","first-page":"343","volume-title":"Computational Geometry","author":"F.F. Yao","year":"1990","unstructured":"F.F. Yao. Handbook of Theorical Computer Science, volume A, chapter 7 Computational Geometry, pages 343\u2013389. J. Van Leeuwen, North Holland, 1990."}],"container-title":["Lecture Notes in Computer Science","Principles and Practice of Constraint Programming \u2014 CP '95"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60299-2_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:00:04Z","timestamp":1742598004000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60299-2_8"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602996","9783540447887"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-60299-2_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}