The linear database model, in which semi-linear sets are the only geometric objects, has been identified as suitable for spatial database applications from both modeling expressiveness as query efficiency considerations. For querying linear databases, the language FO + linear has been proposed. In this paper, we examine the expressiveness of this language. First, we present a list of general queries expressible in FO + linear. In particular, we mention the dimension query, which in turn allows us to express several other interesting linear queries. Next, we show the non-expressibility in FO + linear of a whole class of linear queries that are related to sets not definable by linear formulae, a result which demonstrates the need for more expressive linear query languages. We present a method to extend FO + linear with operators in a sound way with respect to the linear queries expressible in FO + poly, and argue its validity by comparing it to another paradigm for enriching FO + linear. Whether any of the proposed extensions is complete for the linear queries definable in FO + poly remains open. (C) 2001 Elsevier Science B.V. All rights reserved. [References: 49]
展开▼
