Query evaluation and optimization in deductive and object-oriented spatial databases

Wei Lu, Jiawei Han

Research output: Contribution to journalArticlepeer-review


A deductive and object-oriented spatial (DOOS) database system enhances a spatial database system with deductive and object-oriented features. Two major kinds of computations co-exist in a DOOS database system: (1) spatial reasoning based on spatial relationships specified by spatial (deduction) rules, and (2) spatial computation based on computationally intensive geometric algorithms (methods). The impedance mismatch between set-oriented spatial query evaluation and tuple-oriented spatial algorithmic computation poses a major challenge in the implementation of such a system. This study attacks this problem in the following three aspects: (1) deduction rule compilation and high-level, relational and geo-relational algebraic simplification; (2) query plan generation by dynamic connection graph analysis and access path selection; and (3) set-oriented processing of spatial methods. The study presents an integrated view on set-oriented query processing in deductive and object-oriented spatial database systems and leads to a set of spatial query processing and optimization techniques which are useful not only at the processing of deductive and object-oriented spatial queries but also at the possible extensions towards query processing and optimization in other deductive and object-oriented database systems containing both declaratively defined deduction rules and procedurally defined computational routines.

Original languageEnglish (US)
Pages (from-to)131-143
Number of pages13
JournalInformation and Software Technology
Issue number3
StatePublished - 1995
Externally publishedYes


  • deductive and object-oriented databases
  • geographical information systems
  • query optimization
  • query processing
  • set-oriented spatial computation
  • spatial databases

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Computer Science Applications


Dive into the research topics of 'Query evaluation and optimization in deductive and object-oriented spatial databases'. Together they form a unique fingerprint.

Cite this