Joining interval data in relational databases

ABSTRACT

The increasing use of temporal and spatial data in present-day relational systems necessitates an efficient support of joins on interval-valued attributes. Standard join algorithms do not support those data types adequately, whereas special approaches for interval joins usually require an augmentation of the internal access methods which is not supported by existing relational systems. To overcome these problems we introduce new join algorithms for interval data. Based on the Relational Interval Tree, these algorithms can easily be implemented on top of any relational database system while providing excellent performance on joining intervals. As experimental results on an Oracle9i server show, the new techniques outperform existing relational methods for joining intervals significantly.

REFERENCES

• 1: Chuan-Heng Ang , Kok-Phuang Tan, The interval B-tree, Information Processing Letters, v.53 n.2, p.85-89, Jan. 27, 1995 [doi>10.1016/0020-0190(94)00176-Y]
• 2: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jan Vahrenhold , Jeffrey Scott Vitter, A Unified Approach for Indexed and Non-Indexed Spatial Joins, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.413-429, March 27-31, 2000
• 3: Lars Arge , Octavian Procopiuc , Sridhar Ramaswamy , Torsten Suel , Jeffrey Scott Vitter, Scalable Sweeping-Based Spatial Join, Proceedings of the 24rd International Conference on Very Large Data Bases, p.570-581, August 24-27, 1998
• 4: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 5: Jochen Van den Bercken , Bernhard Seeger, Query Processing Techniques for Multiversion Access Methods, Proceedings of the 22th International Conference on Very Large Data Bases, p.168-179, September 03-06, 1996
• 6: G. Slivinskas, Developing a DataBlade for a New Index, Proceedings of the 15th International Conference on Data Engineering, p.314, March 23-26, 1999
• 7: Christian Böhm , Gerald Klump , Hans-Peter Kriegel, XZ-Ordering: A Space-Filling Curve for Objects with Spatial Extension, Proceedings of the 6th International Symposium on Advances in Spatial Databases, p.75-90, July 20-23, 1999
• 8: Tolga Bozkaya , Z. Meral Özsoyoglu, Indexing Valid Time Intervals, Proceedings of the 9th International Conference on Database and Expert Systems Applications, p.541-550, August 24-28, 1998
• 9: Thomas Brinkhoff , Hans-Peter Kriegel , Bernhard Seeger, Efficient processing of spatial joins using R-trees, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.237-246, May 25-28, 1993, Washington, D.C., United States
• 10: Weidong Chen , Jyh-Herng Chow , You-Chin Fuh , Jean Grandbois , Michelle Jou , Nelson Mendonça Mattos , Brian T. Tran , Yun Wang, High Level Indexing of User-Defined Types, Proceedings of the 25th International Conference on Very Large Data Bases, p.554-564, September 07-10, 1999
• 11: Edelsbrunner H.: A New Approach to Rectangle Intersections. Internat. J. Comput. Math. 13, 1983, 209--229.
• 12: Ramez Elmasri , Gene T. J. Wuu , Yeong-Joon Kim, The Time Index: An Access Structure for Temporal Data, Proceedings of the 16th International Conference on Very Large Data Bases, p.1-12, August 13-16, 1990
• 13: C. Faloutsos , S. Roseman, Fractals for secondary key retrieval, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.247-252, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73746]
• 14: Gao D., Jensen C. S., Snodgrass R. T., Soo M. D.: Join Operations in Temporal Databases. A Time Center Technical Report (TR-71), 2002.
• 15: Himawan Gunadhi , Arie Segev, Query Processing Algorithms for Temporal Intersection Joins, Proceedings of the Seventh International Conference on Data Engineering, p.336-344, April 08-12, 1991
• 16: Oliver Günther, Efficient Computation of Spatial Joins, Proceedings of the Ninth International Conference on Data Engineering, p.50-59, April 19-23, 1993
• 17: Eric N. Hanson , Theodore Johnson, Selection predicate indexing for active databases using interval skip lists, Information Systems, v.21 n.3, p.269-298, May 1996 [doi>10.1016/0306-4379(96)00015-4]
• 18: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations, Proceedings of the 23rd International Conference on Very Large Data Bases, p.396-405, August 25-29, 1997
• 19: IBM Corp.: IBM DB2 Universal Database Administration Guide: Implementation, Ver. 8. Armonk, NY, 2002.
• 20: IBM Corp.: IBM Informix Virtual-Index Interface Programmer's Guide, Ver. 9.4. Armonk, NY, 2003.
• 21: ISO International Standard: Databse Language SQL - Part2: Foundation. 1999.
• 22: ISO International Standard: SQL Multimedia and Application Packages - Part 3: Spatial. 2001.
• 23: Marcel Kornacker, High-Performance Extensible Indexing, Proceedings of the 25th International Conference on Very Large Data Bases, p.699-708, September 07-10, 1999
• 24: Kriegel H.-P., Pfeifle M., Pötke M., Seidl T., Enderle J.: Object-Relational Spatial Indexing. In: Manolopoulos Y., Papadopoulos A., Vassilakopoulos M. (Eds.): Spatial Databases: Technologies, Techniques and Trends. Idea Group Inc., in press.
• 25: Hans-Peter Kriegel , Marco Pötke , Thomas Seidl, Managing Intervals Efficiently in Object-Relational Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.407-418, September 10-14, 2000
• 26: Leung T. Y. C., Muntz R. R.: Stream Processing: Temporal Query Processing and Optimization. In: Tansel A. U., Clifford J., Gadia S. K., Segev A., Snodgrass R. T. (Eds.): Temporal Databases: Theory, Design, and Implementation. Benjamin/Cummings 1993, 329--355.
• 27: Ming-Ling Lo , Chinya V. Ravishankar, Spatial hash-joins, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.247-258, June 04-06, 1996, Montreal, Quebec, Canada
• 28: Hongjun Lu , Beng Chin Ooi , Kian-Lee Tan, On Spatially Partitioned Temporal Join, Proceedings of the 20th International Conference on Very Large Data Bases, p.546-557, September 12-15, 1994
• 29: Oralce Corp.: Oracle9i Data Cartridge Developer's Guide, Rel. 9.2. Redwood City, CA, 2002.
• 30: Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
• 31: Dieter Pfoser , Christian S. Jensen, Incremental Join of Time-Oriented Data, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.232, July 28-30, 1999 [doi>10.1109/SSDM.1999.787639]
• 32: Sridhar Ramaswamy, Efficient Indexing for Constraint and Temporal Databases, Proceedings of the 6th International Conference on Database Theory, p.419-431, January 08-10, 1997
• 33: Satyendra P. Rana , Farshad Fotouhi, Efficient Processing of Time-Joins in Temporal Data Bases, Proceedings of the 3rd International Conference on Database Systems for Advanced Applications (DASFAA), p.427-432, April 06-08, 1993
• 34: Han Shen , Beng Chin Ooi , Hongjun Lu, The TP-Index: A Dynamic and Efficient Indexing Mechanism for Temporal Databases, Proceedings of the Tenth International Conference on Data Engineering, p.274-281, February 14-18, 1994
• 35: Inga Sitzmann , Peter J. Stuckey, Improving Temporal Joins Using Histograms, Proceedings of the 11th International Conference on Database and Expert Systems Applications, p.488-498, September 04-08, 2000
• 36: Daeweon Son , Ramez Elmasri, Efficient Temporal Join Processing Using Time Index, Proceedings of the Eighth International Conference on Scientific and Statistical Database Management, p.252-261, June 18-20, 1996 [doi>10.1109/SSDM.1996.506068]
• 37: Michael D. Soo , Richard Thomas Snodgrass , Christian S. Jensen, Efficient Evaluation of the Valid-Time Natural Join, Proceedings of the Tenth International Conference on Data Engineering, p.282-292, February 14-18, 1994
• 38: Extensible Indexing: a Framework for Integrating Domain-Specific Indexing Schemes into Oracle8i, Proceedings of the 16th International Conference on Data Engineering, p.91, February 28-March 03, 2000
• 39: Michael Stonebraker, Inclusion of New Types in Relational Data Base Systems, Proceedings of the Second International Conference on Data Engineering, p.262-269, February 05-07, 1986
• 40: Chun Zhang , Jeffrey Naughton , David DeWitt , Qiong Luo , Guy Lohman, On supporting containment queries in relational database management systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.425-436, May 21-24, 2001, Santa Barbara, California, United States
• 41: Donghui Zhang , Vassilis J. Tsotras, Index Based Processing of Semi-Restrictive Temporal Joins, Proceedings of the Ninth International Symposium on Temporal Representation and Reasoning (TIME'02), p.70, July 07-09, 2002
• 42: Efficient Temporal Join Processing Using Indices, Proceedings of the 18th International Conference on Data Engineering, p.103, February 26-March 01, 2002