Spatial query optimization: From boolean constraints to range queries

Richard Helm, Kim Marriott, Martin Odersky

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)197-210
Number of pages14
JournalJournal of Computer and System Sciences
Issue number2
Publication statusPublished - 1 Jan 1995

Cite this