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

ABSTRACT

Closed semi-algebraic sets in the plane form a powerful model of planar spatial datasets. 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 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: J. Bochnak, M. Coste, and M.-F. Roy. Real Algebraic Geometry. Springer-Verlag, 1998.
• 4: H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 1995.
• 5: M. Egenhofer and R. Franzosa. Point-set topological spatial relations. Int. J. Geographical Information Systems, 5(2):161--174, 1991.
• 6: M. Egenhofer and R. Franzosa. On the equivalence of topological relations. Int. J. Geographical Information Systems, 9(2):133--152, 1995.
• 7: M. Egenhofer and D. Mark. Modeling conceptual neighborhoods of topological line-region relations. Int. J. Geographical Information Systems, 9(5):555--565, 1995.
• 8: 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]
• 9: 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]
• 10: 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
• 11: 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
• 12: G. Kuper, L. Libkin, and J. Paredaens, editors. Constraint Databases. Springer, 2000.
• 13: R. Laurini and D. Thompson. Fundamentals of Spatial Information Systems. Number 37 in APIC Series. Academic Press, 1992.
• 14: Robert McNaughton , Seymour A. Papert, Counter-Free Automata (M.I.T. research monograph no. 65), The MIT Press, 1971
• 15: E. E. Moise. Geometric topology in dimensions 2 and 3, volume 47 of Graduate Texts in Mathematics. Springer, 1977.
• 16: 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]
• 17: 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]
• 18: Jan Paredaens , Bart Kuijpers, Data models and query languages for spatial databases, Data & Knowledge Engineering, v.25 n.1-2, p.29-53, March 1998 [doi>10.1016/S0169-023X(98)00052-4]
• 19: J. Paredaens, B. Kuijpers, and J. Van den Bussche. On topological elementary equivalence of closed semi-algebraic sets in the plane. Journal of Symbolic Logic, 65(4):1530--1555, 2000.
• 20: 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]
• 21: 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]
• 22: Wolfgang Thomas, Languages, automata, and logic, Handbook of formal languages, vol. 3: beyond words, Springer-Verlag New York, Inc., New York, NY, 1997
• 23: L. van den Dries. Tame Topology and O-Minimal Structures. Cambridge University Press, 1998.