Spatial query optimization: From boolean constraints to range queries

In spatial database systems, there is a gap between the high-level query language required in applications and the simpler query language supported by the underlying spatial data-structure. Here, we give query optimization techniques to bridge this gap between the high-level query language — multivariate Boolean constraints over arbitrary shapes — and the query language supported by existing spatial data-structures — univariate range queries over simple shapes. The optimization has two main steps: First, it approximates multivariate Boolean constraints by a sequence of univariate Boolean constraints. Second, each univariate Boolean constraint is approximated by a range query over a domain over simpler shapes, such as the lattice of bounding boxes. The original query is implemented as an interleaved sequence of these range queries and univariate Boolean constraints. This optimization relies on new results on existential quantifier elimination in Boolean algebras.