On the decidability of semilinearity for semialgebraic sets and its implications for spatial databases

Several authors have suggested using first-order logic over the real number s to describe spatial database applications. Geometric objects are then des cribed by polynomial inequalities with integer coefficients involving the c oordinates of the objects. Such geometric objects are called semialgebraic sets. Similarly, queries are expressed by polynomial inequalities. The quer y language thus obtained is usually referred to as FO + poly. From a practi cal 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, g eometric objects are described by linear inequalities and are called semili near sets. The language of the queries expressible by linear inequalities i s usually referred to as FO + linear. As part of a general study of the fea sibility of the linear model, we show in this paper that semilinearity is d ecidable for semialgebraic sets. In doing so, we point out important subtle ties related to the type of the coefficients in the linear inequalities use d to describe semilinear sets. An important concept in the development of t he paper is regular stratification. We point out the geometric significance , as well as its significance in the context of FO + linear and FO + poly c omputations. 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 t he 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. (C) 1999 Academic Press.