|
Rewriting Declarative Query Languages
Brantner, Matthias
|
URL:
|
http://ub-madoc.bib.uni-mannheim.de/1749
|
|
URN:
|
urn:nbn:de:bsz:180-madoc-17499
|
|
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:
|
11 October 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 Syst H.2.3 Lang ,
|
|
Subject headings (SWD):
|
Optimierung , XPath , XML 1.0 , XML , XQuery , SQL
|
|
Individual keywords (German):
|
Entschachtelung , Disjunktionen , logische Algebra
|
|
Keywords (English):
|
Unnesting , Disjunctions , logical Algebra
|
|
Abstract:
|
Queries against databases are formulated in declarative languages. Examples are the relational query language SQL and XPath or XQuery for querying data stored in XML. Using a declarative query language, the querist does not need to know about or decide on anything about the actual strategy a system uses to answer the query. Instead, the system can freely choose among the algorithms it employs to answer a query. Predominantly, query processing in the relational context is accomplished using a relational algebra. To this end, the query is translated into a logical algebra. The algebra consists of logical operators which facilitate the application of various optimization techniques. For example, logical algebra expressions can be rewritten in order to yield more efficient expressions. In order to query XML data, XPath and XQuery have been developed. Both are declarative query languages and, hence, can benefit from powerful optimizations. For instance, they could be evaluated using an algebraic framework. However, in general, the existing approaches are not directly utilizable for XML query processing. This thesis has two goals. The first goal is to overcome the above-mentioned misfits of XML query processing, making it ready for industrial-strength settings. Specifically, we develop an algebraic framework that is designed for the efficient evaluation of XPath and XQuery. To this end, we define an order-aware logical algebra and a translation of XPath into this algebra. Furthermore, based on the resulting algebraic expressions, we present rewrites in order to speed up the execution of such queries. The second goal is to investigate rewriting techniques in the relational context. To this end, we present rewrites based on algebraic equivalences that unnest nested SQL queries with disjunctions. Specifically, we present equivalences for unnesting algebraic expressions with bypass operators to handle disjunctive linking and correlation. Our approach can be applied to quantified table subqueries as well as scalar subqueries. For all our results, we present experiments that demonstrate the effectiveness of the developed approaches.
|
|
Translation of the title:
|
Umschreiben von deklarativen Anfragesprachen
(German)
|
|
Translation of the abstract:
|
Anfragen an Datenbanken werden mit Hilfe deklarativer Anfragesprachen gestellt. Beispiele hierfür sind die relationale Anfragesprache SQL und XPath oder XQuery für Anfragen an XML-Daten. Auf Grund der Deklarativität muss der Anfragesteller nichts über die Techniken wissen, die benutzt werden, um eine Anfrage zu bearbeiten. Stattdessen kann der Anfragebearbeiter eines Datenbanksystems hierfür beliebige Algorithmen auswählen. Im relationalen Kontext wird die Anfragebearbeitung gewöhnlich mit Hilfe einer relationalen Algebra durchgeführt. Hierfür wird eine Anfrage in eine logische Algebra übersetzt. Diese Algebra besteht aus logischen Operatoren, die es erlauben, zahlreiche Optimierungstechniken anzuwenden. Beispielsweise können Ausdrücke in einer logischen Algebra umgeschrieben werden, um Ausdrücke zu erhalten, die effizienter auszuwerten sind. Um Anfragen an Daten zu stellen, die im XML Format gespeichert sind, wurden die Anfragesprachen XPath und XQuery entwickelt. Beide sind deklarativ und haben dadurch ebenfalls ein großes Optimierungspotential. Insbesondere können sie mit einer Algebra ausgewertet werden. Leider sind die existierenden Ansätze (z.B. aus dem relationalen Kontext) jedoch nicht direkt anwendbar. Das Ziel dieser Dissertation besteht aus zwei Teilen. Im ersten Teil werden die eben genannten Defizite der Auswertung von XML-Anfragespachen beseitigt. Es wird ein algebraisches Rahmenwerk entwickelt, um XPath und XQuery effizient auszuwerten. Dadurch soll es möglich werden, XPath und XQuery im großtechnischen Einsatz zu benutzen. Hierfür wird zuerst eine ordnungserhaltende logische Algebra definiert und danach eine Übersetzung von XPath in diese Algebra vorgestellt. Darüber hinaus werden Regeln vorstellt, mit denen ein Algebra-Ausdruck umgeformt werden kann, um den resultierenden algebraischen Ausdruck schneller ausgewerten zu können. Im zweiten Teil der Arbeit werden neue Optimierungen im relationalen Kontext entwickelt, mit deren Hilfe sich geschachtelte SQL-Anfragen mit Disjunktionen entschachteln lassen. Hierfür werden algebraische Äquivalenzen vorgestellt, welche geschachtelte algebraische Ausdrücke in algebraische Ausdrücke mit "Bypass-Operatoren" überführen. Die entwickelten Äquivalenzen können Anfragen mit einem disjunktiven Verbindungsprädikat und Anfragen, bei denen das Korrelationsprädikat disjunktiv vorkommt, entschachteln. Damit lassen sich sowohl Unteranfragen mit mengenwertigen Ergebnissen, als auch Anfragen mit skalaren Ergebnissen, entschachteln. Für alle Optimierungen wurden Experimente durchgeführt. Ihre Ergebnisse, die in dieser Arbeit vorgestellt werden, zeigen die Wirksamkeit aller entwickelten Ansätze zeigen.
(German)
|
|
Additional information:
|
|
 | Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt. |
 Search Authors in
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)