On Spatially Partitioned Temporal Join
No Thumbnail Available
Files
Date
1994-01-01T00:00:00Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Temporal relations are relations in temporal database which have one or more attributes whose values vary along the time. The most common representation of time adopted in such databases are the time intervals during which those attributes have specified values. Time join in a temporal database matches tuples from two temporal relations whose time intervals overlap. It is an important but very expensive operation because the volume of temporal data is usually large and the join is a non-equijoin operation in nature. This paper presents a partition-based time join method and its supporting storage structure. Under the proposed method, time intervals in a temporal relations are mapped to points in a two dimensional space. These points are stored in clustered buckets whose addresses can be easily computed with the help of a semi-dynamic directory. When a time join of two relations is to be performed, a bucket in one relation only need to be compared with a determinable set of buckets of the other relation whose addresses can also be efficiently computed. As such, the proposed algorithm outperforms both the nested-loops and sort-merge based time join algorithms. The time-space mapping mechanism, the storage structure, and the join algorithms are discussed. Some results of our preliminary performance study are also provided to show the efficiency of the proposed method.