Complete geometric query languages

We extend Chandra and Harel's seminal work on computable queries for relati onal databases to a setting in which also spatial data may be present using a constraint-based data model. Concretely, we introduce both coordinate-ba sed and point-based query languages that are complete in the sense that the y can express precisely all computable queries that are genetic with respec t to certain classes of transformations of space, corresponding to certain geometric interpretations of spatial data. The languages we introduce are o btained by augmenting basic languages with a "while" construct. We also sho w that the respective basic point-based languages are complete: relative to the subclass of the corresponding generic queries consisting of those that are expressible in the relational calculus with real polynomial constraint s. (C) 1999 Academic Press.