Cardinality-Aware and Purely Relational Implementation of an XQuery Processor

Abstract

Das rasante Wachstum des Einsatzes von XML-Dokumenten als universelles Format zur Speicherung und zum Austausch von Daten im Web führte zur Entwicklung einer Vielzahl von Ansätzen, die es erlauben, XML-Daten effizient speichern und anfragen zu können. Da XQuery sich zur standardisierten XML-Anfragesprache entwickelt hat, wurden besondere Anstrengungen gemacht, um effiziente XQuery-Prozessoren zu konstruieren. Die vorliegende Dissertation beschreibt eine rein-relationale Implementation eines XQuery-Prozessors, der sich auf die etablierte Stabilität und wohlverstandene Optimierungstechniken der Relationalen Datenbanktechnologie stützt, indem XQuery-Ausdrücke in äquivalente SQL-Skripte übersetzt werden. Diese Skripte basieren auf der als "XPath Accelerator" bekannten relationalen XML-Kodierung und können auf jedem herkömmlichen Relationalen Datenbankmanagementsystem ausgeführt werden, ohne daß änderungen am Datenbankkern vorgenommen werden müßten. Der Übersetzungsvorgang führt XQuery-Ausdrücke in einen algebraischen Plan über, der dann in ein äquivalentes SQL-Skript kompiliert wird. Diese Übersetzung wird durch eine Bibliothek von Übersetzungsmustern realisiert. Um kompakte und effizient auswertbare Anfragen generieren zu können, beschreiben wir alternative Ansätze und relationale Optimierungen, die diese Übersetzung von XQuery nach SQL implementieren. Weiterhin beschreibt diese Dissertation eine neue Methode, die die Abschätzung der Kardinalität eines XQuery-Ausdrucks sowie seiner Teilausdrücke erlaubt. Diese Kardinalitätsabschätzungen spielen eine zentrale Rolle im Anfrageoptimierungsprozess. Dazu diskutiert diese Arbeit, wie die dann verfügbare Kardinalitätsinformation als Hinweis für den Anfrageoptimierer des Datenbanksystems genutzt werden kann, um diesen bei der Wahl der besten Ausführungsalternative für die generierten SQL-Skripte zu unterstützen. Die in dieser Arbeit beschriebenen Experimente belegen die Effizienz und Skalierbarkeit dieser rein-relationalen Methode im Vergleich zu nativen XML/XQuery- Datenbanksystemen.