Join operations in temporal databases - Aalborg Universitet.pdf

VLDB Journal (2003) / Digital Object Identifier (DOI) 10.1007/s00778-003-0111-3 Join operations in temporal databases 1 2 1 3 Dengfeng Gao , Christian S. Jensen , Richard T. Snodgrass , Michael D. Soo 1 Computer Science Department, P.O. Box 210077, University of Arizona, Tucson, AZ 85721-0077, USA e-mail: {dgao,rt }@ 2 Department of Computer Science, Aalborg University, Fredrik Bajer sVej 7E, 9220 Aalborg Ø, Denmark e-mail: csj@cs.auc.dk 3 A, Seattle; e-mail: soo@ Edited by T. Sellis. Received: October 17, 2002 / Accepted: July 26, 2003 c Published online: October 28, 2003 – Springer-Verlag 2003 Abstract. Join sare arguably the most important relational languages, recent attention ha sbeen on implementation- operators. Poor implementation sare tantamount to comput- related i ues, most notably indexing and query proce ing ing the Cartesian product of the input relations. In a temporal strategies. In thi spaper, we consider an important subproblem database, the problem i smore acute for two reasons. First, con- of temporal query proce ing, the evaluation ad hoc temporal ventional technique sare designed for the evaluation of join join operations, i.e., join operation sfor which indexing or sec- with equality predicate srather than the inequality predicate ondary acce path sare not available or appropriate. Temporal prevalent in valid-time queries. Second, the presence of tempo- indexing, which ha sbeen a prolific research area in it sown rally varying data dramatically increase sthe size of a database. right [44], and query evaluation algorithm sthat exploit such These factor sindicate that specialized technique sare needed temporal indexe sare beyond the scope of thi spaper. to effic