Scheduling Issues in Partitioned Temporal Join

Abstract

One of the major problems of temporal databases is to develop efficient algorithms for operations that involves the time attributes. An operation that has received much attention in recent years is the temporal join which matches records from two temporal relations whose time intervals overlap. Under a partition-based algorithm, temporal data are split into partitions. During the join process, a partition in one relation only needs to join with some, but not all, partitions of the other relation. In this paper, we address scheduling issues in such an algorithm. Depending on the orders in which partitions are read, the number of I/Os incurred varies. We propose a three-phase scheduling framework to minimize the number of I/Os incurred. From the framework, a large number of scheduling strategies can be derived. We also study several representative scheduling strategies and report our findings in this paper.