A foundation for conventional and temporal query optimization addressing duplicates and ordering

Giedrius Slivinskas, Christian S. Jensen, Richard T. Snodgrass

Research output: Contribution to journalConference articlepeer-review

13 Scopus citations


Most real-world databases contain substantial amounts of time-referenced, or temporal, data. Recent advances in temporal query languages show that such database applications may benefit substantially from built-in temporal support in the DBMS. To achieve this, temporal query representation, optimization, and processing mechanisms must be provided. This paper presents a foundation for query optimization that integrates conventional and temporal query optimization and is suitable for both conventional DBMS architectures and ones where the temporal support is obtained via a layer on top of a conventional DBMS. This foundation captures duplicates and ordering for all queries, as well as coalescing for temporal queries, thus generalizing all existing approaches known to the authors. It includes a temporally extended relational algebra to which SQL and temporal SQL queries may be mapped, six types of algebraic equivalences, concrete query transformation rules that obey different equivalences, a procedure for determining which types of transformation rules are applicable for optimizing a query, and a query plan enumeration algorithm. The presented approach partitions the work required by the database implementor to develop a provably correct query optimizer into four stages: The database implementor has to 1) specify operations formally, 2) design and prove correct appropriate transformation rules that satisfy any of the six equivalence types, 3) augment the mechanism that determines when the different types of rules are applicable to ensure that the enumeration algorithm applies the rules correctly, and 4) ensure that the mapping generates a correct initial query plan.

Original languageEnglish (US)
Pages (from-to)21-49
Number of pages29
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number1
StatePublished - Jan 2001
Event16th International Conference on Data Engineering - San Diego, CA, United States
Duration: Feb 29 2000Mar 3 2000


  • Coalescing
  • Duplicate elimination
  • Query optimization
  • Temporal algebra
  • Temporal databases
  • Transformation rules

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'A foundation for conventional and temporal query optimization addressing duplicates and ordering'. Together they form a unique fingerprint.

Cite this