Zugang zum Dokument
Mayer, Sabine:
Enhancing the Tree Awareness of a Relational DBMS: Adding Staircase Join to PostgreSQL
|
 PDF 524kB
PDF 131kB
|
| URL: | http://kops.ub.uni-konstanz.de/volltexte/2004/1166/ | |
|---|---|---|
| Institut: | Fachbereich Informatik und Informationswissenschaft | |
| Dokumentart: | Diplomarbeit, Magisterarbeit | |
| Sprache: | Englisch | |
| Erstellungsjahr: | 2004 | |
| Eingestellt in KOPS am: | 02.02.2004 | |
| Kurze Inhaltszusammenfassung auf Englisch | 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. |
|
| Kurze Inhaltszusammenfassung auf Deutsch | 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. |
|
| Kontrollierte Schlagwörter (Deutsch): | SQL , XML , XPath , Relationales Datenbanksystem , PostgreSQL | |
| Freie Schlagwörter (Deutsch): | baumstrukturierte Daten , XPath Accelerator , Staircase Join | |
| Freie Schlagwörter (Englisch): | relational database , tree-structured data , XPath Accelerator , Staircase Join | |
| DDC-Sachgruppe: | Informatik | |
| Urheberrecht: | Hinweis zum Urheberrecht | |
