A. , S. Abiteboul, and V. Vianu, Computing with rst-order logic, Journal of Computer and System Sciences, vol.50, issue.2, pp.309-335, 1995.

J. Bochnak, M. Coste, and M. Roy, Real Algebraic Geometry, 1998.
DOI : 10.1007/978-3-662-03718-8

M. Benedikt, G. Dong, L. Libkin, and L. Wong, Relational expressive power of constraint query languages, Journal of the ACM, vol.45, issue.1, pp.1-34, 1998.
DOI : 10.1145/273865.273870

M. Ben-or, D. Kozen, and J. Reif, The complexity of elementary algebra and geometry, Journal of Computer and System Sciences, pp.251-264, 1986.

J. Cai, M. , and N. Immerman, An optimal lower bound on the number of variables for graph identification, Combinatorica, vol.9, issue.No. 4, pp.389-410, 1992.
DOI : 10.1007/BF01305232

]. J. Cor79 and . Corbett, Topological principles in cartography, US Bureau of the Census, 1979.

]. M. Cos89 and . Coste, EEective Semialgebraic Geometry, Geometry and Robotics, pp.1-27, 1989.

]. R. Cro63, R. Crowell, and . Fox, Introduction to knot theory, 1963.

A. Dawar, S. Lindell, and S. Weinstein, Infinitary Logic and Inductive Definability over Finite Structures, Information and Computation, vol.119, issue.2, pp.160-175, 1995.
DOI : 10.1006/inco.1995.1084
URL : http://doi.org/10.1006/inco.1995.1084

]. M. Ege93 and . Egenhofer, A Model for Detailed Binary Topological Relationships, Geomatica, vol.47, issue.3-4, pp.261-273, 1993.

M. J. Egenhofer and R. Franzosa, Point-set topological spatial relations, International journal of geographical information systems, vol.2, issue.2, pp.161-174, 1991.
DOI : 10.1109/32.6141

]. M. Ef95a, R. Egenhofer, and . Franzosa, On the Equivalence of Topological Relations, Int'l J. of Geographical Information Systems, vol.9, issue.2, pp.133-152, 1995.

E. Ebbinghaus and J. Flum, Finite Model Theory, 1995.

R. Franzosa and M. Egenhofer, Topological spatial relations based on components and dimensions of set intersections, Vision Geometry, pp.236-246, 1992.
DOI : 10.1117/12.142172

]. M. Ege94 and . Egenhofer, Spatial SQL: A Query and Presentation Language, IEEE Transactions on Knowledge and Data Engineering, vol.6, issue.1, pp.86-95, 1994.

A. Frank and W. Kuhn, Cell Graph: A Provable Correct Method for the Storage of Geometry, Proc. Second International Symposium on Spatial Data Handling, pp.411-436, 1986.

F. R. Fagin, L. Stockmeyer, and M. Vardi, On monadic NP vs. monadic co-NP, [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference, pp.78-92, 1995.
DOI : 10.1109/SCT.1993.336544
URL : http://doi.org/10.1006/inco.1995.1100

G. , E. , and M. Otto, Inductive deenability with counting on nite structures, Computer Science Logic, CSL'92 Selected Papers, pp.231-247, 1993.

]. M. Gro97 and . Grohe, Large Finite Structures with Few L k -Types, Proc. Symp. on Logic in Computer Science, 216{227, 1997.

]. M. Gro98 and . Grohe, Fixed-point logics on planar graphs, Proc. Symp. on Logic in Computer Science, pp.6-15, 1998.

G. , S. Grumbach, and G. Kuper, Tractable recursion over geometric data, Proc. Int'l. Conf. on Constraint Programming, 1997.

G. , S. Grumbach, and J. Su, Queries with Arithmetical Constraints, Theoretical Computer Science, vol.173, issue.1, pp.151-181, 1997.
DOI : 10.1016/s0304-3975(96)00194-6
URL : http://doi.org/10.1016/s0304-3975(96)00194-6

G. , S. Grumbach, and J. Su, Finitely representable databases, Journal of Computer and System Sciences, vol.55, issue.2, pp.273-298, 1997.
DOI : 10.1006/jcss.1997.1524
URL : https://hal.archives-ouvertes.fr/inria-00120273

G. S. Grumbach, J. Su, and C. Tollu, Linear constraint databases, Proc.Logic and Complexity Workshop, 1994.

]. Y. Gur84 and . Gurevich, Toward logic tailored for computational complexity, Computation and Proof Theory, 1984.

]. Y. Gur88 and . Gurevich, Logic and the challenge of computer science, Theoretical Computer Science (E. Borger, pp.1-57, 1988.

]. J. Her91 and . Herring, TIGRIS: A Data Model for an Object-Oriented Geographic Information System, Computers and Geosciences, vol.18, issue.4, pp.443-452, 1991.

I. and L. G. Base-de-donn-ees-topographiques-de-l-'i, The Cartographical Database of the National Geographic Institute, in French.) Bulletin d'Information de l'I, 1991.

]. N. Imm86 and . Immerman, Relational queries computable in polynomial time, Information and Control, 1986.

]. N. Imm87 and . Immerman, Expressibility as a complexity measure: results and directions, Proc. 2nd Structure in Complexity Conference, 1987.

D. Kozen and C. Yap, Algebraic cell decomposition in NC, 26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pp.515-521, 1985.
DOI : 10.1109/SFCS.1985.4

K. B. Kuijpers, J. Paredaens, and J. Van-den-bussche, Lossless representation of topological spatial data, Proc. Fourth Int'l. Symp. on Large Spatial Databases, 1{13, 1995.
DOI : 10.1007/3-540-60159-7_1

B. Kuijpers, J. Paredaens, and J. Van-den-bussche, On topological elementary equivalence of spatial databases, Proc. Int'l. Conf. on database Theory, pp.432-446, 1997.
DOI : 10.1007/3-540-62222-5_62

]. S. Mor85 and . Morehouse, ARC/INFO: A Geo-Relational Model for Spatial Information, Proc. Int'l. Symp. on Computer Assisted Cartography (Auto-Carto 7), pp.388-397, 1985.

]. S. Mor89 and . Morehouse, The Architecture of ARC/INFO, Proc. Int'l. Symp. on Computer Assisted Cartography (Auto-Carto 9), pp.266-277, 1989.

]. A. Mar58 and . Markov, Unsolvability of the problem of homeomorphy, Proc. Int'l Congress of Mathematics, pp.300-306, 1958.

O. , P. Van-oosterom, and T. Vijlbrief, Building a GIS on Top of the Open DBMS Postgres, EGIS '91, pp.775-787, 1991.

P. , C. H. Papadimitriou, D. Suciu, and V. Vianu, Topological Queries in Spatial Databases, In Journal of Computer and System Sciences, vol.58, issue.1, pp.29-53, 1999.
DOI : 10.1007/3-540-48168-0_1

J. Paredaens, J. Van-den-bussche, and D. Van-gucht, Towards a theory of spatial database queries, Proc. ACM Symp. on Principles of Database Systems, pp.279-288, 1994.

]. J. Par95 and . Paredaens, Spatial Databases, the Final Frontier, Proc. 5th Int'l. Conf. on Database Theory, pp.14-32, 1995.

]. J. Par+95, J. Paredaens, D. Van-den-bussche, and . Van-gucht, First-order queries on nite structures over the reals, Proc. IEEE Conf. on Logic in Computer Science, 79{87, 1995.

]. J. Ren92 and . Renegar, On the computational complexity and geometry of the rst-order theory of the reals, J. of Symbolic Computation, pp.255-300, 1992.

]. J. Ros82 and . Rosenstein, Linear Orderings, 1982.

G. Rozenberg and A. Salomaa, Handbook of formal languages, 1997.

]. L. Seg and . Segouun, Manipulation de donn ees spatiales et topologiques, 1999.

]. M. Seq, J. Stonebraker, K. Frew, J. Gardels, and . Meredith, The Sequoia 2000 Storage Benchmark, Proc. ACM SIGMOD Int'l. Conf. on the Management of Data, pp.2-11, 1993.

P. Svensson, H. Zhexue, and . Geo-sal, Geo-SAL: A query language for spatial data analysis, Proc. Advances in Spatial Databases-Second Symposium, SSD '91, pp.119-140, 1991.
DOI : 10.1007/3-540-54414-3_35

]. A. Tar51 and . Tarski, A Decision Method for Elementary Algebra and Geometry, 1951.

]. M. Var82 and . Vardi, The complexity of relational query languages, Proc. 14th ACM Symp. on Theory of Computing, pp.137-146, 1982.

]. M. Wor92 and . Worboys, A Geometric Model for Planar Geographical Objects. Int'l, J. of Geographical Information Systems, vol.6, issue.5, pp.353-372, 1992.