A representation independent language for planar spatial databases with Euclidean distance

Linear constraint databases and query languages are appropriate for spatial database applications. Not only the data model is natural to represent a large portion of spatial data suchas in GIS systems, but also there exist efficient algorithms for the core operations in the query languages. However, an important limitation of the linear constraint data model is that it cannot model constructs such as “Euclidean distance. ” A previous attempt to expend linear constraint languages withthe ability to express Euclidean distance, by Kuijpers, Kuper, Paredaens, and Vandeurzen is to adapt two fundamental Euclidean constructions withruler and compass in a first order logic over points. The language, however, requires the input database to be encoded in an ad hoc LPC representation so that the logic operations can apply. This causes a problem that sometimes queries in their language may depend on the encoding and thus do not have any natural meaning. In this paper, we propose an alternative approach and develop an algebraic language in which the traditional operators and Euclidean constructions work directly on the data represented by “semi-circular ” constraints. By avoiding the encoding step, our language do not suffer from this problem. We show that the language is closed under these operations.