Lehr- und Forschungseinheit für Datenbanksysteme Datenbanksysteme boeing company


High resolution indexing for CAD databases


The management of complex spatial objects in many non-standard database applications, such as computer-aided design (CAD), imposes new requirements on spatial database systems, in particular on efficient query processing. In the past two decades various index structures have been proposed to support this process. Recently, there has been an increasing awareness that it is indispensable to integrate these index structures into fully-fledged database systems.
In this master thesis a new spatial index is introduced, which supports the intersect predicate on a data type TSpatialObject. This new access method, called X-RI-tree, can easily be implemented on top of an object-relational database management system, exploiting its extensible indexing framework. Thus, fundamental services of underlying commercial database systems can be fully reused, including transactions, concurrency control, and recovery.
The X-RI-tree is a multi step index for grey interval sequences, which can be generated out of spatial objects via space filling curves. Each of these grey intervals consists of an interval hull, aggregated information of the grey interval, and a detailed attached black interval sequence. This structure is reflected in the query process, which is based on three consecutive filter steps. In a first filter step, all overlapping pairs of grey database and query intervals are determined, by means of a slightly altered RI-tree. In a second filter step a so called fast grey test is used to determine intersecting intervals without examining the attached interval sequences. In a last third filter step, an expensive BLOB test is carried out, scrutinizing the attached interval sequences.


Both the RI-tree and the X-RI-tree were implemented on top of an Oracle Server Release 8.1.7, using PL/SQL for the computational main memory based programming.
The experimental evaluation of a well parameterized X-RI-tree, compared to the optimized version of the RI-tree, can be summarized as follows:



Bearbeiter Martin Pfeifle
Betreuer Dr. Thomas Seidl, Dr. Marco Pötke


paper (pdf 2.047 KB)
talk (ppt 1.269 KB)

Homepages: homeDBShomeInstituthomeLMU
21.02.2001, Marco Pötke