In this section, many of the issues and results that have been discussed in the previous chapters and sections are brought together. We will look at temporal join algorithms that are not based on explicit partitioning , i.e. algorithms that do not contain an explicit partitioning stage as an integral part. This group of algorithms comprises nested-loop joins (with no partitioning stage), sort-merge joins (with an implicit partitioning stage) and index joins (using precomputed partitioning). Figure 4.1 illustrates these three techniques within the hierarchy of section 3.6. In chapter 3, we discussed these techniques in the light of processing equi-joins. In this section, we look at them for processing temporal joins.
As we can expect from the issues presented in section 3.4, it is only the sort-merge approach that needs some minor modifications. The general idea, however, remains unchanged. Nested-loops and join indices do not require any change. Nevertheless, temporal join conditions imply increased join selection ratios in general. This means that join results are larger in comparison to equi-joins between equally sized relations. Or put differently: a bigger share of the cartesian product participates in the temporal join result. This, however, might influence the choice of algorithm as we have already indicated in chapter 3.
In the following discussions, we will concentrate on the temporal intersection join whenever the type of the temporal join is relevant. As we mentioned in section 4.1, the intersection join can be considered as a supertype of most temporal joins. Algorithms for the more specialised temporal joins can be derived from the intersection join algorithms.
