On the desirability and limitations of linear spatial database models

Abstract

A general linear spatial database model is presented in which both the representation and the manipulation of non-spatial data is based on first-order logic over the real numbers with addition. We first argue the naturalness of our model and propose it as a general framework to study and compare linear spatial database models. However, we also establish that no reasonable safe extension of our data manipulation language can be complete for the linear spatial queries in that even very simple queries such as deciding colinearity or computing convex hull of a finite set of points cannot be expressed. We show that this fundamental result has serious ramifications for the way in which query languages for linear spatial database models have to be designed.