Please use this identifier to cite or link to this item: `http://hdl.handle.net/1942/13463`
 Title: On the Decidability of Semi-Linearity of Semi-Algebraic Sets and Its Implications for Spatial Databases Authors: DUMORTIER, Freddy GYSSENS, Marc Van Gucht, DirkVANDEURZEN, Luc Issue Date: 1997 Publisher: ACM Press Source: Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, p. 68-77 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. Document URI: http://hdl.handle.net/1942/13463 ISBN: 0-89791-910-6 DOI: 10.1145/263661.263670 Rights: 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. Type: Proceedings Paper Appears in Collections: Research publications

#### Page view(s)

48
checked on May 25, 2022