Login
- Originaltitel:
- Pathfinder: XQuery Compilation Techniques for Relational Database Targets
- Übersetzter Titel:
- Pathfinder: XQuery-Übersetzungstechniken für relationale Datenbankbackends
- Autor:
- Teubner, Jens Thilo
- Jahr:
- 2006
- Dokumenttyp:
- Dissertation
- Fakultät/School:
- Fakultät für Informatik
- Betreuer:
- Grust, Torsten (Prof. Dr.)
- Gutachter:
- Grust, Torsten (Prof. Dr.); Kersten, Martin (Prof. Dr.)
- Format:
- Text
- Sprache:
- en
- Fachgebiet:
- DAT Datenverarbeitung, Informatik
- Stichworte:
- XQuery; RDBMS; Compiler; XPath Accelerator; Staircase Join; Loop-Lifting
- Übersetzte Stichworte:
- XQuery; RDBMS; Übersetzer; XPath Accelerator; Staircase Join; Loop-Lifting
- Kurzfassung:
- Even after at least a decade of work on XML and semi-structured information, such data is still predominantly processed in main-memory, which obviously leads to significant constraints for growing XML document sizes.
On the other hand, mature database technologies are readily available to handle vast amounts of data easily. The most efficient ones, relational database management systems (RDBMSs), however, are largely locked-in to the processing of very regular, table-shaped data only. In this thesis, we will unleash the power of relational database technology to the domain of semi-structured data, the world of XML. We will present a purely relational XQuery processor that handles huge amounts of XML data in an efficient and scalable manner.
Our setup is based on a relational tree encoding. The XPath accelerator, also known as pre/post numbering, has since become a widely accepted means to efficiently store XML data in a relational system. Yet, it has turned out that there is additional performance to gain. A close look into the encoding itself and the deliberate choice of relational indexes will give intriguing insights into the efficient access to node-based tree encodings.
The backbone of XML query processing, the access to XML document regions in terms of XPath tree navigation, becomes particularly efficient if the database system is equipped with enhanced, tree-aware algorithms. We will devise staircase join, a novel join operator that encapsulates knowledge on the underlying tree encoding to provide efficient support for XPath navigation primitives. The required changes to the DBMS kernel remain remarkably small: staircase join integrates well with existing features of relational systems and comes at the cost of adding a single join operator only. The impact on performance, however, is significant: we observed speedups of several orders of magnitude on large-scale XML instances.
Although existing XQuery processors make use of the resulting XPath performance gain by evaluating XPath navigation steps in the DBMS back-end, they tend to perform other core XQuery operations outside the relational database kernel. Most notably this affects the FLWOR iteration primitive, XQuery's node construction facilities, and the dynamic type semantics of XQuery. The loop-lifting technique we present in this work deals with these aspects in a purely relational fashion. The outcome is a loop-lifting compiler that translates arbitrary XQuery expressions into a single relational query plan. Generated plans take particular advantage of the operations that relational databases know how to perform best: relational joins as well as the computation of aggregates.
The MonetDB/XQuery system to which this thesis has contributed provides the experimental proof of the effectiveness of our approach. MonetDB/XQuery is one of the fastest and most scalable XQuery engines available today and handles queries in the multi-gigabyte range in interactive time. The key to this performance are the techniques described in this thesis. They form the basis for MonetDB/XQuery's core component: the XQuery compiler Pathfinder. - Übersetzte Kurzfassung:
- Obwohl XML als semi-strukturiertes Datenformat bereits seit Jahren in der Informatik etabliert ist, werden in der Praxis noch überwiegend hauptspeicherbasierte Techniken zur Verarbeitung von XML eingesetzt. Angesichts ständig anwachsender Datenmengen entsteht dadurch offensichtlich ein Performanzengpass.
Gleichzeitig stehen in der Datenbankwelt ausgereifte Technologien zur Verfügung, mit denen auch große Datenmengen effizient verarbeitet werden können. Die effizientesten Repräsentanten, relationale Datenbankmanagementsysteme (RDBMSs), sind jedoch auf die Verarbeitung sehr regulärer, tabellenstrukturierter Daten beschränkt. In dieser Arbeit werden die Stärken dieser Systeme dazu genutzt, auch semi-strukturierte Informationen im XML-Format effizient zu verarbeiten. Es wird ein XQuery-Prozessor vorgestellt, der ausschließlich mit Hilfe relationaler Techniken auch große Mengen an XML-Daten effizient und skalierbar handhaben kann.
Grundlage für diesen Prozessor ist ein relationales Kodierungsverfahren für XML-Bäume. Die XPath Accelerator-Technik (auch bekannt als pre/post-Nummerierung), hat sich zwischenzeitlich als effektive Möglichkeit zur XML-Datenspeicherung etabliert. Dennoch zeigt sich, dass durch geschicktes Ausnutzen einiger Eigenschaften des Kodierungsverfahrens sowie durch die Auswahl geeigneter relationaler Indexstrukturen die Performanz des Systems noch weiter verbessert werden kann.
Das Rückgrat datenbankgestützter XML-Verarbeitung, der Zugriff auf XML-Baumstrukturen mittels XPath, lässt sich dann besonders effizient durchführen, wenn das Datenbanksystem mit geeigneten Algorithmen angereichert wird, deren Implementation Kenntnis über die zugrunde liegenden Baumstrukturen aufweist. Staircase Join ist ein neuer Joinoperator, der solches Wissen kapselt und zur effizienten XPath-Auswertung nutzt. Die notwendigen Änderungen am Datenbankkern sind dabei bemerkenswert gering: Staircase Join fügt sich nahtlos in bestehende Datenbankfunktionalität ein und erfordert lediglich das Hinzufügen eines einzelnen Joinoperators. Demgegenüber steht eine Performanzsteigerung durch Staircase Join um mehrere Größenordnungen.
Obwohl auch einige bestehende XQuery-Prozessoren zur XPath-Auswertung auf effiziente Datenbank-Backends zurückgreifen, verarbeiten diese Systeme darüber hinausgehende XQuery-Operationen überwiegend außerhalb des Datenbankkerns. In erster Linie betrifft das die Auswertung des FLWOR-Iterationskonstrukts, der Knotenkonstruktoren, sowie die dynamische Typsemantik von XQuery. Die loop-lifting-Technik, die wir in dieser Arbeit vorstellen, behandelt diese Konstrukte auf konsequent relationale Weise. Das Ergebnis ist ein Übersetzer, der beliebige XQuery-Ausdrücke in einen einzigen Aufruf an die relationale Datenbank übersetzt. Die generierten Pläne stützen sich dabei auf Primitive, die von relationalen Systemen besonders effizient implementiert werden: relationale Joins und die Berechnung von Aggregaten.
Als experimentelle Plattform dieser Arbeit bestätigt das MonetDB/XQuery-System die praktische Nutzbarkeit der vorgestellten Techniken. Das System ist zur Zeit einer der schnellsten und skalierbarsten XQuery-Prozessoren, und ist in der Lage, Anfragen im Multi-Gigabytebereich interaktiv zu beantworten. Der Schlüssel zu dieser Performanz liegt in den Techniken, die in dieser Arbeit vorgestellt werden. Sie bilden die Grundlage für den Kernbestandteil des MonetDB/XQuery-Systems: den XQuery-Übersetzer Pathfinder. - Veröffentlichung:
- Universitätsbibliothek der Technischen Universität München
- WWW:
- https://mediatum.ub.tum.de/?id=601772
- Eingereicht am:
- 10.05.2006
- Mündliche Prüfung:
- 23.10.2006
- Dateigröße:
- 1293415 bytes
- Seiten:
- 177
- Urn (Zitierfähige URL):
- https://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss20061115-0920351297
- Letzte Änderung:
- 15.11.2006
BibTeX