In this thesis, we investigate and elaborate mechanisms to optimise partitioned temporal join processing. To that end, we have to consider the problem of tuple replication and investigate how near-optimal partitions can be derived. As optimal partitions might only be found by an exhaustive or at least a very expensive search, we therefore have to investigate whether this is really the case, and thus to analyse the complexity of the problem. Once this has been established, we have to look for heuristics for efficiently finding near-optimal partitions for temporal join processing.
In this thesis, we focus on the intersection of intervals as the principal temporal join condition (see previous example). Many other temporal join conditions, such as an interval being contained in an other interval, are specialisations of this intersection condition. These specialisations allow several performance enhancing optimisation, e.g. the restriction of tuple replication to a certain subset of the participating relations [Leung and Muntz, 1992]. However, many of them still suffer from the same problems as the more general intersection join. In most cases, such as the various types of overlap joins, the contain join and the during join, for example, tuple replication cannot totally be abandoned despite being restricted to only one of the participating relations. Partitioned processing of theses joins can therefore still benefit from the optimisations that we propose. In order to provide a clear distinction between the optimisations that can be based on the more specialised join condition and the optimisations that are applicable to all intersection joins we focus on the intersection join condition and regard our work as complementary to that by Leung and Muntz.
In this thesis, we consider join predicates that involve the intervals associated with the tuples. There might be other, non-interval attributes involved. However, we want to investigate the possibilities arising from partitioning over the interval attributes and therefore concentrate on them, thereby ignoring the parts of the join predicate that are not relevant for partitioning. This also helps to distinguish between optimisation and partitioning methods that are available for predicates over atomic attributes - such methods have already been the focus of a large numbers of papers - and those involving interval attributes - these are investigated in the context of this thesis as they have not found any attention yet. In the future, one will need to investigate the tradeoff between these two sets of techniques in order to provide a query optimiser with a guideline of how to choose the most appropriate and efficient technique. However, developing such a guideline here in the context of interval partitioning, however, would go beyond the scope of a single thesis.
