Relational Interval Tree
There is a growing demand for database systems that handle temporal and spatial data. Intervals occur as transaction time and valid time ranges in temporal databases, as line segments on a space-filling curve in spatial applications, as inaccurate measurements with tolerances in engineering databases, for hierarchical type systems in object-oriented databases, or for handling interval and finite domain constraints in declarative systems. Particularly for industrial or commercial applications, the integration into (object-)relational database management systems is essential.
The Relational Interval Tree (RI-tree) is a new method to efficiently support intersection queries, i.e. reporting all intervals from the database that overlap a given query interval. Rather than being a typical external memory data structure, the RI-tree follows a new paradigm in being a relational storage structure. The basic idea is to manage the data objects by common relational indexes rather than to access raw disk blocks directly, thus exploiting the availability, robustness and high performance of built-in index structures in existing systems.