A characterization of first-order topological properties of planar spatial data

ABSTRACT

Planar spatial datasets can be modeled by closed semi-algebraic sets in the plane. We establish a characterization of the topological properties of such datasets expressible in the relational calculus with real polynomial constraints. The characterization is in the form of a query language that can only point that can only talk about points in the set and the “cones” around these points.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: Michael Benedikt , Guozhu Dong , Leonid Libkin , Limsoon Wong, Relational expressive power of constraint query languages, Journal of the ACM (JACM), v.45 n.1, p.1-34, Jan. 1998 [doi>10.1145/273865.273870]
• 3: Michael Benedikt , Jan Van den Bussche , Christof Löding , Thomas Wilke, A characterization of first-order topological properties of planar spatial data, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055575]
• 4: Bochnak, J., Coste, M., and Roy, M.-F. 1998. Real Algebraic Geometry. Springer-Verlag, New York.
• 5: Ebbinghaus, H.-D., and Flum, J. 1995. Finite Model Theory. Springer-Verlag, New York.
• 6: Ebbinghaus, H.-D., Flum, J., and Thomas, W. 1984. Mathematical Logic. Undergraduate Texts in Mathematics. Springer-Verlag, New York.
• 7: Egenhofer, M., and Franzosa, R. 1991. Point-set topological spatial relations. Int. J. Geograph. Inf. Syst. 5, 2, 161--174.
• 8: Egenhofer, M., and Franzosa, R. 1995. On the equivalence of topological relations. Int. J. Geograph. Inf. Syst. 9, 2, 133--152.
• 9: Egenhofer, M., and Mark, D. 1995. Modeling conceptual neighborhoods of topological line-region relations. Int. J. Geograph. Inf. Syst. 9, 5, 555--565.
• 10: Gaifman, H. 1982. On local and nonlocal properties. In Proceedings of the Herbrand symposium (Marseilles, 1981), Studies in Logic and the Foundations of Mathematics, vol. 107 North-Holland, Amstendam, The Netherlands.
• 11: Martin Grohe , Luc Segoufin, On first-order topological queries, ACM Transactions on Computational Logic (TOCL), v.3 n.3, p.336-358, July 2002 [doi>10.1145/507382.507384]
• 12: Stéphane Grumbach , Jianwen Su, Queries with arithmetical constraints, Theoretical Computer Science, v.173 n.1, p.151-181, Feb. 1997 [doi>10.1016/S0304-3975(96)00194-6]
• 13: John E. Hopcroft , Rajeev Motwani , Rotwani , Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computability, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2000
• 14: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Journal of Computer and System Sciences, v.51 n.1, p.26-52, Aug. 1995
• 15: Bart Kuijpers , Jan Van den Bussche, On Capturing First-Order Topological Properties of Planar Spatial Databases, Proceeding of the 7th International Conference on Database Theory, p.187-198, January 10-12, 1999
• 16: Kuper, G., Libkin, L., and Paredaens, J. Ed. 2000. Constraint Databases. Springer-Verlag, New York.
• 17: Laurini, R., and Thompson, D. 1992. Fundamentals of Spatial Information Systems. Number 37 in APIC Series. Academic Press.
• 18: Leonid, L. 2004. Elements of Finite Model Theory. Springer-Verlag, New York.
• 19: Robert McNaughton , Seymour A. Papert, Counter-Free Automata (M.I.T. research monograph no. 65), The MIT Press, 1971
• 20: Moise, E. E. 1977. Geometric topology in dimensions 2 and 3, volume 47 of Graduate Texts in Mathematics. Springer-Verlag, New York.
• 21: Martin Otto , Jan Van den Bussche, First-order queries on databases embedded in an infinite structure, Information Processing Letters, v.60 n.1, p.37-41, Oct. 14, 1996 [doi>10.1016/S0020-0190(96)00140-8]
• 22: C. H. Papadimitriou , D. Suciu , V. Vianu, Topological queries in spatial databases, Journal of Computer and System Sciences, v.58 n.1, p.29-53, Feb. 1999 [doi>10.1006/jcss.1998.1597]
• 23: Paredaens, J., Kuijpers, B., and Van den Bussche, J. 2000. On topological elementary equivalence of closed semi-algebraic sets in the plane. J. Symb. Logic 65, 4, 1530--1555.
• 24: Jan Paredaens , Jan Van den Bussche , Dirk Van Gucht, Towards a theory of spatial database queries (extended abstract), Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.279-288, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182640]
• 25: Luc Segoufin , Victor Vianu, Querying spatial databases via topological invariants, Journal of Computer and System Sciences, v.61 n.2, p.270-301, Oct. 2000 [doi>10.1006/jcss.2000.1712]
• 26: Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
• 27: Van den Dries, L. 1998. Tame Topology and O-Minimal Structures. Cambridge University Press, Cambridge, MA.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Languages, Theory