Managing Intervals Efficiently in Object-Relational Databases

Modern database applications show a growing demand for efficient and dynamic management of intervals, particularly for temporal and spatial data or for constraint handling. Common approaches require the augmentation of index structures which, however, is not supported by existing relational database systems. By design, the new Relational Interval Tree1 (RI-tree) employs built-in indexes on an as-they-are basis and is easy to implement. Whereas the functionality and efficiency of the RI-tree is supported by any off-the-shelf relational DBMS, it is perfectly encapsulated by the object-relational data model. The RI-tree requires O(n/b) disk blocks of size b to store n intervals, O(logbn) I/O operations for insertion or deletion, and O(h · logbn + r/b) I/Os for an intersection query producing r results. The height h of the virtual backbone tree corresponds to the current expansion and granularity of the data space but does not depend on n. As demonstrated by our experimental evaluation on an Oracle8i server, competing dynamic interval access methods are outperformed by factors of up to 42 for disk accesses and 4.9 for query response time.

Authors: Kriegel H.-P., Pötke M., Seidl T.
Published in: Proc. 26th Int. Conf. on Very Large Data Bases (VLDB 2000), Cairo, Egypt
Publisher: Morgan Kaufmann
Sprache: EN
Jahr: 2000
Seiten: 407-418
ISBN: 1-55860-715-3
Konferenz: VLDB
URL:Demo RI-Tree
Typ: Tagungsbeiträge
Forschungsgebiet: Fast Access to Complex Data