The join techniques that are assisted by data structures, such as index trees or bitmap indices, might require modification in order to process interval data. B-trees [Bayer, 1972], for example, are designed for indexing atomic data on which a total order is defined. The total order is essential for this indexing method and most other conventional ones, too. However, there is no total ordering among interval data which would enable us to find separating values x such that an interval is either less than or equal to x or greater than x. Unfortunately, one can always find a third type of interval which just overlaps the breakpoint x and is neither less-equal nor greater than x. This makes it impossible in the general case to find a partition (of the time line) that satisfies certain optimality constraints. A lot of index methods, however, rely on such optimal partitions. Consider, for example, the process of balancing a B-tree which effectively means adjusting the original partition (of the indexing attribute's domain) in order to achieve a better balance of the tree.
Elmasri et al. proposed an indexing method, called the time index , which can be used for join processing purposes [Elmasri et al., 1993]. In general, various indexing methods have been proposed for interval timestamps . Further examples can be found in [Kolovson, 1993] and [Gunadhi and Segev, 1993]. They all can be used with the general join algorithm in figure 4.5.
Similarly, the join index based algorithm presented in figure 3.15 works unmodified given that the underlying join index is built upon the temporal intersection condition.
In both cases, the search strategy should be the same and avoid any unsuccessful tuples comparisons and unnecessary retrievals. Figure 4.6 visualises the search strategy for the example that has been employed throughout this chapter.
