Document Server@UHasselt >
Research >
Research publications >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/13463

Title:  On the Decidability of SemiLinearity of SemiAlgebraic Sets and Its Implications for Spatial Databases 
Authors:  Dumortier, Freddy Gyssens, Marc Van Gucht, Dirk Vandeurzen, Luc 
Issue Date:  1997 
Publisher:  ACM Press 
Citation:  Proceedings of the Sixteenth ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems, p. 6877 
Abstract:  Several authors have suggested to use firstorder 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 semialgebraic 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 socalled polynomial model is more desirable. In the socalled 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 semilinearity is decidable for semialgebraic sets. In doing so, we point out important subtleties related to the type of the coefficients in the linear inequalities used to describe semilinear 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 semilinear set can be computed in FO + linear.
The decidability of semilinearity of semialgebraic 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. 
URI:  http://hdl.handle.net/1942/13463 
DOI:  10.1145/263661.263670 
ISBN:  0897919106 
Type:  Proceedings Paper 
Appears in Collections:  Research publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
