{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,15]],"date-time":"2026-10-15T06:50:16Z","timestamp":1792047016239,"version":"4.4.0"},"reference-count":51,"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":[[2006,1]]},"abstract":"<jats:p>We study queries to spatial databases, where spatial data are modeled as semi-algebraic sets, using the relational calculus with polynomial inequalities as a basic query language. We work with the extension of the relational calculus with terminating transitive closures. The main result is that this language can express the linearization of semialgebraic databases. We also show that the sublanguage with linear inequalities only can express all computable queries on semilinear databases. As a consequence of these results, we obtain a completeness result for topological queries on semialgebraic databases.<\/jats:p>","DOI":"10.1137\/s0097539702410065","type":"journal-article","created":{"date-parts":[[2008,2,12]],"date-time":"2008-02-12T16:51:45Z","timestamp":1202835105000},"page":"1386-1439","source":"Crossref","is-referenced-by-count":6,"title":["Linearization and Completeness Results for Terminating Transitive Closure Queries on Spatial Databases"],"prefix":"10.1137","volume":"35","author":[{"given":"Floris","family":"Geerts","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bart","family":"Kuijpers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jan","family":"Van den Bussche","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","unstructured":", Advances in spatial databases, Proceedings of the Third International Symposium on Large Spatial Databases (SSD \u201993) held at the National University of Singapore, Singapore, June 23\u201325, 1993, Lecture Notes in Computer Science, Vol. 692, Springer\u2010Verlag, 1993, 0\u20130, xiv+52994e:68004"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235813"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-05355-3"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798342484"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1810"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03718-8"},{"key":"R7","unstructured":"H. Brakhage,\n                      Topologische Eigenschaften algebraischer Gebilde \u00fcber einem beliebigen reell\u2010abgeschlossenen Konstantenk\u00f6rper\n                      , Dissertation, Universit\u00e4t Heidelberg, Heidelberg, Germany, 1954."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"A. P. Buchmann, O. G\u00fcnther, T. R. Smith, and Y.\u2010F. Wang, eds.\n                      Design and Implementation of Large Spatial Databases\u2014First Symposium (SSD\u201989\n                      ), Lecture Notes in Comput. Sci. 409, Springer\u2010Verlag, Berlin, New York, 1989.","DOI":"10.1007\/3-540-52208-5"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03427-9"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1625"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"H. D. Ebbinghaus and J. Flum,\n                      Finite Model Theory\n                      , Springer\u2010Verlag, Berlin, 1995.","DOI":"10.1007\/3-540-28788-4"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. J. Egenhofer and J. R. Herring, eds.\n                      Advances in Spatial Databases\u20144th Symposium (SSD\u201995)\n                      , Lecture Notes in Comput. Sci. 951, Springer\u2010Verlag, Berlin, New York, 1995.","DOI":"10.1007\/3-540-60159-7"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"F. Geerts,\n                      Linear approximation of semi\u2010algebraic spatial databases using transitive closure logic, in arbitrary dimension\n                      , in Proceedings of the 8th International Workshop on Databases and Programming Languages, Lecture Notes in Comput. Sci., Springer\u2010Verlag, 2002, pp.","DOI":"10.1007\/3-540-46093-4_11"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-0770-2"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"F. Geerts and B. Kuijpers,\n                      Expressing topological connectivity of spatial databases\n                      , in Research Issues in Structured and Semistructured Database Programming. Proceedings of the 7th International Workshop on Database Programming Languages, Lecture Notes in Comput. Sci. 1949, Springer\u2010Verlag, Berlin, New York, 1999, pp. 224\u2013238.","DOI":"10.1007\/3-540-44543-9_14"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"F. Geerts and B. Kuijpers,\n                      Linear approximation of planar spatial databases using transitive\u2010closure logic\n                      , in Proceedings of the 19th ACM Symposium on Principles of Database Systems, ACM, New York, 2000, pp. 126\u2013135.","DOI":"10.1145\/335168.335215"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.034"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"S. Grumbach and G. Kuper,\n                      Tractable recursion over geometric data\n                      , in Proceedings of the 3rd Conference on Principles and Practice of Constraint Programming, G. Smolka, ed., Lecture Notes in Comput. Sci. 1330, Springer\u2010Verlag, Berlin, New York, 1997, pp. 450\u2013462.","DOI":"10.1007\/BFb0017459"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"S. Grumbach, P. Rigaux, M. Scholl, and L. Segoufin,\n                      DEDALE, a spatial constraint database\n                      , in Proceedings of Database Programming Languages (DBPL \u201997), S. Cluet and R. Hull, eds., Lecture Notes in Comput. Sci. 1369, Springer\u2010Verlag, Berlin, New York, 1998, pp. 38\u201359.","DOI":"10.1007\/3-540-64823-2_4"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"S. Grumbach, P. Rigaux, and L. Segoufin,\n                      The DEDALE system for complex spatial queries\n                      , in Proceedings of the ACM International Conference on Management of Data (SIGMOD \u201998), L. M. Haas and A. Tiwary, eds., ACM, New York, 1998, pp. 213\u2013224.","DOI":"10.1145\/276304.276324"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"S. Grumbach and J. Su,\n                      Towards practical constraint databases\n                      , in Proceedings of the 15th ACM Symposium on Principles of Database Systems (PODS \u201996), ACM, New York, 1996, pp. 28\u201339.","DOI":"10.1145\/237661.237672"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00194-6"},{"key":"R23","volume-title":"Differential topology","author":"Guillemin Victor","year":"1974"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"O. Gunther and H.\u2010J. Schek, eds.\n                      Advances in Spatial Databases\u20142nd Symposium (SSD\u201991)\n                      , Lecture Notes in Comput. Sci. 525, Springer\u2010Verlag, Berlin, New York, 1991.","DOI":"10.1007\/3-540-54414-3"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"R. H. G\u00fcting, ed.\n                      Advances in Spatial Databases\u20146th Symposium (SSD\u201999)\n                      , Lecture Notes in Comput. Sci. 1651, Springer\u2010Verlag, Berlin, New York, 1999.","DOI":"10.1007\/3-540-48482-5"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1007\/BF01403128"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1051"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"Pascal Koiran, Approximating the volume of definable sets, IEEE Comput. Soc. Press, Los Alamitos, CA, 1995, 134\u20131411619085","DOI":"10.1109\/SFCS.1995.492470"},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Stephan Kreutzer, Operational semantics for fixed\u2010point logics on constraint databases, Lecture Notes in Comput. Sci., Vol. 2250, Springer, Berlin, 2001, 470\u20134842003h:68029","DOI":"10.1007\/3-540-45653-8_32"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"S. Kreutzer,\n                      Query languages for constraint databases: First\u2010order logic, fixed\u2010points, and convex hulls\n                      , in Proceedings of the 9th International Conference on Database Theory, J. Van den Bussche and V. Vianu, eds., Lecture Notes in Comput. Sci. 1973, Springer\u2010Verlag, Berlin, New York, 2001, pp. 248\u2013262.","DOI":"10.1007\/3-540-44503-X_17"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"B. Kuijpers, J. Paredaens, M. Smits, and J. Van den Bussche,\n                      Termination properties of spatial datalog\n                      , in Logic in Databases (LID \u201996), D. Pedreschi and C. Zaniolo, eds., Lecture Notes in Comput. Sci. 1154, Springer\u2010Verlag, Berlin, New York, 1996, pp. 101\u2013116.","DOI":"10.1007\/BFb0031737"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.2307\/2695063"},{"key":"R33","doi-asserted-by":"crossref","unstructured":"B. Kuijpers and M. Smits,\n                      On expressing topological connectivity in spatial datalog\n                      , in Proceedings of the 2nd Workshop on Constraint Databases and Applications, V. Gaede, A. Brodsky, O. Gunter, D. Srivastava, V. Vianu, and M. Wallace, eds., Lecture Notes in Comput. Sci. 1191, Springer\u2010Verlag, Berlin, New York, 1997, pp. 116\u2013133.","DOI":"10.1007\/3-540-62501-1_29"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"G. M. Kuper, J. Paredaens, and L. Libkin, eds.\n                      Constraint Databases\n                      , Springer\u2010Verlag, Berlin, New York, 2000.","DOI":"10.1007\/978-3-662-04031-7"},{"key":"R35","volume-title":"Introduction to topological manifolds","author":"Lee John","year":"2000"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-9906-6"},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804120"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009335"},{"key":"R40","unstructured":"E. Rannou,\n                      Personal communication\n                      , 2000."},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80003-3"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"M. Scholl and A. Voisard, eds.\n                      Advances in Spatial Databases\u20145th Symposium (SSD\u201997)\n                      , Lecture Notes in Comput. Sci. 1262, Springer\u2010Verlag, Berlin, New York, 1997.","DOI":"10.1007\/3-540-63238-7"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1525\/9780520348097"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511525919"},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-96-08416-1"},{"key":"R46","unstructured":"L. Vandeurzen,\n                      Logic\u2010Based Query Languages for the Linear Constraint Database Model\n                      , Ph.D. thesis, Limburgs Universitair Centrum (LUC), Diepenbeek, Belgium, 1999."},{"key":"R47","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 Advances in Spatial Databases\u20144th Symposium (SSD \u201995), M. J. Egenhofer and J. R. Herring, eds., Lecture Notes in Comput. Sci. 951, Springer\u2010Verlag, Berlin, New York, 1995, pp. 14\u201328.","DOI":"10.1007\/3-540-60159-7_2"},{"key":"R48","doi-asserted-by":"crossref","unstructured":"L. Vandeurzen, M. Gyssens, and D. Van Gucht,\n                      An expressive language for linear spatial database queries\n                      , in Proceedings of the 17th ACM Symposium on Principles of Database Systems (PODS \u201998), ACM, New York, 1998, pp. 109\u2013118.","DOI":"10.1145\/275487.275500"},{"key":"R49","doi-asserted-by":"publisher","DOI":"10.2307\/2275270"},{"key":"R50","doi-asserted-by":"publisher","DOI":"10.1007\/s000290050052"},{"key":"R51","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8431-1"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539702410065","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:24:12Z","timestamp":1787336652000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539702410065"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":51,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/S0097539702410065"],"URL":"https:\/\/doi.org\/10.1137\/s0097539702410065","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}