Efficient Interval Management Using Object-Relational Database Servers

User-defined data types such as intervals require

specialized access methods to be efficiently searched and

queried. As database implementors cannot provide appropriate

index structures and query processing methods for each

conceivable data type, present-day object-relational database

systems offer extensible indexing frameworks that enable

developers to extend the set of built-in index structures by

custom access methods. Although these frameworks permit

a seamless integration of user-defined indexing techniques

into query processing they do not facilitate the actual implementation

of the access method itself. In order to leverage

the applicability of indexing frameworks, relational access

methods such as the Relational Interval Tree (RI-tree),

an efficient index structure to process interval intersection

queries, mainly rely on the functionality, robustness and performance

of built-in indexes, thus simplifying the index implementation

significantly. To investigate the behavior and

performance of the recently released IBM DB2 indexing

framework we use this interface to integrate the RI-tree into

the DB2 server. The standard implementation of the RI-tree,

however, does not fit to the narrow corset of the DB2 framework

which is restricted to the use of a single index only.We

therefore present our adaptation of the original two-tree technique

to the single index constraint as well as an approximate

adaptation which conceptually only needs a single index. As

experimental results with interval intersection queries show,

the plugged-in accessmethods deliver excellent performance

compared to other techniques.


Authors: Brochhaus C., Enderle J., Schlosser A., Seidl T., Stolze K.
Published in: In Informatik - Forschung und Entwicklung (IFE) 20(3)
Publisher: Springer - Heidelberg,Germany
Sprache: EN
Jahr: 2005

ISSN: 0178-3564 (Paper), 0949-2925 (Online); DOI: 10.1007/s00450-005-0207-7

Seiten: 121-137
ISSN: 0178-3564
URL:IFE journal link
Typ: Zeitschriftenartikel
Forschungsgebiet: Fast Access to Complex Data