Spatial query optimization

From boolean constraints to range queries

Richard Helm, Kim Marriott, Martin Odersky

Research output: Contribution to journalArticleResearchpeer-review

7 Citations (Scopus)

Abstract

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
Volume51
Issue number2
DOIs
Publication statusPublished - 1 Jan 1995

Cite this

@article{32affdd1e984435a91b0802d02c72a34,
title = "Spatial query optimization: From boolean constraints to range queries",
abstract = "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.",
author = "Richard Helm and Kim Marriott and Martin Odersky",
year = "1995",
month = "1",
day = "1",
doi = "10.1006/jcss.1995.1061",
language = "English",
volume = "51",
pages = "197--210",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Elsevier",
number = "2",

}

Spatial query optimization : From boolean constraints to range queries. / Helm, Richard; Marriott, Kim; Odersky, Martin.

In: Journal of Computer and System Sciences, Vol. 51, No. 2, 01.01.1995, p. 197-210.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Spatial query optimization

T2 - From boolean constraints to range queries

AU - Helm, Richard

AU - Marriott, Kim

AU - Odersky, Martin

PY - 1995/1/1

Y1 - 1995/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0029394312&partnerID=8YFLogxK

U2 - 10.1006/jcss.1995.1061

DO - 10.1006/jcss.1995.1061

M3 - Article

VL - 51

SP - 197

EP - 210

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 2

ER -