Article

Linear Approximation of Semi-algebraic Spatial Databases Using Transitive Closure Logic, in Arbitrary Dimension

Author:

Floris GeertsAuthors Info & Claims

DBPL '01: Revised Papers from the 8th International Workshop on Database Programming Languages

Pages 182 - 197

Published: 08 September 2001 Publication History

Abstract

We consider n-dimensional semi-algebraic spatial databases. We compute in first-order logic extended with a transitive closure operator, a linear spatial database which characterizes the semi-algebraic spatial database up to a homeomorphism. In this way, we generalize our earlier results to semi-algebraic spatial databases in arbitrary dimensions, our earlier results being true for only two dimensions.Consequently, we can prove that first-order logic with a transitive closure operator extended with stop conditions, can express all Boolean topological queries on semi-algebraic spatial databases of arbitrary dimension.

References

[1]

R. Benedetti and J.J. Risler. Real Algebraic and Semi-algebraic Sets. Hermann, Paris, 1990.

[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]

M. Benedikt, M. Grohe, L. Libkin, and L. Segoufin. Reachability and connectivity queries in constraint databases. In Proceedings of the 19th ACM Symposium on Principles of Database Systems, pages 104-115. ACM Press, 2000.

[4]

M. Benedikt and L. Libkin. Safe constraint queries. SIAM Journal of Computing, 29(5):1652-1682, 2000.

[5]

J. Bochnak, M. Coste, and M.-F. Roy. Real Algebraic Geometry, volume 36 of Ergebenisse der Mathematik und ihrer Grenzgebiete. Springer-Verlag, 1998.

[6]

A. Chandra and D. Harel. Computable queries for relational data bases. Journal of Computer and System Sciences, 21(2):156-178, 1980.

[7]

F. Geerts and B. Kuijpers. Expressing topological connectivity of spatial databases. In Research Issues in Structured and Semistructured Database Programming. Proceedings of the 8th International Workshop on Database Programming Languages, volume 1949 of Lecture Notes in Computer Science, pages 224-238. Springer-Verlag, 1999.

[8]

F. Geerts and B. Kuijpers. Linear approximation of planar spatial databases using transitive-closure logic. In Proceedings of the 19th ACM Symposium on Principles of Database Systems, pages 126-135. ACM Press, 2000.

[9]

S. Grumbach and G. Kuper. Tractable recursion over geometric data. In G. Smolka, editor, Proceedings of the 3rd Conference on Principles and Practice of Constraint Programming, volume 1330 of Lecture Notes in Computer Science, pages 450-462. Springer-Verlag, 1997.

[10]

S. Grumbach and J. Su. Finitely representable databases. Journal of Computer and System Sciences, 55(2):273-298, 1997.

[11]

S. Grumbach and J. Su. Queries with arithmetical constraints. Theoretical Computer Science, 173(1):151-181, 1997.

[12]

V. Guillemin and A. Pollack. Differential topology. Prentice-Hall, 1974.

[13]

M. Gyssens, J. Van den Bussche, and D. Van Gucht. Complete geometrical query languages. Journal of Computer and System Sciences, 58(1):483-511, 1999.

[14]

P.C. Kanellakis, G.M. Kuper, and P.Z. Revesz. Constraint query languages. Journal of Computer and System Science, 51(1):26-52, 1995.

[15]

S. Kreutzer. Fixed-point query languages for linear constraint databases. In Proceedings of the 19th ACM Symposium on Principles of Database Systems, pages 116-125. ACM Press, 2000.

[16]

S. Kreutzer. Query languages for constraint databases: First-order logic, fixed-points, and convex hulls. In J. Van den Bussche and V. Vianu, editors, Proceedings of the 9th International Conference on Database Theory, volume 1973 of Lecture Notes in Computer Science, pages 248-262. Springer-Verlag, 2001.

[17]

G.M. Kuper, J. Paredaens, and L. Libkin, editors. Constraint Databases. Springer-Verlag, 1999.

[18]

E. Rannou. The complexity of stratification computation. Discrete and Computational Geometry, 19:47-79, 1998.

[19]

M. Shiota. Geometry of Subanalytic and Semialgebraic Sets. Birkhäuser, 1997.

[20]

L. Vandeurzen, M. Gyssens, and D. Van Gucht. An expressive language for linear spatial database queries. In Proceedings of the 17th ACM Symposium on Principles of Database Systems, pages 109-118. ACM Press, 1998.

[21]

L. Vandeurzen, M. Gyssens, and D. Van Gucht. On query languages for linear queries definable with polynomial constraints. In E. F. Freuder, editor, Proceedings of the 2nd Conference on Principles and Practice of Constraint Programming, volume 1118 of Lecture Notes in Computer Science, pages 468-481, Springer-Verlag, 1996.

Cited By

Geerts FKuijpers B(2005)On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databasesTheoretical Computer Science10.1016/j.tcs.2004.10.034336:1(125-151)Online publication date: 25-May-2005
https://dl.acm.org/doi/10.1016/j.tcs.2004.10.034

Linear Approximation of Semi-algebraic Spatial Databases Using Transitive Closure Logic, in Arbitrary Dimension
1. Information systems
  1. Data management systems
2. Theory of computation

Recommendations

Linear approximation of planar spatial databases using transitive-closure logic
PODS '00: Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

We consider spatial databases in the plane that can be defined by polynomial constraint formulas. Motivated by applications in geographic information systems, we investigate linear approximations of spatial databases and study in which language they can ...
Non-well-founded Proof Theory of Transitive Closure Logic

Supporting inductive reasoning is an essential component is any framework of use in computer science. To do so, the logical framework must extend that of first-order logic. Transitive closure logic is a known extension of first-order logic that is ...
Linearization and Completeness Results for Terminating Transitive Closure Queries on Spatial Databases

We study queries to spatial databases, where spatial data are modeled as semi-algebraic sets, using the relational calculus with polynomial inequalities as a basic query language. We work with the extension of the relational calculus with terminating ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

DBPL '01: Revised Papers from the 8th International Workshop on Database Programming Languages

September 2001

341 pages

ISBN:3540440801

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 08 September 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Geerts FKuijpers B(2005)On the decidability of termination of query evaluation in transitive-closure logics for polynomial constraint databasesTheoretical Computer Science10.1016/j.tcs.2004.10.034336:1(125-151)Online publication date: 25-May-2005
https://dl.acm.org/doi/10.1016/j.tcs.2004.10.034

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents