Lehr- und Forschungseinheit für Datenbanksysteme Datenbanksysteme Database Systems

Diplomarbeit

Entwicklung und Evaluierung von R-Bäumen für objekt-relationale Datenbanksysteme

Inhalt

In den letzten Jahren hat die Verwaltung von räumlich ausgedehnten Objekten in kommerziellen Datenbanksystemen stark an Bedeutung gewonnen. Typische Anwendungsgebiete liegen etwa in der Verwaltung von Zeitintervallen (1D), von geographischen Entitäten (2D) oder von CAD-Geometrien (2D und 3D). Die führenden Datenbank-Hersteller haben inzwischen auf den wachsenden Bedarf an solchen "Non-standard"-Anwendungen reagiert und ihre Produkte um objekt-relationale Funktionen und Komponenten erweitert. Mit Hilfe von "Extensibility Frameworks" ist es nun möglich, eigene komplexe Datentypen und Operatoren inklusive domänenspezifischer Indexstrukturen zu definieren und transparent in den Datenbankserver einzubetten.

Aufgabenstellung

In dieser Diplomarbeit soll eine an die Struktur des R-Baums angelehnte Indexstruktur objekt-relational modelliert und implementiert werden. Das dynamische Verhalten dieser Indexstruktur soll dabei durch stochastische Einfüge- und Splitheuristiken gesteuert werden, welche die physikalische und logische Abstraktion des relationalen Schemas optimal ausnutzen. Dieser "objekt-relationale R-Baum" ist mit gängigen Verfahren wie dem R*-Baum zu vergleichen. Dabei sollen insbesondere Eigenschaften bezüglich der Effizienz von Anfrage- und Update-Operationen und der Anbindung an die Optimizer-Schnittstelle untersucht werden.

Tools

Oracle8i, Explain plan, Tkprof

Personen

Bearbeiter Christian Braun
Betreuer Marco Pötke

Arbeitsplan

Arbeitsabschnitt Zeitbedarf
Erarbeiten einer relationalen Modellierung 1 Woche
Implementierung der R*-Algorithmen für diese Modellierung 2 Wochen
Implementierung und Vergleich verschiedener Anfragealgorithmen 2 Wochen
Entwicklung von stochastischen Algorithmen für Einzeleinfügungen 3 Wochen
Vergleich von R*-Baum und stochastischen Algorithmen 1 Woche
Implementierung und Vergleich verschiedener Clustering-Verfahren 3 Wochen
Entwicklung und Vergleich von Bulkloading-Verfahren 3 Wochen
Implementierung einer Selektivitätsschätzung 2 Wochen
Entwicklung einer statischen höhenbeschränkten Tiefensuche 3 Wochen
Entwicklung einer dynamischen höhenbeschränkten Tiefensuche 2 Wochen

Ergebnis

In dieser Diplomarbeit wurden verschiedene R-Baum-Varianten für das objekt-relationale Datenbanksystem Oracle8i entwickelt und evaluiert.
Zunächst wurde eine relationale Modellierung entwickelt. Dafür wurde eine Kostenfunktion hergeleitet, mit der man die optimale Seitengröße bestimmen kann. Es wurden verschiedene Algorithmen entwickelt, die die Freiheiten der Modellierung ausnutzen:




Homepages:  homeDBS homeInstitut homeLMU
03.06.2000 Christian Braun