skip to main content
10.1145/1055558.1055575acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
Article

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

Published: 14 June 2004 Publication History

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]
S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.]]
[2]
M. Benedikt, G. Dong, L. Libkin, and L. Wong. Relational expressive power of constraint query languages. Journal of the ACM, 45(1):1--34, 1998.]]
[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]
M. Grohe and L. Segoufin. On first-order topological queries. ACM Transactions on Computational Logic, 3(3):336--358, 2002.]]
[9]
S. Grumbach and J. Su. Queries with arithmetical constraints. Theoretical Computer Science, 173(1):151--181, 1997.]]
[10]
P. C. Kanellakis, G. M. Kuper, and P. Z. Revesz. Constraint query languages. Journal of Computer and System Sciences, 51(1):26--52, August 1995.]]
[11]
B. Kuijpers and J. Van den Bussche. On capturing first-order topological properties of planar spatial databases. In C. Beeri and P. Buneman, editors, Database Theory, ICDT'99, volume 1540 of Lecture Notes in Computer Science, pages 187--198, 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]
R. McNaughton and S. A. Papert, Counter-Free Automata. MIT Press, Cambridge, MA, 1971.]]
[15]
E. E. Moise. Geometric topology in dimensions 2 and 3, volume 47 of Graduate Texts in Mathematics. Springer, 1977.]]
[16]
M. Otto and J. Van den Bussche. First-order queries on databases embedded in an infinite structure. Information Processing Letters, 60:37--41, 1996.]]
[17]
C. H. Papadimitriou, D. Suciu, and V. Vianu. Topological queries in spatial databases. Journal of Computer and System Sciences, 58(1):29--53, 1999.]]
[18]
J. Paredaens and B. Kuijpers. Data models and query languages for spatial databases. Data & Knowledge Engineering, 25:29--53, 1998.]]
[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]
J. Paredaens, J. Van den Bussche, and D. Van Gucht. Towards a theory of spatial database queries. In Proceedings 13th ACM Symposium on Principles of Database Systems. pages 279--288. ACM Press, 1994.]]
[21]
L. Segoufin and V. Vianu. Querying spatial databases via topological invariants. Journal of Computer and System Sciences, 61(2):270--301, 2000.]]
[22]
W. Thomas. Languages, automata, and logic. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Language Theory, volume III. Springer, 1997.]]
[23]
L. van den Dries. Tame Topology and O-Minimal Structures. Cambridge University Press, 1998.]]

Cited By

View all
  • (2007)An Ehrenfeucht-Fraïssé game approach to collapse results in database theoryInformation and Computation10.1016/j.ic.2006.10.002205:3(311-379)Online publication date: 1-Mar-2007
  • (2006)A characterization of first-order topological properties of planar spatial dataJournal of the ACM10.1145/1131342.113134653:2(273-305)Online publication date: 1-Mar-2006

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODS '04: Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
June 2004
350 pages
ISBN:158113858X
DOI:10.1145/1055558
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2004

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

SIGMOD/PODS04

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 30 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2007)An Ehrenfeucht-Fraïssé game approach to collapse results in database theoryInformation and Computation10.1016/j.ic.2006.10.002205:3(311-379)Online publication date: 1-Mar-2007
  • (2006)A characterization of first-order topological properties of planar spatial dataJournal of the ACM10.1145/1131342.113134653:2(273-305)Online publication date: 1-Mar-2006

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media