In the previous chapter, join processing has been discussed in a very general context although there was an emphasis on equi-joins as the most frequently used join type. In this chapter, we want to focus on temporal joins.
Temporal joins have an impact on many of the aspects that were discussed in chapter 3. Consequently, many of the techniques that were designed and used for processing equi-joins are not directly applicable to temporal joins if a reasonable performance is required. In this chapter, we point to the differences, present adaptations for sequential temporal join processing that were presented in the literature, and propose improvements.
The issues discussed in this chapter are similar to those of chapter 3: Section 4.1 defines the temporal join operation and introduces a classification scheme for temporal join conditions. Here, the temporal intersection join is identified as a supertype of most other temporal joins. In section 4.2, we discuss the significance of the temporal join operation. Sections 4.3 and 4.4 present temporal join processing techniques. The discussion is divided into non-explicit partitioning (section 4.3) and explicit partitioning techniques (section 4.4). The first set of algorithms are straightforward adaptions of the corresponding equi-join techniques Here, modifications are only minor. Explicit partitioning algorithms, however, require certain parts of the relations to be replicated. This introduces an overhead in various ways. In section 4.4, we present techniques which reduce the overhead. Some of these have been proposed in the literature, some of them are new. In section 4.5, we conduct a simple comparison of temporal join algorithms. This allows us to summarise the most important features. Finally, in section 4.6, we focus on optimisation problems that are specific to temporal join processing.