Bei einem aktuellen Projekt haben wir eine interessante Fragestellung, die einem eigentlich immer bei hierarchischen Strukturen begegnet. Konkret geht es darum, numerische Daten zu hierarchisch organisierten Orten zu aggregieren (Summenbildung). Beispiel: Werte zu Städten sollen hierarchisch aggregiert (∑-Bildung) werden:
In unserem Projekt haben wir die Daten zu den Blättern, und müssen Auswertungen über diese Daten an der Knoten resp. an der Wurzel berechnen. Stellen wir uns also folgende Aufgabe: das Summieren aller Nachfahren von Europa. Dazu müssten zunächst alle Kinder von Europa selektiert werden und anschließend alle Kinder dieser Kinder. Schon an der Formulierung wird deutlich: hierbei handelt es sich um ein rekursives Problem. Solch ein Problem lässt sich mittels SQL allerdings weder leicht noch effizient lösen. Wir müssen unsere Entitäten also um weitere Attribute ergänzen, die eine solche Selektion effizienter machen.
Für die Umsetzung des Projekts haben wir auf das in python geschriebene WebFramework django1) gesetzt. Hierzu existiert eine Erweiterung, die sich django-mptt2) nennt. MPTT steht für Modified Preorder Tree Traversal, auch als Nested Sets bekannt. Diese Technik ermöglicht es Pfade oder Teilbäume innerhalb eines Baumes effizient auszulesen. Der Nachteil ist, dass Modifikationen an den Bäumen teuer sind; d.h. wir erkaufen uns effiziente Lesezugriffe durch aufwändige Schreibzugriffe. Für Anwendungen, bei denen sich die Bäume häufig ändern, kann das zu einem Problem werden; unser Use-Case sieht das zum Glück nicht vor.
Wie arbeitet diese Erweiterung nun im Detail? Theoretisch braucht man für eine Baumstruktur nur ein parent-Attribut, dass an allen Knoten hängt. So ist dies auch bei mptt, wobei mptt dieses um die folgenden Attribute erweitert: tree id, right und left.
Alle Entitäten, die die gleiche Wurzel haben, erhalten die gleiche tree id. Im Prinzip bedeutet das, alle Nachfahren einer Entität, deren parent-Attribut nicht gesetzt ist, gehören zu einem Baum. Diese Entität ist somit Wurzel. Im obigen Beispiel wären das Europa und Asien. Die beiden weiteren Attribute sind etwas schwieriger zu verstehen. Um diese Werte zu ermitteln wird ein, der Tiefensuche ähnlicher, Algorithmus verwendet. Dazu schauen wir uns noch einmal die Grafik dieses Beitrages an:
Die Vergabe der left- und right Attribute funktioniert so: Der Algorithmus durchläuft alle Knoten im Baum beginnend bei der Wurzel und führt dabei einen Zähler mit. Beim betreten eines Knotens wird der left-Wert auf den aktuellen Zählerwert gesetzt und der Zähler erhöht. Hat der Knoten Kinder so werden diese nun durchlaufen. Sind alle Kinder eines Knotens durchlaufen oder hat der Knoten keine Kinder wird er wieder verlassen. Beim Verlassen des Knotens wird der right-Wert wiederum auf den aktuellen Zählerstand gesetzt und dieser anschließend inkrementiert. Dies wird fortgeführt bis alle Knoten besucht wurden und wieder die Wurzel erreicht ist.
Wenn wir uns nun die Zahlen betrachten stellen wir folgendes fest:
Welche Queries lassen sich mit diesem Wissen realisieren? (Jeder Query der sich auf die Baum-Attribute bezieht ist immer im Context einer tree id. Diese muss also in jeden Query aufgenommen werden und wird hier der Einfachheit halber nicht mit aufgeführt.):
Außerdem gibt es natürlich auch die trivialen Queries:
Hier nun ein Beispiel eines Selects, der der Aufgabenstellung entspricht, also die Summe über die Werte alle Nachfahren.
SELECT SUM(`value`.`amount`)
FROM `node` AS `parent`
JOIN `node` AS `descendant`
ON (`descendant`.`tree_id` = `parent`.`tree_id`
AND `descendant`.`left` > `parent`.`left`
AND `descendant`.`right` < `parent`.`right`)
JOIN `value`
ON (`value`.`node_id` = `descendant`.`id`)
WHERE `parent`.`name` = 'Europa'
Wollen wir alle Knoten in der Reihenfolge ausgeben, in der sie oben gezeigt ist, müssen wir nur nach tree id und left sortieren. Wichtig ist, dass alle Baum-Attribute von der Datenbank indiziert werden, da sie bei jedem Query benötigt werden.
In unserem Projekt ist das ganze natürlich etwas komplizierter als hier beschrieben - so sind die Teilbäume dynamsich (abhängig von Filterregeln); und Daten können auch in Zwischenebenen existieren.
Kommentare