On the Decidability of Semi-Linearity of Semi-Algebraic Sets and Its Implications for Spatial Databases.

@inproceedings{DBLP:conf/pods/GuchtDGV97,
  author    = {Freddy Dumortier and
               Marc Gyssens and
               Luc Vandeurzen and
               Dirk Van Gucht},
  title     = {On the Decidability of Semi-Linearity of Semi-Algebraic Sets
               and Its Implications for Spatial Databases},
  booktitle = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona},
  publisher = {ACM Press},
  year      = {1997},
  isbn      = {0-89791-910-6},
  pages     = {68-77},
  ee        = {http://doi.acm.org/10.1145/263661.263670, db/conf/pods/GuchtDGV97.html},
  crossref  = {DBLP:conf/pods/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Several authors have suggested to use first-order logic over the real numbers to describe spatial database applications. Geometric objects are then described by polynomial inequalities with integer coefficients involving the coordinates of the objects. Such geometric objects are called semi-algebraic sets. Similarly, queries are expressed by polynomial inequal- ities. The query language thus obtained is usually referred to as FO + poly.

From a practical point of view, it has been argued that a linear restriction of this so-called polynomial model is more desirable. In the so-called linear model, geometric objects are described by linear inequalities, and are called semilinear sets. The language of the queries expressible by linear inequalities is usually referred to as FO + linear.

As part of a general study of the feasibility of the linear model, we show in this paper that semi-linearity is decidable for semi-algebraic sets. In doing so, we point out important subtleties related to the type of the coefficients in the linear inequalities used to describe semi-linear sets. An important concept in the development of the paper is regularity, of which we point out the geometric significance. We show that the regular points of a semi-linear set can be computed in FO + linear.

The decidability of semi-linearity of semi-algebraic sets has an important consequence. It has been shown that it is undecidable whether a query expressible in FO + poly is linear, i.e., maps spatial databases of the linear model into spatial databases of the linear model. It follows now that, despite this negative result, there exists a syntactically definable language precisely expressing the linear queries expressible in FO + poly.

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Foto N. Afrati, Stavros S. Cosmadakis, Stéphane Grumbach, Gabriel M. Kuper: Linear vs Polynomial Constraints in Database Query Languages. PPCP 1994: 181-192 BibTeX

[2]

Michael Benedikt, Guozhu Dong, Leonid Libkin, Limsoon Wong: Relational Expressive Power of Constraint Query Languages. PODS 1996: 5-16 BibTeX

[3]

...

[4]

...

[5]

...

[6]

...

[7]

...

[8]

...

[9]

Tien Huynh, Catherine Lassez, Jean-Louis Lassez: Fourier Algorithm Revisited. ALP 1990: 117-131 BibTeX

[10]

...

[11]

Alfons Kemper, Mechtild Wallrath: An Analysis of Geometric Modeling in Database Systems. ACM Comput. Surv. 19(1): 47-91(1987) BibTeX

[12]

Paris C. Kanellakis, Gabriel M. Kuper, Peter Z. Revesz: Constraint Query Languages. J. Comput. Syst. Sci. 51(1): 26-52(1995) BibTeX

[13]

Gabriel M. Kuper: On The Expressive Power of the Relational Calculus with Arithmetic Constraints. ICDT 1990: 202-211 BibTeX

[14]

...

[15]

...

[16]

Jürg Nievergelt, Michael Freeston: Special Issue Editorial: Other Objects, or: What is unique about Spatial Data? Comput. J. 37(1): 1-2(1994) BibTeX

[17]

Jan Paredaens, Jan Van den Bussche, Dirk Van Gucht: Towards a Theory of Spatial Database Queries. PODS 1994: 279-288 BibTeX

[18]

Niki Pissinou, Richard T. Snodgrass, Ramez Elmasri, Inderpal Singh Mumick, M. Tamer Özsu, Barbara Pernici, Arie Segev, Babis Theodoulidis, Umeshwar Dayal: Towards an Infrastructure for Temporal Databases: Report of an Invitational ARPA/NSF Workshop. SIGMOD Record 23(1): 35-51(1994) BibTeX

[19]

...

[20]

...

[21]

...

[22]

...

[23]

Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: On the Desirability and Limitations of Linear Spatial Database Models. SSD 1995: 14-28 BibTeX

[24]

Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: On Query Languages for Linear Queries Definable with Polynomial Constraints. CP 1996: 468-481 BibTeX

[25]

...

Referenced by

1. Stephan Kreutzer: Fixed-Point Query Languages for Linear Constraint Databases. PODS 2000: 116-125
2. Floris Geerts, Bart Kuijpers: Linear Approximation of Planar Spatial Databases Using Transitive-Closure Logic. PODS 2000: 126-135
3. Stéphane Grumbach, Philippe Rigaux, Luc Segoufin: The DEDALE System for Complex Spatial Queries. SIGMOD Conference 1998: 213-224
4. Luc Vandeurzen, Marc Gyssens, Dirk Van Gucht: An Expressive Language for Linear Spatial Database Queries. PODS 1998: 109-118
5. Michael Benedikt, Leonid Libkin: Safe Constraint Queries. PODS 1998: 99-108
6. Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo Giulio Franciosa, Jeffrey Scott Vitter: Efficient Searching with Linear Constraints. PODS 1998: 169-178
7. Jan Paredaens, Bart Kuijpers, Gabriel M. Kuper, Luc Vandeurzen: Eucil, Tarski, and Engler Encompassed (Preliminary Report). DBPL 1997: 1-24