{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T07:58:50Z","timestamp":1787385530171,"version":"build-2736575974"},"reference-count":22,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We investigate properties of finite relational structures over the reals expressed by first-order sentences whose predicates are the relations of the structure plus arbitrary polynomial inequalities, and whose quantifiers can range over the whole set of reals. In constraint programming terminology, this corresponds to Boolean real polynomial constraint queries on finite structures. The fact that quantifiers range over all reals seems crucial; however, we observe that each sentence in the first-order theory of the reals can be evaluated by letting each quantifier range over only a finite set of real numbers without changing its truth value. Inspired by this observation, we then show that when all polynomials used are linear, each query can be expressed uniformly on all finite structures by a sentence of which the quantifiers range only over the finite domain of the structure. In other words, linear constraint programming on finite structures can be reduced to ordinary query evaluation as usual in finite model theory and databases. Moreover, if only \"generic\" queries are taken into consideration, we show that this can be reduced even further by proving that such queries can be expressed by sentences using as polynomial inequalities only those of the simple form x &lt; y.<\/jats:p>","DOI":"10.1137\/s009753979629766","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1747-1763","source":"Crossref","is-referenced-by-count":25,"title":["First-Order Queries on Finite Structures Over the Reals"],"prefix":"10.1137","volume":"27","author":[{"given":"Jan","family":"Paredaens","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Van den Bussche","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dirk","family":"Van Gucht","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"S. Abiteboul, R. Hull, and V. Vianu,\n                      Foundations of Databases\n                      , Addison\u2010Wesley, Reading, MA, 1994."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Alfred Aho, Jeffrey Ullman, Universality of data retrieval languages, ACM, New York, 1979, 110\u201312081j:68027","DOI":"10.1145\/567752.567763"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(88)90049-5"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/0213054"},{"key":"R5","first-page":"308","volume":"286","author":"Alamazyan A.","year":"1986","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"R6","unstructured":"O. Belegradek, A. Stolboushkin, and M. Taitslin,\n                      On Order\u2010Generic Queries\n                      , Tech. Report 96\u201001, DIMACS, Rutgers University, New Brunswick, NJ, 1996."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Benedikt, G. Dong, L. Libkin, and L. Wong,\n                      Relational expressive power of constraint query languages\n                      , in Proc. 15th ACM Symposium on Principles of Database Systems, ACM Press, New York, 1996, pp. 5\u201316.","DOI":"10.1145\/237661.237667"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Michael Benedikt, Leonid Libkin, On the structure of queries in constraint query languages, IEEE Comput. Soc. Press, Los Alamitos, CA, 1996, 25\u2013341461818","DOI":"10.1109\/LICS.1996.561300"},{"key":"R9","volume-title":"Constraint logic programming","author":"Benhamou Fr\u00e9d\u00e9ric","year":"1993"},{"key":"R10","unstructured":"J. Bochnak, M. Coste, and M.\u2010F. Roy,\n                      G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle\n                      , Springer\u2010Verlag, Berlin, 1987."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90032-X"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"George Collins, Quantifier elimination for real closed fields by cylindrical algebraic decomposition, Springer, Berlin, 1975, 0\u20130, 134\u2013183. Lecture Notes in Comput. Sci., Vol. 3353:7771","DOI":"10.1007\/3-540-07407-4_17"},{"key":"R13","unstructured":"H. Enderton,\n                      A Mathematical Introduction to Logic\n                      , Academic Press, New York, 1972."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"St\u00e9phane Grumbach, Jianwen Su, Christophe Tollu, Linear constraint query languages: expressive power and complexity, Lecture Notes in Comput. Sci., Vol. 960, Springer, Berlin, 1995, 426\u20134461449673","DOI":"10.1007\/3-540-60178-3_96"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1007\/BF01213204"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1051"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"G. Kuper,\n                      On the expressive power of the relational calculus with arithmetic constraints\n                      , in ICDT\u201990, Lecture Notes in Computer Science 470, S. Abiteboul and P. Kanellakis, eds., Springer\u2010Verlag, New York, 1990, pp. 202\u2013214.","DOI":"10.1007\/3-540-53507-1_78"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00140-8"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J. Paredaens, J. Van den Bussche, and D. Van Gucht,\n                      Towards a theory of spatial database queries\n                      , in Proc. 13th ACM Symposium on Principles of Database Systems, ACM Press, New York, 1994, pp. 279\u2013288.","DOI":"10.1145\/182591.182640"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"J. Paredaens, J. Van den Bussche, and D. Van Gucht,\n                      First\u2010order queries on finite structures over the reals (extended abstract)\n                      , in Proc. 10th IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1995, pp. 79\u201387.","DOI":"10.1109\/LICS.1995.523246"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"A. Stolboushkin and M. Taitslin,\n                      Linear vs. order constraints over rational databases\n                      , in Proc. 15th ACM Symposium on Principles of Database Systems, ACM Press, New York, 1996, pp. 17\u201327.","DOI":"10.1145\/237661.237669"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1017\/S0022481200028899"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S009753979629766","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:14:21Z","timestamp":1787336061000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S009753979629766"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":22,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S009753979629766"],"URL":"https:\/\/doi.org\/10.1137\/s009753979629766","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}