Efficient evaluation of the valid-time natural join

Michael D. Soo, Richard T. Snodgrass, Christian S. Jensen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

59 Scopus citations


Joins are arguably the most important relational operators. Poor implementations are tantamount to computing the Cartesian product of the input relations. In a temporal database, the problem is more acute for two reasons. First, conventional techniques are designed for the optimization of joins with equality predicates, rather than the inequality predicates prevalent in valid-time queries. Second, the presence of temporally-varying data dramatically increases the size of the database. These factors require new techniques to efficiently evaluate valid-time joins. We address this need for efficient join evaluation in databases supporting valid-time. A new temporal-join algorithm based on tuple partitioning is introduced. This algorithm avoids the quadratic cost of nested-loop evaluation methods; it also avoids sorting. Performance comparisons between the partition-based algorithm and other evaluation methods are provided. While we focus on the important valid-time natural join, the techniques presented are also applicable to other valid-time joins.

Original languageEnglish (US)
Title of host publicationProceedings - International Conference on Data Engineering
Editors Anon
PublisherPubl by IEEE
Number of pages11
ISBN (Print)0818654007
StatePublished - 1994
EventProceedings of the 10th International Conference on Data Engineering - Houston, TX, USA
Duration: Feb 14 1994Feb 18 1994

Publication series

NameProceedings - International Conference on Data Engineering


OtherProceedings of the 10th International Conference on Data Engineering
CityHouston, TX, USA

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'Efficient evaluation of the valid-time natural join'. Together they form a unique fingerprint.

Cite this