Constraint-based query optimization for spatial databases

We present a method for converting a system of multivariate Boolean constraints into a sequence of univariate range queries of the type supported by current spatial databases. The method relies on the transformation of a Boolean constraint system into triangular form. We extend previous results in this area by considering negative as well as positive constraints. We also present a method to approximate triangular Boolean constraints by bounding box constraints. 1 Introduction In spatial database systems, there is a gap between the high-level query language required by applications and users, and the simpler query language supported by the underlying spatial data-structure. Typically, applications such as geographic information systems [5, 8, 10], visual language parsers [7], VLSI design rule checkers [14], require a query language in which queries and integrity constraints may be expressed over a number of variables subject to Boolean constraints (that is, constraints over sets). In ...