|
An Algebraic Approach to XQuery Optimization
May, Norman
|
URL:
|
https://ub-madoc.bib.uni-mannheim.de/1784
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-17849
|
|
Document Type:
|
Doctoral dissertation
|
|
Year of publication:
|
2007
|
|
The title of a journal, publication series:
|
None
|
|
Publishing house:
|
Universität Mannheim
|
|
Evaluator:
|
Moerkotte, Guido
|
|
Date of oral examination:
|
29 November 2007
|
|
Publication language:
|
English
|
|
Institution:
|
School of Business Informatics and Mathematics > Practical Computer Science III (Moerkotte 1996-)
|
|
Subject:
|
004 Computer science, internet
|
|
Classification:
|
CCS:
H.2.4 ,
|
|
Subject headings (SWD):
|
XML , Datenbanksystem , Abfrageverarbeitung , Implementierung , Optimierung
|
|
Individual keywords (German):
|
XQuery , geschachtelte Anfragen , Anfrageentschachtlung
|
|
Keywords (English):
|
XQuery , nested queries , query decorrelation
|
|
Abstract:
|
As more data is stored in XML and more applications need to process this data, XML query optimization becomes performance critical. While optimization techniques for relational databases have been developed over the last thirty years, the optimization of XML queries poses new challenges. Query optimizers for XQuery, the standard query language for XML data, need to consider both document order and sequence order. Nevertheless, algebraic optimization proved powerful in query optimizers in relational and object oriented databases. Thus, this dissertation presents an algebraic approach to XQuery optimization. In this thesis, an algebra over sequences is presented that allows for a simple translation of XQuery into this algebra. The formal definitions of the operators in this algebra allow us to reason formally about algebraic optimizations. This thesis leverages the power of this formalism when unnesting nested XQuery expressions. In almost all cases unnesting nested queries in XQuery reduces query execution times from hours to seconds or milliseconds. Moreover, this dissertation presents three basic algebraic patterns of nested queries. For every basic pattern a decision tree is developed to select the most effective unnesting equivalence for a given query. Query unnesting extends the search space that can be considered during cost-based optimization of XQuery. As a result, substantially more efficient query execution plans may be detected. This thesis presents two more important cases where the number of plan alternatives leads to substantially shorter query execution times: join ordering and reordering location steps in path expressions. Our algebraic framework detects cases where document order or sequence order is destroyed. However, state-of-the-art techniques for order optimization in cost-based query optimizers have efficient mechanisms to repair order in these cases. The results obtained for query unnesting and cost-based optimization of XQuery underline the need for an algebraic approach to XQuery optimization for efficient XML query processing. Moreover, they are applicable to optimization in relational databases where order semantics are considered.
|
|
Translation of the title:
|
Ein algebraischer Ansatz zur Optimierung von XQuery
(German)
|
|
Translation of the abstract:
|
Mit der zunehmenden Verbreitung von XML-Daten und XML -Anwendungen wird es wichtiger, XML-Anfragen effizient auszuwerten. Während in den letzten dreißig Jahren eine Reihe von Optimierungstechniken für relationale Datenbanken entwickelt wurden, müssen bei der Optimierung von XML-Anfragen neue Herausforderungen gelöst werden. Insbesondere müssen Optimierer für XQuery, die Standardanfragesprache für XML, sowohl die Dokumentreihenfolge als auch die Sequenzreihenfolge beachten. Andererseits haben sich algebraische Optimierungen in relationalen Datenbanken als flexibel und leistungsfähig erwiesen. Daher wird in dieser Dissertation ein algebraischer Ansatz für die Optimierung von XQuery-Anfragen entwickelt, der eine einfache Übersetzung von XQuery in diese Algebra ermöglicht. Basierend auf der formalen Definition der algebraischen Operatoren werden Eigenschaften der Algebra formal bewiesen. In dieser Arbeit nutzen wir die Algebra, um algebraische Äquivalenzen für das Entschachteln geschachtelter XQuery-Anfragen zu entwickeln. Nach der Entschachtlung der Anfragen werden nahezu alle Anfragen in Sekunden oder Millisekunden ausgewertet, während die ursprüngliche geschachtelte Anfrage oft mehrere Stunden für die Auswertung benötigt. In dieser Dissertation werden drei Grundmuster für algebraische Äquivalenzen identifiziert. Für die Auswahl der effektivsten Entschachtlungsäquivalenz wird für jedes dieser Grundmuster ein Entscheidungsbaum entwickelt. Ein weiteres wichtiges Ergebnis der Anfrageentschachtlung besteht darin, dass in der darauf folgenden kostenbasierten Optimierung mehr alternative Pläne, und vor allem meist auch schneller auswertbare Pläne, generiert werden können. In dieser Arbeit werden zwei weitere Fälle präsentiert, in denen der Suchraum für alternative Pläne erweitert werden muß, um effiziente Auswertungspläne zu generieren: das Umordnen von Joins und von Location Steps in Pfadausdrücken. Das in dieser Arbeit vorgestellte algebraische Rahmenwerk erkennt alle Fälle, in denen bei der Umordnung dieser Operationen die Ordnungssemantik von XQuery verletzt wird. Allerdings ermöglichen es aktuelle Ansätze zur Optimierung der Reihenfolge in Anfragen, effizient die korrekte Reihenfolge wieder herzustellen. Der in dieser Dissertation vorgestellte Ansatz zur algebraischen Optimierung von XQuery stellt somit einen wesentlichen Baustein für die effiziente Auswertung von XML-Anfragen dar. Darüberhinaus profitiert auch Anfrageauswertung in relationalen Datenbanken von diesen Techniken, wenn die Reihenfolge bei der Optimierung berücksichtigt werden muss.
(German)
|
|
Additional information:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Search Authors in
BASE:
May, Norman
Google Scholar:
May, Norman
You have found an error? Please let us know about your desired correction here: E-Mail
Actions (login required)
 |
Show item |
|
![[img]](https://madoc.bib.uni-mannheim.de/style/images/fileicons/application_pdf.png)