The research presented in this paper is situated in the framework of constraint databases introduced by Kanellakis, Kuper, and Revesz in their seminal paper of 1990, specifically, the language with real polynomial constraints (FO+poly). For reasons of efficiency, this model is implemented with only linear polynomial constraints, but this limitation to linear polynomial constraints has severe implications on the expressive power of the query language. In particular, when used for modeling spatial data, important queries that involve Euclidean distance are not expressible. The aim of this paper is to identify a class of two‐dimensional constraint databases and a query language within the constraint model that go beyond the linear model and allow the expression of queries concerning distance. We seek inspiration in the Euclidean constructions, i.e., constructions by ruler and compass. We first present a programming language that captures exactly the first‐order ruler‐and‐compass constructions that are expressible in a first‐order language with real polynomial constraints. If this language is extended with a while operator, we obtain a language that is complete for all ruler‐and‐compass constructions in the plane. We then transform this language in a natural way into a query language on finite point databases, but this language turns out to have the same expressive power as FO+poly and is therefore too powerful for our purposes. We then consider a safe fragment of this language and use this to construct a query language that allows the expression of Euclidean distance without having the full power of FO+poly.

We exhibit a coordinate-based language, called PFOL, which is sound for the linear queries computable in first-order logic over the reals and extends the latter's restriction to linear arithmetic. To evaluate its expressive power, we first consider PFOL-fin, the PFOL queries that compute finite outputs upon finite inputs. In order to study this fragment of PFOL, we also define a syntactical language, called SPFOL, which is safe with respect to queries from finite inputs to finite outputs. We show that SPFOL has the same expressive power as SafeEuQl [15], whence all ruler-and-compass constructions in the plane on finite sets of points can be expressed in SPFOL. This result gives a geometrical justification of SPFOL, and highlights the richness of PFOL-fin. Then, we define finite representations for arbitrary semi-linear sets and show that there are PFOL programs for both the encoding and the decoding. This result is used (i) to identify a broad, natural class of linear queries expressible in PFOL, highlighting the richness of general PFOL, and (ii) to establish a general theorem about lifting query languages on finite databases to query languages on arbitrary linear databases. This theorem is applied to a recent result of Benedikt and Libkin [5] from finite to arbitrary semi-linear sets, yielding the existence of a natural, syntactically definable fragment of FO+poly sound and complete for all FO+poly-expressible linear queries.

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 inequalities. 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 denable language precisely expressing the linear queries expressible in FO + poly.