Complete geometrical query languages

Abstract

We introduce query languages for spatial databases that are complete, in the sense that they can express precisely all computable queries that are generic with respect to certain classes of transformations of space, corresponding to certain geometric interpretations of spatial data. We thus extend Chandra and Harel's seminal work on computable queries for relational databases to a spatial setting. We use a constraint-based spatial data model which models spatial data as semi-algebraic relations over the real numbers. We also introduce natural point-based query languages that are complete realtive to the basic class of queries expressible in the relations calculus with real polynomial constraints.