Efficiently processing queries on interval-and-value tuples in relational databases

ABSTRACT

With the increasing occurrence of temporal and spatial data in present-day database applications, the interval data type is adopted by more and more database systems. For an efficient support of queries that contain selections on interval attributes as well as simple-valued attributes (e.g. numbers, strings) at the same time, special index structures are required supporting both types of predicates in combination. Based on the Relational Interval Tree, we present various indexing schemes that support such combined queries and can be integrated in relational database systems with minimum effort. Experiments on different query types show superior performance for the new techniques in comparison to competing access methods.

References

1. Beckmann N., Kriegel H.-P., Schneider R., Seeger B.: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conf. 1990: 322--331.]]
2. Bentley J. L.: Algorithms for Klee's Rectangle Problems. Computer Science Department, Carnegie-Mellon University, Pittsburgh (1977).]]
3. Blankenagel G., Güting R. H.: External Segment Trees. Algorithmica 12(6): 498--532 (1994).]]
4. Böhm C., Klump G., Kriegel H.-P.: XZ-Ordering: A Space-Filling Curve for Objects with Spatial Extension. SSD 1999: 75--90.]]
5. Brochhaus, C., Enderle J., Schlosser A., Seidl T., Stolze K.: Integrating the Relational Interval Tree into IBM's DB2 Universal Database Server. BTW 2005:67--86.]]
6. Clifford J., Dyreson C. E., Isakowitz T., Jensen C. S., Snodgrass R. T.: On the Semantics of "Now" in Databases. ACM Trans. Database Syst. 22(2): 171--214 (1997).]]
7. Edelsbrunner H.: A New Approach to Rectangle Intersections, parts I and II. Internat. J. Comput. Math., 13:209--229, 1983.]]
8. Elmasri R., Wuu G. T. J., Kim Y.-J.: The Time Index: An Access Structure for Temporal Data. VLDB 1990: 1--12.]]
9. Enderle J., Hampel M., Seidl T.: Joining Interval Data in Relational Databases. SIGMOD Conf. 2004: 683--694.]]
10. Faloutsos C., Rong Y.: DOT: A Spatial Access Method Using Fractals. ICDE 1991: 152--159.]]
11. Faloutsos C., Roseman S.: Fractals for Secondary Key Retrieval. PODS 1989: 247--252.]]
12. Gao D., Kline N., Soo M. D., Dunn J.: TIME-IT: The Time Integrated Testbed, version 1.1. Available on ftp.cs.arizona.edu August 2002.]]
13. Goh C. H., Lu H., Ooi B. C., Tan K.-L.: Indexing Temporal Data Using Existing B+-Trees. Data Knowl. Eng. 18(2): 147--165 (1996).]]
14. Gunadhi H., Segev A.: Efficient Indexing Methods for Temporal Relations. IEEE Trans. Knowl. Data Eng. 5(3): 496--509 (1993).]]
15. Guttman A.: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conf. 1984: 47--57.]]
16. ISO/IEC 9075-2:2003: Information Technology -- Database Languages - SQL - Part 2: Foundation (SQL/Foundation), 2003.]]
17. Jagadish H. V.: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conf. 1990: 332--342.]]
18. Kanellakis P. C., Ramaswamy S., Vengroff D. E., Vitter J. S.: Indexing for Data Models with Constraints and Classes. PODS 1993: 233--243.]]
19. Kolovson C. P., Stonebraker M.: Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data. SIGMOD Conf. 1991: 138--147.]]
20. 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., 2004.]]
21. Kriegel H.-P., Pötke M., Seidl T.: Interval Sequences: An Object-Relational Approach to Manage Spatial Data. SSTD 2001: 481--501.]]
22. Kriegel H.-P., Pötke M., Seidl T.: Managing Intervals Efficiently in Object-Relational Databases. VLDB 2000: 407--418.]]
23. Kriegel H.-P., Pötke M., Seidl T.: Object-Relational Indexing for General Interval Relationships. SSTD 2001: 522--542.]]
24. Lawder J. K., King P. J. H.: Querying Multi-dimensional Data Indexed Using the Hilbert Spacefilling Curve. SIGMOD Record 30(1): 19--24 (2001).]]
25. Lawder J. K., King P. J. H.: Using Space-Filling Curves for Multi-dimensional Indexing. BNCOD 2000: 20--35.]]
26. Ramaswamy S.: Efficient Indexing for Constraint and Temporal Databases. ICDT 1997: 419--431.]]
27. Robinson J. T.: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conf. 1981: 10--18.]]
28. Salzberg B., Tsotras V. J.: Comparison of Access Methods for Time-Evolving Data. ACM Comput. Surv. 31(2): 158--221 (1999).]]
29. Sellis T. K., Roussopoulos N., Faloutsos C.: The R+ - Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507--518.]]
30. Snodgrass R. T., Ahn I.: A Taxonomy of Time in Databases. SIGMOD Conf. 1985: 236--246.]]

Index Terms

• Information systems

  • Data management systems

    • Database design and models

      • Relational database model

    • Database management system engines

      • Database query processing

    • Query languages

      • Relational database query languages

  • Information retrieval

    • Document representation

    • Search engine architectures and scalability

      • Search engine indexing

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)