PhD Thesis, November 1997, Department of Computer Science, University of Edinburgh
This work is divided into two parts. First, we analyse techniques that have been proposed for equi-joins. Some of them have already been adapted for temporal join processing by other authors. However, hash-based and parallel techniques -- which are usually the most efficient ones in the context of equi-joins -- have only found little attraction and leave several temporal-specific issues unresolved. Hash-based and parallel techniques are based on explicit symmetric partitioning. In the case of an equi-join condition, partitioning can guarantee that the relations are split into disjoint fragments; in the case of a temporal intersection condition, partitioning usually results in non-disjoint fragments with a large number of tuples being replicated between fragments. This causes a considerable overhead for partitioned temporal join processing. This problem is an instance of the `min-max dilemma': minimising the number of replicated tuples means minimising the number of fragments, thus minimising the degree of parallelism -- however, increasing the number of fragments and therefore the degree of parallelism also increases the number of tuple replications. We analyse this problem and show that there is an algorithm of polynomial time complexity that computes an optimal solution for the interval partitioning problem (IP). This result concludes the analytical part.
In the second, the synthetical part of this work, we focus on the conclusions that can be drawn from the results of the first part. We propose an optimisation process that
Keywords: temporal join, parallel join, hash join, interval partitioning, temporal databases, parallel databases, data warehousing
Back to the PhD thesis index page
Thomas Zurek, mail to <tz@dcs.ed.ac.uk>, last change 26.11.97