{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T22:19:56Z","timestamp":1794349196991,"version":"4.9.0"},"publisher-location":"Dordrecht","reference-count":47,"publisher":"Springer Netherlands","isbn-type":[{"value":"9781402055867","type":"print"},{"value":"9781402055874","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-1-4020-5587-4_13","type":"book-chapter","created":{"date-parts":[[2007,9,1]],"date-time":"2007-09-01T05:19:57Z","timestamp":1188623997000},"page":"799-856","source":"Crossref","is-referenced-by-count":2,"title":["Real Algebraic Geometry and Constraint Databases"],"prefix":"10.1007","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"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/3-540-58601-6_100","volume-title":"Proceedings of the 2nd Workshop on Principles and Practice of Constraint Programming","author":"F. Afrati","year":"1994","unstructured":"Afrati, F., Cosmadakis, S., Grumbach, S., and Kuper, G. (1994). Linear versus polynomial constraints in database query languages. In Borning, A., editor, Proceedings of the 2nd Workshop on Principles and Practice of Constraint Programming, volume 874 of Lecture Notes in Computer Science, pages 181\u2013192, Berlin. Springer-Verlag."},{"key":"13_CR2","unstructured":"Andradas, C., Br\u00f6cker, L., and Ruiz, J. M. (1996). Constructible sets in real geometry, volume 33 of Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer-Verlag."},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Basu, S., Pollack, R., and Roy, M.-F. (2003a). Algorithms in real algebraic geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag.","DOI":"10.1007\/978-3-662-05355-3"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Basu, S., Pollack, R., and Roy, M.-F. (2003b). Algorithms in Real Algebraic Geometry, volume 10 of Algorithms and Computation in Mathematics. Springer-Verlag.","DOI":"10.1007\/978-3-662-05355-3"},{"key":"13_CR5","unstructured":"Belegradek, O. V., Stolboushkin, A. P., and Taitslin, M. A. (1996). On order-generic queries. Technical Report 96-01, DIMACS."},{"key":"13_CR6","unstructured":"Benedetti, R. and Risler, J.-J. (1990). Real algebraic and semi-algebraic sets. Actualit\u00e9s Math\u00e9matiques. [Current Mathematical Topics]. Hermann."},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Dong, G., Libkin, L., and Wong, L. (1996). Relational expressive power of constraint query languages. In Proceedings of the 15th ACM Symposium on Principles of Database Systems, pages 5\u201316.","DOI":"10.1145\/237661.237667"},{"issue":"1","key":"13_CR8","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/S0022-0000(02)00034-X","volume":"66","author":"M. Benedikt","year":"2003","unstructured":"Benedikt, M., Grohe, M., Libkin, L., and Segoufin, L. (2003). Reachability and connectivity queries in constraint databases. J. Comput. System Sci., 66(1):169\u2013206.","journal-title":"J. Comput. System Sci."},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Benedikt, M. and Keisler, H. J. (2000). Definability over linear constraints. In Clote, P. and Schwichtenberg, H., editors, Proceedings of Computer Science Logic, 14th Annual Conference of the EACSL, volume 1862 of Lecture Notes in Computer Science, pages 217\u2013231. Springer-Verlag.","DOI":"10.1007\/3-540-44622-2_14"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Kuijpers, B., L\u00f6ding, C, Van den Bussche, J., and Wilke, T. (2006). A characterization of first-order topological properties of planar spatial data. Journal of the ACM.","DOI":"10.1145\/1131342.1131346"},{"key":"13_CR11","doi-asserted-by":"crossref","unstructured":"Benedikt, M. and Libkin, L. (1996). On the structure of queries in constraint query languages. In 11th Annual IEEE Symposium on Logic in Computer Science, pages 25\u201334.","DOI":"10.1109\/LICS.1996.561300"},{"issue":"5","key":"13_CR12","doi-asserted-by":"publisher","first-page":"1652","DOI":"10.1137\/S0097539798342484","volume":"29","author":"M. Benedikt","year":"2000","unstructured":"Benedikt, M. and Libkin, L. (2000). Safe constraint queries. SIAM J. Comput., 29(5):1652\u20131682.","journal-title":"SIAM J. Comput."},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Benedikt, M.A. and Libkin, L. (1997). Languages for relational databases over interpreted structures. In Proceedings of the 16th ACM Symposium on Principles of Database Systems, pages 87\u201398.","DOI":"10.1145\/263661.263672"},{"key":"13_CR14","unstructured":"Bochnak, J., Coste, M., and Roy, M.-F. (1987). G\u00e9om\u00e9trie alg\u00e9brique r\u00e9elle. Springer-Verlag."},{"key":"13_CR15","unstructured":"Bochnak, J., Coste, M., and Roy, M.-F. (1998). Real algebraic geometry, volume 36 of Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer-Verlag."},{"key":"13_CR16","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-7091-9459-1","volume-title":"Quantifier Elimination and Cylindrical Algebraic Decomposition","author":"B.F. Caviness","year":"1998","unstructured":"Caviness, B.F. and Johnson, J.R. (1998). Quantifier Elimination and Cylindrical Algebraic Decomposition. New York: Springer-Verlag."},{"issue":"6","key":"13_CR17","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"E. Codd","year":"1970","unstructured":"Codd, E. (1970). A relational model for large shared databanks. Communications of the ACM, 13(6):377\u2013387.","journal-title":"Communications of the ACM"},{"key":"13_CR18","first-page":"134","volume-title":"Automata Theory and Formal Languages","author":"G.E. Collins","year":"1975","unstructured":"Collins, G.E. (1975). Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Brakhage, H., editor, Automata Theory and Formal Languages, volume 33 of Lecture Notes in Computer Science, pages 134\u2013183, Berlin. Springer-Verlag."},{"key":"13_CR19","volume-title":"An Introduction to O-minimal Geometry","author":"M Coste","year":"1998","unstructured":"Coste, M (2000a). An Introduction to O-minimal Geometry. Istituti Editoriali e Poligrafici Internazionali, Pisa."},{"key":"13_CR20","volume-title":"An Introduction to Semialgebraic Geometry","author":"M Coste","year":"1998","unstructured":"Coste, M (2000b). An Introduction to Semialgebraic Geometry. Istituti Editoriali e Poligrafici Internazionali, Pisa."},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"Ebbinghaus, H.-D. and Flum, J. (1995). Finite model theory. Perspectives in Mathematical Logic. Springer-Verlag.","DOI":"10.1007\/978-3-662-03182-7"},{"key":"13_CR22","unstructured":"Ebbinghaus, H.-D., Flum, J., and Thomas, W. (1984). Mathematical Logic. Undergraduate Texts in Mathematics. Springer-Verlag."},{"issue":"4","key":"13_CR23","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1007\/s00454-003-0770-2","volume":"30","author":"F. Geerts","year":"2003","unstructured":"Geerts, F. (2003). Expressing the box cone radius in the relational calculus with real polynomial constraints. Discrete Comput. Geom., 30(4):607\u2013622.","journal-title":"Discrete Comput. Geom."},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Geerts, F. and Kuijpers, B. (2000). Linear approximation of planar spatial databases using transitive-closure logic. In Proceedings of the 19th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, pages 126\u2013135.","DOI":"10.1145\/335168.335215"},{"issue":"1","key":"13_CR25","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.tcs.2004.10.034","volume":"336","author":"F. Geerts","year":"2005","unstructured":"Geerts, F. and Kuijpers, B. (2005). On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databases. Theoretical Computer Science, 336(1):125\u2013151. Database Theory\u2013Special issue with selected papers of ICDT\u201903.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"13_CR26","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1006\/jcom.2000.0571","volume":"17","author":"M. Giusti","year":"2001","unstructured":"Giusti, M., Lecerf, G., and Salvy, B. (2001). A Gr\u00f6bner free alternative for polynomial system solving. Journal of Complexity, 17(1):154\u2013211.","journal-title":"Journal of Complexity"},{"issue":"3","key":"13_CR27","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1145\/507382.507384","volume":"3","author":"M. Grohe","year":"2002","unstructured":"Grohe, M. and Segoufin, L. (2002). On first-order topological queries. ACM Transactions on Computational Logic, 3(3):336\u2013358.","journal-title":"ACM Transactions on Computational Logic"},{"key":"13_CR28","doi-asserted-by":"crossref","unstructured":"Grumbach, S. and Su, J. (1995). First-order definability over constraint databases. In Proceedings of 1st Conference on Principles and Practice of Constraint Programming, volume 976 of Lecture Notes in Computer Science. Springer-Verlag.","DOI":"10.1007\/3-540-60299-2_8"},{"key":"13_CR29","doi-asserted-by":"crossref","unstructured":"Grumbach, S., Su, J., and Tollu, C. (1995). Linear constraint query languages: expressive power and complexity. In Leivant, D., editor, Logic and Computational Complexity, volume 960 of Lecture Notes in Computer Science, pages 426\u2013446. Springer-Verlag.","DOI":"10.1007\/3-540-60178-3_96"},{"issue":"3","key":"13_CR30","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1006\/jcss.1999.1630","volume":"58","author":"M. Gyssens","year":"1999","unstructured":"Gyssens, M., Van den Bussche, J., and Van Gucht, D. (1999). Complete geometric query languages. J. Comput. System Sci., 58(3):483\u2013511.","journal-title":"J. Comput. System Sci."},{"key":"13_CR31","first-page":"1","volume":"6","author":"J. Heintz","year":"1993","unstructured":"Heintz, J., Roy, M.-F., and Solern\u00f3, P. (1993). Description of the connected components of a semialgebraic set in single exponential time. Discrete and Computational Geometry, 6:1\u201320.","journal-title":"Discrete and Computational Geometry"},{"key":"13_CR32","unstructured":"Hong, H. (1990). QEPCAD - quantifier elimination by partial cylindrical algebraic decomposition. http:\/\/www.cs.usna.edu\/~qepcad\/B\/QEPCAD.html ."},{"key":"13_CR33","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1006\/jcss.1995.1051","volume":"51","author":"P. C. Kanellakis","year":"1995","unstructured":"Kanellakis, P. C., Kuper, G., and Revesz, P. Z. (1995). Constraint query languages. Journal of Computer and System Sciences, 51:26\u201352.","journal-title":"Journal of Computer and System Sciences"},{"key":"13_CR34","doi-asserted-by":"crossref","unstructured":"Kreutzer, S. (2001). Operational semantics for fixed-point logics on constraint databases. In Logic for programming, artificial intelligence, and reasoning, volume 2250 of Lecture Notes in Compututer Science, pages 470\u2013484. Springer-Verlag.","DOI":"10.1007\/3-540-45653-8_32"},{"issue":"4","key":"13_CR35","doi-asserted-by":"publisher","first-page":"1530","DOI":"10.2307\/2695063","volume":"65","author":"B. Kuijpers","year":"2000","unstructured":"Kuijpers, B., Paredaens, J., and Van den Bussche, J. (2000). Topological elementary equivalence of closed semi-algebraic sets in the real plane. J. Symbolic Logic, 65(4):1530\u20131555.","journal-title":"J. Symbolic Logic"},{"key":"13_CR36","doi-asserted-by":"crossref","unstructured":"Kuper, G. M., Libkin, L., and Paredaens, J., editors (2000). Constraint Databases. Springer-Verlag.","DOI":"10.1007\/978-3-662-04031-7"},{"key":"13_CR37","unstructured":"Motzkin, T. S. (1936). Beitr\u00e4ge zur Theorie der linearen Ungleichungen. Doctoral dissertation. Universit\u00e4t Z\u00fcrich."},{"key":"13_CR38","unstructured":"Paredaens, J., Van den Bussche, J., and Van Gucht, D. (1994). Towards a theory of spatial database queries. In Proceedings of the Thirteenth ACM Symposium on Principles of Database Systems, pages 279\u2013288."},{"key":"13_CR39","doi-asserted-by":"crossref","unstructured":"Paredaens, J., Van den Bussche, J., and Van Gucht, D. (1995). First-order queries on finite structures over the reals. In Proceedings of the 10th IEEE Symposium on Logic in Computer Science, pages 79\u201389.","DOI":"10.1109\/LICS.1995.523246"},{"key":"13_CR40","unstructured":"Revesz, R. Z. (2002). Introduction to Constraint Databases. Springer-Verlag."},{"key":"13_CR41","unstructured":"Rigaux, Ph., Scholl, M., and Voisard, A. (2000). Introduction to Spatial Databases: Applications to GIS. Morgan Kaufmann."},{"key":"13_CR42","doi-asserted-by":"publisher","first-page":"365","DOI":"10.2307\/1969640","volume":"60","author":"A. Seidenberg","year":"1954","unstructured":"Seidenberg, A. (1954). A new decision method for elementary algebra. Ann. of Math. (2), 60:365\u2013374.","journal-title":"Ann. of Math. (2)"},{"key":"13_CR43","unstructured":"Stolboushkin, A.P. and Taitslin, M.A. (1996). Linear vs. order constraints over rational databases. In Proceedings of the 15th ACM Symposium on Principles of Database Systems, pages 17\u201327."},{"key":"13_CR44","unstructured":"Tarski, A. (1948). A Decision Method for Elementary Algebra and Geometry. University of California Press."},{"key":"13_CR45","unstructured":"TERA-project (1993). http:\/\/tera.medicis.polytechnique.fr\/index.html ."},{"key":"13_CR46","unstructured":"van den Dries, L. (1998). Tame Topology and O-minimal Structures, volume 248 of London Mathematical Society Lecture Note Series. Cambridge University Press."},{"key":"13_CR47","first-page":"468","volume-title":"Proceedings of the 2nd Conference on Principles and practice of constraint programming, volume 1118 of Lecture Notes in Computer Science","author":"L. Vandeurzen","year":"1996","unstructured":"Vandeurzen, L., Gyssens, M., and Van Gucht, D. (1996). On query languages for linear queries definable with polynomial constraints. In Freuder, E. F., editor, Proceedings of the 2nd Conference on Principles and practice of constraint programming, volume 1118 of Lecture Notes in Computer Science, pages 468\u2013481, Berlin. Springer-Verlag."}],"container-title":["Handbook of Spatial Logics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4020-5587-4_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T15:13:38Z","timestamp":1556810018000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4020-5587-4_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9781402055867","9781402055874"],"references-count":47,"URL":"https:\/\/doi.org\/10.1007\/978-1-4020-5587-4_13","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-1-4020-5587-4","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2007]]}}}