Habilitationen/Dissertationen
KeyX: Selective Key-Oriented Indexing in Native XML Databases
Universität zu Lübeck Institut für Informationssysteme bchammer [at] ifis [dot] uni-luebeck [dot] de Oktober 2005
Die Extensible Markup Language (XML) ist seit einigen Jahren ein weit verbreitetes Standardformat zum Datenaustausch in heterogenen Systemen. XML ist eine universelle Sprache, die unabhängig von Programmiersprachen, Plattformen, Betriebssystemen und Anwendungsdomänen ist. Der verstärkte Einsatz von XML in Web-Applikationen und E-Commerce-Anwendungen erfordert die Anbindung von XML-Technologien an Datenbankmanagementsysteme, da diese einen schnellen, robusten und anwendungsunabhängigen Zugriff auf Daten ermöglichen. In den letzten Jahren wurden viele (objekt-)relationale Datenbankmanagementsysteme um XML-Funktionalitäten erweitert. Im Gegensatz zu diesen so genannten XML enabled database systems wurde das Paradigma des nativen XMLDatenbankmanagementsystems (XDBMS) eingeführt. XDBMS speichern XML-Daten persistent in einer nativen Baumstruktur und vermeiden so teure Transformationen in Tabellen, die bei Datenbanken mit einem relationalen Kern unvermeidbar sind.
In relationalen Datenbanken werden Indizes zur Beschleunigung von häufig wiederkehrenden Anfragen genutzt. Ein Index ist hierbei eine Datenstruktur, die spezifische Anfragen optimal unterstützt und Zugriffe auf die physikalische Datenbankschicht reduziert. Ein unvermeidbarer Seiteneffekt von Indizes ist der Speicherverbrauch und die notwendige Aktualisierung bei Änderungen der Originaldaten. Aus diesem Grund wird nicht jede Spalte einer relationalen Datenbank indiziert.
In relationalen Datenbankmanagementsystemen (RDBMS) sind Indizes gut verstanden und werden tagtäglich eingesetzt, um spezifische und häufig wiederkehrende Anfragen zu beschleunigen. Für die Indizierung von XML-Datenbanken existieren zurzeit noch keine Standardverfahren, sondern verschiedene Ansätze in der wissenschaftlichen Literatur, die oft nur Strukturanfragen zulassen und nur in wenigen Ausnahmen eine Auswahl bezüglich der indizierten Elemente erlauben. Die gängigen XML-Anfragesprachen wie XQuery und XPath nutzen Pfadausdrücke, um innerhalb der XML-Daten zu navigieren. Aus diesem Grund ist die effiziente Ausführung von Pfadausdrücken eine wichtige Aufgabe von XDBMS. Hierbei existieren verschiedene Ansätze, die z.T. nur navigierende Anfragen ohne Wertvergleiche oder ausschließlich Wertanfragen ohne Pfadberücksichtigung unterstützen. So genannte Structural-Summaries, die alle Knoten der XML-Daten in einer zweiten Datenstruktur ablegen, sind nicht selektiv, benötigen viel Speicher und verbessern die Leistung eines Datenbanksystems nicht, wenn häufig Änderungen vorgenommen werden, da jedes Mal die Indexstruktur aktualisiert werden muss.
In dieser Dissertation wird das Konzept von spezifischen Indizes auf native XML-Datenbankmanagementsysteme (XDBMS) übertragen.
Mit KeyX wird ein Indizierungsansatz vorgestellt, der XML-Element- und Attributwerte mit spezifischem Pfad als Schlüssel interpretiert und die dazugehörenden oder benachbarten Knoten im Originaldokument als Rückgabewert referenziert. Da sich Schlüssel und Wert unterscheiden können, entfällt der Aufwand, der für navigierende Pfadverfolgung zwischen beiden benötigt wird. Zu einem Index können zusätzliche strukturelle Bedingungen gestellt werden, die von allen indizierten Elementen erfüllt sein müssen. Dies ermöglicht z.B. das Indizieren von Büchern mit einer ISBNNummer anhand des Buchtitels. Die ISBN ist dabei eine reine strukturelle Bedingung, so dass der konkrete Wert nicht relevant ist.
KeyX erlaubt das Indizieren von Elementen anhand mehrerer Schlüsselwerte, die in einem geschachtelten Baum organisiert werden. Reine Pfadanfragen werden indiziert, indem der gesamte Pfad als Schlüssel interpretiert wird und alle Elemente, die über diesen Pfad erreichbar sind, referenziert. Experimentell bestimmte Ergebnisse der auf einem nativen XDBMS basierenden prototypischen Implementierung zeigen, dass unser Ansatz die Ausführungszeit von Anfragen signifikant beschleunigt.
Die Auswahl von passenden Indizes ist ein wichtiger Prozess beim Anlegen und Optimieren der Datenbank, der meist manuell von einem Administrator oder in relationalen Datenbanken auch (halb-) automatisch von einem Indexauswahl-Tool durchgeführt wird. Dieses Tool analysiert eine Menge von SQL-Operationen, den so genannten Workload, und schlägt eine Menge von Indizes vor, die die Ausführungszeit des Workloads reduziert. In dieser Arbeit wird dieses in der relationalen Welt wohlbekannte Index Selection Problem (ISP) auf XML-Datenbanken übertragen. Das Bestimmen der besten Lösung ist i.Allg. sehr aufwendig, da das ISP ein NP-vollständiges Problem ist, zu dessen Lösung ein deterministischer Algorithmus exponentiell viel Zeit benötigt. Heuristiken, die gute Ergebnisse in wesentlich kürzerer Zeit liefern, wurden implementiert und bewertet. Es wird eine Implementierung präsentiert, die häufige Anfragen erkennt und nutzt, um die Datenbank zu optimieren. Da der Workload periodisch analysiert wird und durch das ISP günstige Indizes automatisch angelegt und ggf. auch wieder aufgelöst werden, garantiert die KeyXImplementierung eine hohe Leistung über die gesamte Lebenszeit der Datenbank. Das Bestimmen von Indizes erfolgt über Kostenmodelle, die die logarithmische Laufzeit einer indexunterstützten Ausführung der linearen Ausführung ohne Index gegenüberstellen. Über eine statistische Zusammenfassung der XMLDaten kann die Anzahl der durch eine Anfrage selektierten Knoten leicht bestimmt werden.
Jeder Index muss aktualisiert werden, wenn die indizierten Daten sich im Original geändert haben. Ein Index, der Bücher anhand ihres Titels indiziert, muss ein neu hinzugekommenes Buch aufnehmen, um konsistent zu sein. In relationalen Datenbanken, wo ein Index auf einer Tabelle und einer oder mehreren Spalten definiert wird, ist es ein triviales Problem, zu erkennen, ob eine SQL-Anweisung einen Wert einer solchen Spalte ändert oder nicht. In strukturierten XML-Daten ist dieses Problem nicht so einfach zu entscheiden. Durch Platzhalter und bereichsübergreifende Pfadausdrücke ist es möglich, einen Knoten zu selektieren, der im Pfadausdruck nicht explizit aufgeführt wird. Für dieses Problem wird in der Arbeit ein auf endlichen Automaten basierender Algorithmus vorgestellt, der entscheidet, ob der Schnitt zweier XPath-Ausdrücke leer ist oder nicht. Hierbei wird angenommen, dass ein XPath-Ausdruck p den Index definiert, während ein zweiter XPath-Ausdruck p' Teil der modifizierenden Datenbankoperation ist. Ist der Schnitt von p und p' nicht leer, so ist der Index betroffen und muss aktualisiert werden, da beide Anfragen mindestens einen gemeinsamen Knoten auswählen. Die Entscheidung bezüglich des Schnitts wird ohne Rückgriff auf die Daten in der XML-Datenbank nur anhand der Anfragen p und p' durchgeführt, was deutlich effizienter ist, da die Größe der indizierten Daten nicht die Laufzeit des Algorithmus beeinflusst.
Der für XPath-Ausdrücke ohne Negation effiziente Algorithmus bekommt eine exponentielle Laufzeit, sobald die Negation in XPath-Ausdrücken erlaubt ist. Diese geringfügige Änderung des Aufbaus von Path-Ausdrücken führt zu einem NP-vollständigen Entscheidungsproblem. Dieses wird durch eine Reduktion des Erfüllbarkeitsproblems boolescher Formeln (3SAT) auf das Schnittproblem mit Negation bewiesen. Zeitmessungen haben jedoch ergeben, dass eine akzeptable Ausführungszeit für realistische Datenbankanwendungen mit Pfadausdrücken bis zu 100 Bedingungen gegeben ist.
Dissertation als Volltext herunterladen*
* Zum Ansehen benötigen Sie mindestens den Acrobat-Reader 5.0. Den aktuellen Acrobat-Reader bekommen Sie unter www.adobe.de/products/acrobat/
