Enhancing the Tree Awareness of a Relational DBMS: Adding Staircase Join to PostgreSQL

Durch eine geeignete Kodierung kann jedes relationaleDatenbankbankmanagementsystem in die Lage versetzt werden, Anfragen anbaumstrukturierte Daten zu beantworten. Allerdings besitzenkonventionelle relationale Datenbanken in der Regel keine Kenntnisüber die zugrunde liegende Baumstrukturiertheit und können daher diekodierten Informationen nicht optimal ausnutzen.Der Staircase Join ist ein neuer Join-Algorithmus, der hier Abhilfeschafft. Er wurde entwickelt, um die SQL-basierte Auswertung vonXPath-Ausdrücken zu beschleunigen. Der Algorithmus basiert aufbaumspezifischem Wissen sowie auf den Daten des XPathAccelerator. Dabei handelt es sich um eine Kodierung, mit deren HilfeInformationen über den hierarchischen Aufbau eines XML-Dokuments ineiner relationalen Tabelle gespeichert werden können.Die vorliegende Masterarbeit zeigt, dass es möglich ist, den StaircaseJoin in eine konventionelle relationale Datenbank (dieOpen-Source-Datenbank PostgreSQL) zu integrieren. Dazu warenÄnderungen an drei von vier Modulen der Anfragebearbeitung inPostgreSQL 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 erheblichenBeschleunigung der Anfragebearbeitung führt. Im Vergleich zu demJoin-Algorithmus, der von der Original-PostgreSQL-Datenbank zurBeantwortung SQL-basierter XPath-Ausdrücke verwendet wird, war eineVerbesserung um eine bis mehrere Größenordnungen zu beobachten. DieTests haben gezeigt, dass der Staircase Join ein relationalesDatenbanksystem in eine effiziente Lösung für dieXML-Anfragebearbeitung umwandeln kann. Ein wichtiger Baustein, derdazu allerdings noch entwickelt werden muss, ist ein eigenes Modell,mit dem die Kosten für die Ausführung eines Staircase Join abgeschätztwerden können