Enhancing the Tree Awareness of a Relational DBMS: Adding Staircase Join to PostgreSQL
Enhancing the Tree Awareness of a Relational DBMS: Adding Staircase Join to PostgreSQL
Lade...
Datum
2004
Autor:innen
Mayer, Sabine
Herausgeber:innen
ISSN der Zeitschrift
eISSN
item.preview.dc.identifier.isbn
Bibliografische Daten
Verlag
Schriftenreihe
URI (zitierfähiger Link)
Internationale Patentnummer
Link zur Lizenz
EU-Projektnummer
Projekt
Open Access-Veröffentlichung
Sammlungen
Titel in einer weiteren Sprache
Publikationstyp
Masterarbeit/Diplomarbeit
Publikationsstatus
Erschienen in
Zusammenfassung
Durch eine geeignete Kodierung kann jedes relationale
Datenbankbankmanagementsystem in die Lage versetzt werden, Anfragen an
baumstrukturierte Daten zu beantworten. Allerdings besitzen
konventionelle relationale Datenbanken in der Regel keine Kenntnis
über die zugrunde liegende Baumstrukturiertheit und können daher die
kodierten Informationen nicht optimal ausnutzen.
Der Staircase Join ist ein neuer Join-Algorithmus, der hier Abhilfe
schafft. Er wurde entwickelt, um die SQL-basierte Auswertung von
XPath-Ausdrücken zu beschleunigen. Der Algorithmus basiert auf
baumspezifischem Wissen sowie auf den Daten des XPath
Accelerator. Dabei handelt es sich um eine Kodierung, mit deren Hilfe
Informationen über den hierarchischen Aufbau eines XML-Dokuments in
einer relationalen Tabelle gespeichert werden können.
Die vorliegende Masterarbeit zeigt, dass es möglich ist, den Staircase
Join in eine konventionelle relationale Datenbank (die
Open-Source-Datenbank PostgreSQL) zu integrieren. Dazu waren
Änderungen an drei von vier Modulen der Anfragebearbeitung in
PostgreSQL nötig: am Parser, am Planer/Optimizer und am Executor.
Die Messungen, die anschließend in der Datenbank durchgeführt wurden,
bestätigen, dass der Staircase Join zu einer erheblichen
Beschleunigung der Anfragebearbeitung führt. Im Vergleich zu dem
Join-Algorithmus, der von der Original-PostgreSQL-Datenbank zur
Beantwortung SQL-basierter XPath-Ausdrücke verwendet wird, war eine
Verbesserung um eine bis mehrere Größenordnungen zu beobachten. Die
Tests haben gezeigt, dass der Staircase Join ein relationales
Datenbanksystem in eine effiziente Lösung für die
XML-Anfragebearbeitung umwandeln kann. Ein wichtiger Baustein, der
dazu allerdings noch entwickelt werden muss, ist ein eigenes Modell,
mit dem die Kosten für die Ausführung eines Staircase Join abgeschätzt
werden können.
Datenbankbankmanagementsystem in die Lage versetzt werden, Anfragen an
baumstrukturierte Daten zu beantworten. Allerdings besitzen
konventionelle relationale Datenbanken in der Regel keine Kenntnis
über die zugrunde liegende Baumstrukturiertheit und können daher die
kodierten Informationen nicht optimal ausnutzen.
Der Staircase Join ist ein neuer Join-Algorithmus, der hier Abhilfe
schafft. Er wurde entwickelt, um die SQL-basierte Auswertung von
XPath-Ausdrücken zu beschleunigen. Der Algorithmus basiert auf
baumspezifischem Wissen sowie auf den Daten des XPath
Accelerator. Dabei handelt es sich um eine Kodierung, mit deren Hilfe
Informationen über den hierarchischen Aufbau eines XML-Dokuments in
einer relationalen Tabelle gespeichert werden können.
Die vorliegende Masterarbeit zeigt, dass es möglich ist, den Staircase
Join in eine konventionelle relationale Datenbank (die
Open-Source-Datenbank PostgreSQL) zu integrieren. Dazu waren
Änderungen an drei von vier Modulen der Anfragebearbeitung in
PostgreSQL nötig: am Parser, am Planer/Optimizer und am Executor.
Die Messungen, die anschließend in der Datenbank durchgeführt wurden,
bestätigen, dass der Staircase Join zu einer erheblichen
Beschleunigung der Anfragebearbeitung führt. Im Vergleich zu dem
Join-Algorithmus, der von der Original-PostgreSQL-Datenbank zur
Beantwortung SQL-basierter XPath-Ausdrücke verwendet wird, war eine
Verbesserung um eine bis mehrere Größenordnungen zu beobachten. Die
Tests haben gezeigt, dass der Staircase Join ein relationales
Datenbanksystem in eine effiziente Lösung für die
XML-Anfragebearbeitung umwandeln kann. Ein wichtiger Baustein, der
dazu allerdings noch entwickelt werden muss, ist ein eigenes Modell,
mit dem die Kosten für die Ausführung eines Staircase Join abgeschätzt
werden können.
Zusammenfassung in einer weiteren Sprache
Given a suitable encoding, any relational DBMS is able to answer
queries on tree-structured data. However, conventional relational
databases are generally not (made) aware of the underlying tree
structure and thus fail to make full use of the encoded information.
The staircase join is a new join algorithm intended to
enhance the tree awareness of a relational DBMS. It was
developed to speed up the SQL-based evaluation of XPath
expressions. The algorithm encapsulates tree-specific knowledge and
relies on the data provided by the XPath accelerator, an
encoding which maps information about the tree-shaped structure of an
XML document to a relational database table.
This thesis shows that it is possible to incorporate the staircase
join into a conventional RDBMS, namely the open-source RDBMS
PostgreSQL. The implementation involved local changes to three out of
four query processing stages in the PostgreSQL backend: the parser,
the planner/optimizer, and the executor.
The performance tests subsequently carried out in the tree-aware
PostgreSQL instance confirmed that the staircase join leads to a
substantial query speed-up. In comparison to the native join algorithm
which is chosen by the original PostgreSQL database to evaluate
SQL-based XPath expressions, the staircase join produced an
improvement up to several orders of magnitude. Thus, the tests have
shown that, in conjunction with a suitable cost model, the staircase
join can turn a relational database system into an efficient XML query
processing solution.
queries on tree-structured data. However, conventional relational
databases are generally not (made) aware of the underlying tree
structure and thus fail to make full use of the encoded information.
The staircase join is a new join algorithm intended to
enhance the tree awareness of a relational DBMS. It was
developed to speed up the SQL-based evaluation of XPath
expressions. The algorithm encapsulates tree-specific knowledge and
relies on the data provided by the XPath accelerator, an
encoding which maps information about the tree-shaped structure of an
XML document to a relational database table.
This thesis shows that it is possible to incorporate the staircase
join into a conventional RDBMS, namely the open-source RDBMS
PostgreSQL. The implementation involved local changes to three out of
four query processing stages in the PostgreSQL backend: the parser,
the planner/optimizer, and the executor.
The performance tests subsequently carried out in the tree-aware
PostgreSQL instance confirmed that the staircase join leads to a
substantial query speed-up. In comparison to the native join algorithm
which is chosen by the original PostgreSQL database to evaluate
SQL-based XPath expressions, the staircase join produced an
improvement up to several orders of magnitude. Thus, the tests have
shown that, in conjunction with a suitable cost model, the staircase
join can turn a relational database system into an efficient XML query
processing solution.
Fachgebiet (DDC)
004 Informatik
Schlagwörter
baumstrukturierte Daten,XPath Accelerator,Staircase Join,relational database,tree-structured data,XPath Accelerator,Staircase Join
Konferenz
Rezension
undefined / . - undefined, undefined. - (undefined; undefined)
Zitieren
ISO 690
MAYER, Sabine, 2004. Enhancing the Tree Awareness of a Relational DBMS: Adding Staircase Join to PostgreSQL [Master thesis]BibTex
@mastersthesis{Mayer2004Enhan-6319,
year={2004},
title={Enhancing the Tree Awareness of a Relational DBMS: Adding Staircase Join to PostgreSQL},
author={Mayer, Sabine}
}
RDF
<rdf:RDF
xmlns:dcterms="http://purl.org/dc/terms/"
xmlns:dc="http://purl.org/dc/elements/1.1/"
xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
xmlns:bibo="http://purl.org/ontology/bibo/"
xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
xmlns:foaf="http://xmlns.com/foaf/0.1/"
xmlns:void="http://rdfs.org/ns/void#"
xmlns:xsd="http://www.w3.org/2001/XMLSchema#" >
<rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/6319">
<dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:11:26Z</dcterms:available>
<dcterms:issued>2004</dcterms:issued>
<foaf:homepage rdf:resource="http://localhost:8080/"/>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6319/1/onlapp.pdf"/>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6319/1/onlapp.pdf"/>
<dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2011-03-24T16:11:26Z</dc:date>
<dcterms:title>Enhancing the Tree Awareness of a Relational DBMS: Adding Staircase Join to PostgreSQL</dcterms:title>
<dspace:hasBitstream rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6319/2/master.pdf"/>
<dcterms:rights rdf:resource="https://rightsstatements.org/page/InC/1.0/"/>
<dcterms:hasPart rdf:resource="https://kops.uni-konstanz.de/bitstream/123456789/6319/2/master.pdf"/>
<dcterms:abstract xml:lang="deu">Durch eine geeignete Kodierung kann jedes relationale<br />Datenbankbankmanagementsystem in die Lage versetzt werden, Anfragen an<br />baumstrukturierte Daten zu beantworten. Allerdings besitzen<br />konventionelle relationale Datenbanken in der Regel keine Kenntnis<br />über die zugrunde liegende Baumstrukturiertheit und können daher die<br />kodierten Informationen nicht optimal ausnutzen.<br /><br />Der Staircase Join ist ein neuer Join-Algorithmus, der hier Abhilfe<br />schafft. Er wurde entwickelt, um die SQL-basierte Auswertung von<br />XPath-Ausdrücken zu beschleunigen. Der Algorithmus basiert auf<br />baumspezifischem Wissen sowie auf den Daten des XPath<br />Accelerator. Dabei handelt es sich um eine Kodierung, mit deren Hilfe<br />Informationen über den hierarchischen Aufbau eines XML-Dokuments in<br />einer relationalen Tabelle gespeichert werden können.<br /><br />Die vorliegende Masterarbeit zeigt, dass es möglich ist, den Staircase<br />Join in eine konventionelle relationale Datenbank (die<br />Open-Source-Datenbank PostgreSQL) zu integrieren. Dazu waren<br />Änderungen an drei von vier Modulen der Anfragebearbeitung in<br />PostgreSQL nötig: am Parser, am Planer/Optimizer und am Executor.<br /><br />Die Messungen, die anschließend in der Datenbank durchgeführt wurden,<br />bestätigen, dass der Staircase Join zu einer erheblichen<br />Beschleunigung der Anfragebearbeitung führt. Im Vergleich zu dem<br />Join-Algorithmus, der von der Original-PostgreSQL-Datenbank zur<br />Beantwortung SQL-basierter XPath-Ausdrücke verwendet wird, war eine<br />Verbesserung um eine bis mehrere Größenordnungen zu beobachten. Die<br />Tests haben gezeigt, dass der Staircase Join ein relationales<br />Datenbanksystem in eine effiziente Lösung für die<br />XML-Anfragebearbeitung umwandeln kann. Ein wichtiger Baustein, der<br />dazu allerdings noch entwickelt werden muss, ist ein eigenes Modell,<br />mit dem die Kosten für die Ausführung eines Staircase Join abgeschätzt<br />werden können.</dcterms:abstract>
<dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<dc:language>eng</dc:language>
<dc:format>application/pdf</dc:format>
<dc:contributor>Mayer, Sabine</dc:contributor>
<void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
<dc:rights>terms-of-use</dc:rights>
<dc:creator>Mayer, Sabine</dc:creator>
<dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
<bibo:uri rdf:resource="http://kops.uni-konstanz.de/handle/123456789/6319"/>
</rdf:Description>
</rdf:RDF>