{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:53Z","timestamp":1787340233788,"version":"build-2736575974"},"reference-count":42,"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":[[2007,1]]},"abstract":"<jats:p>The research presented in this paper is situated in the framework of constraint databases introduced by Kanellakis, Kuper, and Revesz in their seminal paper of 1990, specifically, the language with real polynomial constraints (FO+poly). For reasons of efficiency, this model is implemented with only linear polynomial constraints, but this limitation to linear polynomial constraints has severe implications on the expressive power of the query language. In particular, when used for modeling spatial data, important queries that involve Euclidean distance are not expressible. The aim of this paper is to identify a class of two\u2010dimensional constraint databases and a query language within the constraint model that go beyond the linear model and allow the expression of queries concerning distance. We seek inspiration in the Euclidean constructions, i.e., constructions by ruler and compass. We first present a programming language that captures exactly the first\u2010order ruler\u2010and\u2010compass constructions that are expressible in a first\u2010order language with real polynomial constraints. If this language is extended with a while operator, we obtain a language that is complete for all ruler\u2010and\u2010compass constructions in the plane. We then transform this language in a natural way into a query language on finite point databases, but this language turns out to have the same expressive power as FO+poly and is therefore too powerful for our purposes. We then consider a safe fragment of this language and use this to construct a query language that allows the expression of Euclidean distance without having the full power of FO+poly.<\/jats:p>","DOI":"10.1137\/s0097539702407199","type":"journal-article","created":{"date-parts":[[2007,3,22]],"date-time":"2007-03-22T18:04:30Z","timestamp":1174586670000},"page":"1570-1599","source":"Crossref","is-referenced-by-count":0,"title":["First\u2010Order Languages Expressing Constructible Spatial Database Queries"],"prefix":"10.1137","volume":"36","author":[{"given":"Bart","family":"Kuijpers","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gabriel","family":"Kuper","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Paredaens","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Luc","family":"Vandeurzen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2007,2,20]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"D. Abel and B. C. Ooi, eds.\n                      Proceedings of the Third International Symposium on Spatial Databases\n                      , Lecture Notes in Comput. Sci. 692, Springer\u2010Verlag, Berlin, 1993.","DOI":"10.1007\/3-540-56869-7"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"F. Afrati, T. Andronikos, and T. Kavalieros,\n                      On the expressiveness of first\u2010order constraint languages\n                      , in Proceedings of the First Workshop on Constraint Databases and Their Applications, Lecture Notes in Comput. Sci. 1034, G. Kuper and M. Wallace, eds., Springer\u2010Verlag, Berlin, 1995, pp. 22\u201339.","DOI":"10.1007\/3-540-60794-3_12"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"F. Afrati, S. Cosmadakis, S. Grumbach, and G. Kuper,\n                      Linear versus polynomial constraints in database query languages\n                      , in Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, Lecture Notes in Comput. Sci. 874, A. Borning, ed., Springer\u2010Verlag, Berlin, 1994, pp. 181\u2013192.","DOI":"10.1007\/3-540-58601-6_100"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235813"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798342484"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"J. Bochnak, M. Coste, and M.\u2010F. Roy,\n                      Real Algebraic Geometry\n                      , Springer\u2010Verlag, Berlin, 1998.","DOI":"10.1007\/978-3-662-03718-8"},{"key":"R7","unstructured":"A. Buchmann, ed.\n                      Proceedings of the First International Symposium on Spatial Databases\n                      , Lecture Notes in Comput. Sci. 409, Springer\u2010Verlag, Berlin, 1989."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"B. F. Caviness and J. R. Johnson, eds.\n                      Quantifier Elimination and Cylindrical Algebraic Decomposition\n                      , Springer\u2010Verlag, Wien, New York, 1998.","DOI":"10.1007\/978-3-7091-9459-1"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"G. E. Collins,\n                      Quantifier elimination for real closed fields by cylindrical algebraic decomposition\n                      , in Automata Theory and Formal Languages, Lecture Notes in Comput. Sci. 33, H. Brakhage, ed., Springer\u2010Verlag, Berlin, 1975, pp. 134\u2013183.","DOI":"10.1007\/3-540-07407-4_17"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"M. J. Egenhofer and J. R. Herring, eds.\n                      Proceedings of the Fourth International Symposium on Spatial Databases\n                      , Lecture Notes in Comput. Sci. 951, Springer\u2010Verlag, Berlin, 1995.","DOI":"10.1007\/3-540-60159-7"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"E. Engeler,\n                      Remarks on the theory of geometrical constructions\n                      , in The Syntax and Semantics of Infinitary Languages, Lecture Notes in Math. 72, A. Dold and B. Echraun, eds., Springer\u2010Verlag, Berlin, 1968, pp. 64\u201376.","DOI":"10.1007\/BFb0079682"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"E. Engeler,\n                      Foundations of Mathematics\n                      , Springer\u2010Verlag, Berlin, 1992.","DOI":"10.1007\/978-3-642-78052-3"},{"key":"R13","unstructured":"H. Eves,\n                      College Geometry\n                      , Jones and Barlett, Boston, 1995."},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(96)00099-0"},{"key":"R15","unstructured":"S. Grumbach,\n                      Implementing linear constraint databases\n                      , in Proceedings of the Second Workshop on Constraint Databases and Applications, Lecture Notes in Comput. Sci. 1191, V. Gaede, A. Brodsky, O. G\u00fcnther, D. Srivastava, V. Vianu, and M. Wallace, eds., Springer\u2010Verlag, Berlin, 1997, pp. 105\u2013115."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"S. Grumbach, P. Rigaux, M. Scholl, and L. Segoufin,\n                      DEDALE, a spatial constraint database\n                      , in Proceedings of the Sixth International Workshop on Database Programming Languages, Lecture Notes in Comput. Sci. 1369, Springer\u2010Verlag, Berlin, 1998, pp. 124\u2013135.","DOI":"10.1007\/3-540-64823-2_4"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"S. Grumbach and J. Su,\n                      Towards practical constraint databases\n                      , in Proceedings of the 15th ACM SIGACT\u2010SIGMOD\u2010SIGART Symposium on Principles of Database Systems, ACM Press, New York, 1996, pp. 28\u201339.","DOI":"10.1145\/237661.237672"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1524"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00194-6"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"S. Grumbach, J. Su, and C. Tollu,\n                      Linear constraint query languages: Expressive power and complexity\n                      , in Proceedings of the Logic and Computational Complexity Workshop, Lecture Notes in Comput. Sci. 960, D. Leivant, ed., Springer\u2010Verlag, Berlin, 1994, pp. 426\u2013446.","DOI":"10.1007\/3-540-60178-3_96"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"O. G\u00fcnther and H.\u2010J. Schek, eds.\n                      Proceedings of the Second International Symposium on Spatial Databases\n                      , Lecture Notes in Comput. Sci. 525, Springer\u2010Verlag, Berlin, 1991.","DOI":"10.1007\/3-540-54414-3"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"R. H. G\u00fcting, ed.\n                      Advances in Spatial Databases\u20146th International Symposium (SSD \u201999)\n                      , Lecture Notes in Comput. Sci. 1651, Springer\u2010Verlag, Berlin, 1999.","DOI":"10.1007\/3-540-48482-5"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"M. Gyssens, L. Vandeurzen, and D. Van Gucht,\n                      An expressive language for linear spatial database queries\n                      , in Proceedings of the 17th ACM SIGACT\u2010SIGMOD\u2010SIGART Symposium on Principles of Database Systems, ACM Press, New York, 1998, pp. 109\u2013118.","DOI":"10.1145\/275487.275500"},{"key":"R24","unstructured":"T. Heath,\n                      The Thirteen Books of Euclid\u2019s Elements\n                      , Dover, New York, 1956."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"J. Heintz and B. Kuijpers,\n                      Constraint databases, data structures and efficient query evaluation\n                      , in Proceedings of the First International Symposium on Applications of Constraint Databases (CDB\u201904), Lecture Notes in Comput. Sci. 3074, B. Kuijpers and P. Revesz, eds., Springer\u2010Verlag, Berlin, 2004, pp. 1\u201324.","DOI":"10.1007\/978-3-540-25954-1_1"},{"key":"R26","unstructured":"D. Hilbert,\n                      Grundlagen der Geometrie\n                      , Teubner, Leipzig, 1899."},{"key":"R27","unstructured":"J. E. Hopcroft and J. D Ullman,\n                      Introduction to Automata Theory, Languages, and Computation\n                      , Addison\u2013Wesley, Reading, MA, 1979."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"P. C. Kanellakis, G. M. Kuper, and P. Z. Revesz,\n                      Constraint query languages\n                      , in Proceedings of the Ninth ACM SIGACT\u2010SIGMOD\u2010SIGART Symposium on Principles of Database Systems, Nashville, TN, 1990, pp. 299\u2013213.","DOI":"10.1145\/298514.298582"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1051"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"G. Kuper, L. Libkin, and J. Paredaens, eds.\n                      Constraint Databases\n                      , Springer\u2010Verlag, Berlin, 2000.","DOI":"10.1007\/978-3-662-04031-7"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"J. L. Lassez,\n                      Querying constraints\n                      , in Proceedings of the Ninth ACM SIGACT\u2010SIGMOD\u2010SIGART Symposium on Principles of Database Systems, ACM Press, New York, 1990, pp. 288\u2013298.","DOI":"10.1145\/298514.298581"},{"key":"R32","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 Proceedings of the 13th ACM SIGACT\u2010SIGMOD\u2010SIGART Symposium on Principles of Database Systems, ACM Press, New York, 1994, pp. 279\u2013288.","DOI":"10.1145\/182591.182640"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"M. F. Preparata and M. I. Shamos,\n                      Computational Geometry\n                      , Springer\u2010Verlag, New York, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80003-3"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.2307\/2266510"},{"key":"R36","unstructured":"M.\u2010F. Roy, S. Basu, and R. Pollack,\n                      Algorithms in Real Algebraic Geometry\n                      , Algorithms Comput. Math. 10, Springer\u2010Verlag, Berlin, 2003."},{"key":"R37","doi-asserted-by":"crossref","unstructured":"M. Scholl and A. Voisard, eds.\n                      Proceedings of the Fifth International Symposium on Spatial Databases\n                      , Lecture Notes in Comput. Sci. 1262, Springer\u2010Verlag, Berlin, 1997.","DOI":"10.1007\/3-540-63238-7"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"A. Tarski,\n                      A Decision Method for Elementary Algebra and Geometry\n                      , University of California Press, Berkeley, CA, 1951.","DOI":"10.1525\/9780520348097"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"L. van den Dries,\n                      Tame Topology and O\u2010minimal Structures\n                      , Cambridge University Press, Cambridge, UK, 1998.","DOI":"10.1017\/CBO9780511525919"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"L. Vandeurzen, M. Gyssens, and D. Van Gucht,\n                      On the desirability and limitations of linear spatial query languages\n                      , in Proceedings of the Fourth International Symposium on Spatial Databases, Lecture Notes in Comput. Sci. 951, M. J. Egenhofer and J. R. Herring, eds., Springer\u2010Verlag, Berlin, 1995, pp. 14\u201328.","DOI":"10.1007\/3-540-60159-7_2"},{"key":"R41","doi-asserted-by":"crossref","unstructured":"L. Vandeurzen, M. Gyssens, and D. Van Gucht,\n                      On query languages for linear queries definable with polynomial constraints\n                      , in Proceedings of the Second International Conference on Principles and Practice of Constraint Programming, Lecture Notes in Comput. Sci. 1118, E. C. Freuder, ed., Springer\u2010Verlag, Berlin, 1996, pp. 468\u2013481.","DOI":"10.1007\/3-540-61551-2_94"},{"key":"R42","first-page":"269","volume":"28","author":"Ziegler M.","year":"1982","journal-title":"Enseign. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0013-8584","issn-type":"print"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539702407199","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:26:18Z","timestamp":1787336778000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539702407199"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,1]]},"references-count":42,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2007,1]]}},"alternative-id":["10.1137\/S0097539702407199"],"URL":"https:\/\/doi.org\/10.1137\/s0097539702407199","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,1]]}}}