Manipulation der Baumstruktur

Im Abschnitt Der Aufbau eines Nested Sets-Baumes wurde eine Einfügeoperation vorgestellt, die einem gegebenen Knoten immer einen neuen Kindknoten hinzufügt und zwar “ganz rechts” im Baum, also in Bezug auf einen preorder-walk “nach” seinen Geschwistern. Für das Beispiel dieses Tutorials ist diese Methode ausreichend, da das in Bezug auf ein einfaches Forum genau die gewünschte Funktionalität darstellt.

Für andere Anwendungen wie zum Beispiel dem interaktiven Aufbau von Menüsystemen werden aber in der Regel weitere Operationen zur Manipulation der Baumstruktur benötigt. In diesem Anhang werden einige der wichtigsten davon vorgestellt. Dabei müssen alle Funktionen auf der Datenbank als “atomare Operationen” ausgeführt werden. Das kann entweder durch ein sperren der gesamten Tabelle oder viel effizienter durch das Einbetten der Methoden in eine Transaktion geschehen, sofern ein Transaktionsmanagemt zur Verfügung steht (z.B. ab MySQL 4+ mit InnoDB).

Bezugspunkte

Alle Funktionen zur weiteren Manipulation des Nested-Set-Baumes benötigen als Eingangsparameter die node_ID des Knotens, auf den sie sich beziehen. Aus dieser können dann in einem einfachen SELECT-Statement die zugehörige root_id sowie die LFT und RGT Werte ermittelt werden.

LOCK TABLES node WRITE;
...
SELECT root_id, lft, rgt FROM node WHERE node_id = V_NODE_ID
...
UNLOCK TABLES;

Im Folgenden werden diese Werte einfach als virtuelle Variablen mit dem Prefix V_ dargestellt. In der Realität können sie einfach innerhalb der jeweils verwendeten, übergeordneten Programmiersprache bereitgestellt werden.

Ein Bruder rechts:

Mit der folgenden Methode kann ein neues Blatt auf dem gleichen Level, rechts vom einem vorhandenen Knoten eingefügt werden. Als Eingangsparameter wird dazu die ID des Bezugsknotens, V_BROTHER_ID, benötigt. Anhand dieser werden zunächst die zugehörigen Werte V_ROOT_ID und V_BROTHER_RGT ermittelt.

LOCK TABLES node WRITE;

# make room for the new node
UPDATE node
   SET lft = lft + 2
 WHERE root_id = V_ROOT_ID AND lft > V_BROTHER_RGT;

UPDATE node
   SET rgt = rgt + 2
 WHERE root_id = V_ROOT_ID AND rgt > V_BROTHER_RGT;

# insert the sibling
INSERT INTO node ( root_id, payload, lft, rgt )
          VALUES ( V_ROOT_ID, 'a right brother', V_BROTHER_RGT + 1,
                   V_BROTHER_RGT + 2 );
UNLOCK TABLES;

Ein Bruder links:

Analog zur eben beschriebenen Methode fügt diese ein neues Blatt auf dem gleichen Level, links vom einem vorhandenen Knoten ein. Als Eingangsparameter wird dazu wieder die ID des Bezugsknotens, V_BROTHER_ID, benötigt. Daraus werden dann die zugehörigen Werte V_ROOT_ID und V_BROTHER_LFT selektiert.

LOCK TABLES node WRITE;

# make room for the new node
UPDATE node
   SET lft = lft + 2
 WHERE root_id = V_ROOT_ID AND lft >= V_BROTHER_LFT;

UPDATE node
   SET rgt = rgt + 2
 WHERE root_id = V_ROOT_ID AND rgt > V_BROTHER_LFT;

# insert the sibling
INSERT INTO node ( root_id, payload, lft, rgt )
          VALUES ( V_ROOT_ID, 'a brother to the left', V_BROTHER_LFT,
                   V_BROTHER_LFT + 1 );
UNLOCK TABLES;

Mit Hilfe dieser beiden Methoden, sowie der Einfügeoperation aus dem Abschnitt Der Aufbau eines Nested Sets-Baumes ist es möglich, beliebige Nested-Set-Bäume in beliebiger Reihenfolge aufzubauen bzw. zu erweitern.

Ein Blatt löschen

Zum Löschen eines einzelnen Blattes (das ist ein Knoten ohne Kinder werden dessen ID, V_NODE_ID, sowie die zugehörigen LFT, RGT und ROOT_ID Werte, V_LFT, V_RGT und V_ROOT_ID, benötigt. Im Vorfeld muss natürlich geprüft werden, ob es sich wirklich nur um ein Blatt handelt (Bedingung: V_RGT = V_LFT + 1), was in der umgebenden Programmiersprache leicht möglich ist.

LOCK TABLES node WRITE;

# delete the node
DELETE FROM node WHERE node_id = V_NODE_ID;                

# move the rest of the nodes ...
UPDATE node
   SET lft = lft - 2
 WHERE root_id = V_ROOT_ID AND lft > V_RGT;

UPDATE node
   SET rgt = rgt - 2
 WHERE root_id = V_ROOT_ID AND rgt > V_RGT;

UNLOCK TABLES;

Einen Teilbaum löschen

Das Löschen eines Teilbaumes verläuft prinzipiell gleich wie das Löschen eines Blattes. Allerdings muss zusätzlich ein Wert V_MOVE berechnet werden, der angibt, um welche Werte die LFT / RGT Attribute der Folgeknoten vermindert werden müssen.

V_MOVE kann in der umgebenden Programmiersprache aus den üblichen Variablen wie folgt berechnet werden:

Pseudocode...

V_MOVE = floor((V_RGT-V_LFT)/2);
V_MOVE = 2 * (1+V_MOVE);

LOCK TABLES node WRITE;

# delete the node including its children
DELETE FROM node
      WHERE root_id = V_ROOT_ID
        AND lft between V_LFT AND V_RGT;                

# move the rest of the nodes ...
UPDATE node
   SET lft = lft - V_MOVE
 WHERE root_id = V_ROOT_ID AND lft > V_RGT;

UPDATE node
   SET rgt = rgt - V_MOVE
 WHERE root_id = V_ROOT_ID AND rgt > V_RGT;

UNLOCK TABLES;

Mit dieser Funktion kann natürlich auch ein einzelnes Blatt gelöscht werden. Das wäre dann der Spezialfall V_RGT = V_LFT + 1.

Für V_MOVE würde sich dann V_MOVE = 2 * (1 + floor ( V_LFT + 1 - V_LFT )/2)) = 2 ergeben.

Und der Rest?

Was noch übrig bleibt sind diverse Verschiebeoperationen. Diese können am besten durch Kombinationen der vorgestellten Grundoperationen realisiert werden. Das Schema ist dabei immer:

Daten des Blattes / Teilbaumes exportieren
Blatt / Teilbaum löschen
Exportierte Daten wieder in der richtigen Reihenfolge einfügen

Eine ausführliche Darstellung würde den Rahmen dieses Tutorials aber sicher sprengen, sie können aber gerne beim Autor Holger Morgenstern nachfragen.

Die Darstellung der Implementation einer Nested-Set-Modellierung mittels JAVA und MySQL finden Sie unter http://www.morgenstern.net/NestedSet.html .