Scheduling Issues in Partitioned Temporal Join

Jeffrey Xu Yu
Department of Computer Science Australian National University Canberra, ACT 0200, Australia yu@cs.anu.edu.au

Kian-Lee Tan
Dept. of Information Systems & Computer Science National University of Singapore Lower Kent Ridge, Singapore 119260 tankl@iscs.nus.sg

Abstract

The temporal join operation is frequently used in temporal databases to match 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 a few, 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.

Conference Home Page