[Workshop] Nested Sets

[Stuck Mojo]

Ich kündige hier mal einen neuen Workshop von Theo (Hardy) an.

Hier mal eine kurze Roadmap zum Workshop:

am anfang hab ich ein paar allgemeine sachen (warum nested sets und das problem der baeume im mysql; kurze uebersicht zu den mathematischen grundlagen). dann folgen beispiele kleiner baeume mit grafiken zum verstaendnis des grundprinzips und alle mathematischen regeln, die in den verschachtelten mengen wichtig sind.
teil 3 beinhaltet den gesamten db-teil. aufbau, erweiterung und manipulation von baeumen. aber noch alles rein im mysql.
teil 4 wird dann die kombination aus php und mysql mit einem beispiel fuer eine php-seite zur administration und eine zur ausgabe von baumstrukturen.

[theo]

So Mädels und Jungs,

hier also Teil I des Workshops "Nested sets".

Zunächst mal ein paar allgemeine Sachen:
die verwendeten Grafiken des ersten Teils stammen alle von folgender Webseite - Nested sets - die kennen sicher viele schon, weil ich sie schon öfter gepostet habe.
Der erste Teil wird sich ausschließlich mit den theo-retischen Grundlagen beschäftigen.
Im zweiten Teil gehe ich dann auf dem Hauptteil der benötigten SQL-Statements ein und im Teil III verbinden wir das Ganze mit einer übergeordneten Programmiersprache (PHP).

Gut ... los gehts!


Was sind Bäume?
Als gelerntem Gärtner und Landespfleger sollte mir bei dem Begriff "Baum" so ein grünes Ding mit Ästen und Blättern einfallen. Doch um die soll es hier nicht gehen. Die Bäume dieses Workshops sind wesentlich abstraktere Gebilde und werden so definiert:

Ein Baum ist ein azyklischer Graph, in dem genau ein Knoten keinen Vorgänger hat und alle anderen Knoten mindestens einen Vorgänger haben.

Klingt kompliziert, ist aber so. Vielleicht sollte ich es mit eigenen Worten beschreiben und dabei ein paar Vorteile und Funktionen erklären.

Jeder von uns, ob Linux-, Mac- oder Win-User, benutzt jeden Tag Bäume. Unsere Festplatten mit ihren Laufwerksbuchstaben sind die Wurzel- oder Root-Verzeichnisse, die Ordner die Verzweigungen oder Knoten und unsere Daten sind die Blätter. Doch warum sind die Datenstrukturen unter allen Systemen so aufgebaut oder anders gefragt: warum haben sich diese Baumstrukturen durchgesetzt? Weil ich an Deinen Rechner gehen kann und egal wie Du Deine Daten ordnest, ich würde mich relativ schnell zurechtfinden.

Baumstrukturen sind also leicht und intuitiv zu handhaben. Hat Dir jemand den Aufbau dieses Forums erklären müssen, damit Du Dich hier sicher und schnell bewegen kannst? Würde es Dir schwer fallen Dir einen Überblick über die einzelnen Teile und die Ordnung eines Unternehmens zu verschaffen, wenn Du auf dessen Baumstruktur schaust? Und was ist mit der Navigation von Webseiten? Hast Du nicht selbst schon eine solche Struktur verwendet oder Seiten gesehen, die es tun?
Was Bäume sind und warum wir ihnen überall begegnen wissen wir also nun. Bleibt die nächste Frage zu klären ….

Was sind Nested sets?
Bei der Abbildung von Baumstrukturen in Datenbanken stehen uns unter SQL leider keine proprietären Erweiterungen, wie z.B. CONNECT BY (PRIOR) zur Verfügung, welche die hierarchische Verkettung von Daten übernehmen können. Wir müssen also auf Hilfskonstrukte zurückgreifen.

Es haben sich hier mit der Zeit unterschiedliche Lösungsansätze entwickelt, von welchen sich das System der Nested sets als effektiv und flexibel bei Aufbau, Erweiterung und Manipulation erwiesen hat.

Das Thema "Nested sets", nicht zuletzt von mir im Forum immer wieder erwähnt, ist ein beinahe mystisches Kapitel der Zusammenarbeit von PHP und SQL. Viele haben davon gehört, die meisten von uns benutzen sie täglich, ohne es zu merken, und doch scheuen sich viele davor, sich mit ihrem Einsatz näher auseinanderzusetzen. Warum?

Die meisten von uns erinnern sich mit Grauen an die langen öden Mathestunden unserer Schulzeit und doch arbeiten wir als Programmierer jeden Tag mit Begeisterung mit den Mitteln, die uns einen bitteren Beigeschmack in die Nachmittage über Büchern und Hausaufgaben gemengt haben. Vielleicht ist hier der Grund zu finden, warum die Nested sets im ersten Augenblick Ablehnung in uns hervorrufen. Denn auch, wenn wir uns beim Umgang mit PHP und SQL meist über deren mathematischen Grundlagen hinwegtäuschen können, beim Modell der verschachtelten Mengen können wir es nicht mehr. Hier springt und die Mathematik mit nacktem Hintern auf den ersten Blick ins Gesicht. Vielleicht ist es aber auch die zugegebenermaßen nicht ganz leicht zu erschließende Logik, die hinter diesem System steht. Doch wer es einmal begriffen und die Genialität seiner Logik schätzen gelernt hat, der wird Nested sets lieben!

Um die Hemmschwellen gegenüber den SQL-basierten Bäumen abzubauen und etwas mehr Verständnis für sie zu wecken, hab ich mich zu diesem Workshop "breitschlagen" lassen.

Also was sind Nested sets? Die Idee, welche sich hinter diesem Begriff verbirgt, ist die Abstraktion von Bäumen als Mengen und Teilmengen oder anders gesagt: verschachtelte Mengen.



Abbildung1: Baum und Menge


Wie in Abbildung 1 sehr gut zu erkennen ist, lassen sich baumartige Strukturen leicht als Mengen und Teilmengen darstellen. Die Wurzel A einhält die Mengen der Objekte B und C. Es hat also sehr viel mit Mathe zu tun. Aber keine Angst! Man kann alles lernen und verstehen.

Zähne zusammenbeißen und … los geht’s!

Schauen wir uns den gleichen Baum von Abbildung 1 in der Form an, wie wir sie in diesem Workshop auch weiterhin verwenden werden (Abbildung 2).



Abbildung2: Baumdarstellung in Tabellen


Hier seht Ihr, daß die einzelnen Knoten, so heißen die Objekte im Baum, als Tabellen dargestellt wurden. Nehmen wir einen solchen Knoten mal etwas genauer unter die Lupe:



Abbildung3: einzelner Knoten


Der Aufbau zeigt drei Teile: den Kopf, Payload oder Name des Knotens, eine linke und eine rechte Seite. Was verbirgt sich hinter diesen geheimnisvollen Feldern?

Die beiden Tabellenfelder LFT und RGT werden benötigt, um die Abhängigkeiten innerhalb des Baumes darstellen zu können. Die Reihenfolge der Knoten wird durch das Auslesen der Zahlen mittels so genanntem Preorder-Walk gewährleistet. Doch wie funktioniert das Ganze?

Bei den einzelnen Elementen des Baumes wird die linke Seite des Wurzelknotens ausgelesen und dann alle linken Seiten der Unterknoten durchlaufen bis zum letzten Blatt und dann werden alle rechten Seiten ausgelesen. Klingt kompliziert, ist es auch. Aber nicht wirklich!

In der Abbildung 2 seht Ihr einen Baum, mein alter Prof. Höster möge mir verzeihen, bestehend aus einer Wurzel und zwei Blättern. Die Darstellung mit den Tabellen zeigt deutlich die Logik hinter den Nested sets. Die Wurzel beginnt links immer mit 1. Danach werden in numerischer Reihenfolge zuerst alle linken und dann alle rechten Seiten durchlaufen. Alles klar? Prima! Dann machen wir jetzt noch ein klein wenig Mathe und das nächste Mal gehen wir dann die Datenbanken an.

Doch erst könnt Ihr Euer neu erworbenes Wissen testen, indem Ihr Euch die Abbildung 4 anseht und prüft, ob Euch klar ist, daß beide Darstellungen einander entsprechen.



Abbildung4: umfangreicherer Baum als Tabellen- und Baumdarstellung


Warum machen wir den ganzen "Blödsinn" mit den linken und rechten Seiten, den Zahlen und Mengen? Kann man das nicht einfacher haben? Nützt das was?



Abbildung5: Abbildung4 als Mengendiagramm


Klar nützt das was! Man kann sich als Held fühlen, wenn man es verstanden hat, massig angeben und einen Workshop machen.

Aber im Ernst … na klar hat das Ganze einen tieferen Sinn. Und der kommt jetzt.

Folgende Regeln gelten in den Bäumen:

1. LFT = 1 => Wurzel
   d.h. eine Wurzel hat auf der linken Seite immer eine "1" stehen. Klingt einfach und logisch, ist aber oft sehr wichtig zu wissen. Vor allem wenn wir dann zu den SQL-Statements kommen!
2. Blatt RGT – Blatt LFT = 1
   Auch das klingt simpel und logisch. Ist es auch und daher ein sehr guter Anhaltspunkt für die Manipulation von Bäumen,
3. Wurzel RGT / 2 = Anzahl der Knoten im Baum
   also teilt man in der Wurzel den Wert der rechten Seite, so erhält man die Anzahl aller Knoten im Baum,
4. floor((RGT – LFT) / 2) = Anzahl der Kindknoten im Zweig (incl. Der Blätter)
   zieht man von der rechten die linke Seite ab und teil sie durch 2, so entspricht das gerundete Ergebnis der Anzahl der Blätter im Zweig,
5. alle LFT- und RGT-Werte sind eindeutig!

Laßt Euch diese fünf einfachen Regeln mal in Ruhe ein, zwei Tage durch den Kopf gehen. Dann komme ich mit Teil II und der Frage: Wie setze ich das ganze in einer Datenbankstruktur um?
Dann wird es etwas weniger trocken nicht ganz so lang.

Hardy (aka theo)

[theo]

Baumstrukturen und SQL

Wer den Workshop bis jetzt genau verfolgt hat, der wird bei vergleichen mit den Seiten der Quellangaben (Bilder) festgestellt haben: hey, der schreibt ja fast das Gleiche wie dort.

Ok, dann paßt in diesem Abschnitt ebenso gut auf und ihr werdet feststellen, daß ich einige der SQL-Statements geändert habe.

Zunächst brauchen wir eine einfache Tabelle in unserer Datenbank und die legen wir ganz einfach wie folgt an:

CREATE TABLE node (
node_id INT(10) UNSIGNED NOT NULL AUTO_INCREMENT,
root_id INT(10) UNSIGNED NOT NULL,
payload VARCHAR(64) NULL,
lft INT(10) UNSIGNED NOT NULL,
rgt INT(10) UNSIGNED NOT NULL,
PRIMARY KEY (node_id),
KEY root_id (root_id)
);

Damit dürfte niemand Probleme haben. Wer doch … der sollte zunächst einen anderen Workshop durcharbeiten.

Fangen wir mit der Erstellung einer Wurzel an. Im Teil I des Workshops haben wir gelernt: jeder Knoten hat links eine "1". Und jeder Wurzelknoten ohne Blätter hat auf der rechten Seite eine "2". Das haben viele gelesen, gelacht und gesagt: na der erklärt Sachen, die so offensichtlich logisch sind, daß man nicht drüber reden muß. Na gut, dann setzen wir das Ganze mal um!

INSERT INTO node (payload,lft,rgt)
VALUES ('Name der Wurzel',1,2);
		
SELECT @max_id := MAX(root_id)
FROM node;
					
UPDATE node
SET root_id = @max_id + 1
WHERE node_id = LAST_INSERT_ID();

Dieses Statement erzeugt eine Wurzel. Im Gegensatz zu anderen Statements erzeugt mein Script so viele Wurzeln, wie man möchte und muß lediglich später im Zusammenspiel mit der übergeordneten Programmiersprache mit einem entsprechenden Namen für die einzelnen Wurzeln versehen werden.

Es sei hier nochmals drauf hingewiesen, daß ich in diesem Teil ausschließlich auf MySQL eingehen werde. Wer auf fertige Codes und PHP wartet, der … muß sich noch ein wenig gedulden!

So, dann schauen wir doch mal, ob der Knoten auch da ist. Dafür lesen wir jetzt einfach alle Wurzeln aus (da das Auslesen aller Daten ja wohl kein Problem sein dürfte). Z.B. so:

SELECT payload
FROM node
GROUP BY root_id;

War eigentlich auch ein Kinderspiel. Jetzt müßtet Ihr folgendes sehen:
+---------+
| payload |
+---------+
| Wurzel 1 |
+---------+

Nach dem Einfügen weiterer Wurzeln werden auch diese in unserer Liste auftauchen. Doch warum nicht gleich alles ausgeben? Wir erinnern uns: es soll eine Baumstruktur werden.

Wir müssen also aus den Zahlen, die in der Datenbank stehen, lesen, welches Objekt in welcher Ebene eingeordnet wird. Doch wie soll das gehen? Ganz einfach so:

SELECT node1.payload, node1.node_id,
COUNT(*) AS level
FROM node AS node1,
node AS node2

WHERE node1.root_id = 1
AND node2.root_id = 1
AND node1.lft BETWEEN node2.lft AND node2.rgt
GROUP BY node1.lft

Das ist mal wieder ein Statement für Dennis. Wir machen aus einer Tabelle eine Megatabelle. Aber über das Thema kartesisches Produkt bei JOINS haben wir ja bereits diskutiert. Und hier geht es um 5 Spalten. Hey … das kann so schlimm nicht werden!

Hier erhalten wir eine Liste aller Objekte der Wurzel mit der root_id = 1. Leider werden hier nicht alle Wurzeln ausgegeben und ich muß auf dieses Thema im PHP-Teil zurückkommen. Denn bislang hab ich die Ausgabe aller Wurzeln (incl. ihrer Zweige und Blätter) nur mit einem zweiten Statement und einer while-Schleife lösen können. Sollte jemand eine reine SQL-Alternative finden, so schreibt mir.


Manipulieren von Bäumen

Ich hoffe, daß alle, die den Workshop bis hierher verfolgt haben, bereits erkennen, wohin die Sache geht. Wir haben Wurzeln und Zweige aufgebaut und ausgelesen. Aber damit können wir natürlich nicht zufrieden sein. Kommen wir darum jetzt zum Einfügen neuer Zweige und Blätter.

Die übergeordnete Programmiersprache muß später für unser folgendes Statement die nötigen Variablen bereitstellen:

1. root_id der Wurzel bzw. des Zweiges, an dem das neue Element angefügt werden soll = ROOT_ID
2. rechte Seite der Wurzel oder des Zweiges = RGT
3. (sonst wird auch noch die linke Seite ausgelesen, doch die benötigen wir nicht)

UPDATE node
SET lft = lft + 2
WHERE root_id = ROOT_ID
AND lft > RGT;

UPDATE node
SET rgt = rgt + 2
WHERE root_id = ROOT_ID
AND rgt >= RGT;

INSERT INTO node (root_id,payload,lft,rgt)
VALUES (ROOT_ID,'neues Blatt',RGT,RGT+1);

Mit Hilfe diesen Statements könnt Ihr an jeder beliebigen Stelle einen neuen Zweig oder ein Blatt rechts vom gewählten Knoten einfügen. Alle linken und rechten Seiten (wir erinnern uns an die Abbildungen aus Teil I) werden automatisch korrigiert.

Na … is das was?! Der Hammer oder?! Macht das mal per Hand … und ohne Fehler! Oder auf einem Blatt Papier. Wie lange würdet Ihr brauchen?

Erinnern wir uns an die 4. Regel innerhalb von Bäumen aus Teil I: floor((RGT-LFT) / 2) = Anzahl der Knoten im Zweig.
Mit ihrer Hilfe können wir uns jetzt Folgendes anzeigen lassen:

SELECT node1.payload,
floor((node1.rgt – node1.lft) / 2) AS children
COUNT(*) AS level
FROM node AS node1,
node AS node2

WHERE node1.root_id = 1
AND node2.root_id = 1
AND node1.lft BETWEEN node2.lft AND node2.rgt
GROUP BY node1.lft;

Als Ergebnis erhalten wir eine Tabelle, welche alle Knoten der Wurzel mit der root_id = 1 incl. der Angabe über vorhandene Kindknoten und Ebene der Knoten.

Wer es bis hierher geschafft hat, wird auch den Rest noch "überstehen". Machen wir uns also an die noch fehlenden Funktionen: Knoten an bestimmten Positionen einfügen, löschen und ganze Teilbäume entfernen.

Da es jetzt etwas komplizierter wird, werde ich das Tempo etwas rausnehmen.

Wir wollen also in unseren vorhandenen Baum einen neuen Knoten auf der gleichen Ebene einfügen. Dafür muß uns die übergeordnete Programmiersprache wieder die benötigten Variablen bereitstellen. Bei Seiten, bei denen mehrere User gleichzeitig das gleiche Script zur Manipulationen an Bäumen verwenden können, sollten die Tabellen für die Zeit der Änderung gesperrt werden. Bei den aktuellen SQL-Versionen kann das Sperren der Tabellen auch über die Verwendung entsprechender Tabellentypen gewährleistet werden (InnoDB).
Ich verzichte hier auf die Sperrung. Wer dazu noch Fragen hat, kann sich gerne melden.

Ich werde für mein Statement lediglich die node_id als von der übergeordneten Scriptsprache übergebenen Parameter annehmen. Wer mag, läßt die SQL-Variable raus und holt sich die Werte bereits vorher per PHP. Somit ließe sich eine Abfrage sparen.

Das folgende Statement fügt auf dem gleichen Level rechts eines vorhandenen Knotens einen neuen Knoten ein. Die Bezeichnung "Bruder" für diese Knoten gefällt mir so sehr, daß ich sie hier auch übernehmen werde.
Wir fügen also jetzt einen Bruder auf der rechten Seite ein:

SELECT @ROOT_ID := root_id, @BROTHER_RGT := rgt
FROM node
WHERE node_id = 'NODE_ID';

UPDATE node
SET lft = lft + 2
WHERE root_id = @ROOT_ID AND lft > @BROTHER_RGT;

UPDATE node
SET rgt = rgt + 2
WHERE root_id = @ROOT_ID AND rgt > @BROTHER_RGT;

INSERT INTO node (root_id, payload, lft, rgt)
VALUES (@ROOT_ID, 'my right little brother', @BROTHER_RGT+1, @BROTHER_RGT+2);

Bevor ich der zwingenden Logik folge und Euch das Einfügen eines Bruders auf der linken Seite zeige, will ich mal wieder ein wenig was für das grundlegende Verständnis tun.
An der Stelle hab ich länger gebraucht, weil es ohne Grafik (zumindest für mich) nicht ohne weiteres zu verstehen war.

Warum dieses links und rechts? Ist das nicht egal? ... Nö!



Abbildung1: Bruder rechts einfügen


Die Abbildung1 zeigt, wo der Knoten rechts eines vorhandenen eingefügt wird.
Sehen wir uns das Einfügen auf der linken Seite an:

SELECT @node_id := root_id, @lft := lft
FROM node
WHERE node_id = NODE_ID;
				
UPDATE node
SET lft = lft + 2
WHERE root_id = @node_id AND lft > @lft;
				
UPDATE node
SET rgt = rgt + 2
WHERE root_id = @root_id AND rgt > @lft";

INSERT INTO node (root_id, payload, lft, rgt)
VALUES (@root_id, 'my left little brother' @lft, @lft + 1);

Hätten wir das mit den bisherigen Statements hinbekommen?
Nach dieser rethorischen Frage nochmal was fürs Auge:



Abbildung2: Bruder links einfügen


Eine Struktur wie in Abbildung2 zu manipulieren, schaffen wir nur noch mit einem guten Script und sauberen Statements.
Was, wenn wir jetzt ein einzelnes Blatt löschen wollen? Alle Zahlen müssen für den Preorder-Walk neu geordnet werden. Doch ist das Blatt wirklich ein Blatt? Wie war das noch mit den Blättern? Regel 2: rechte minus linke Seite gleich 1?! Richtig! Wir prüfen also zuvor, ob es sich wirklich um ein Blatt handelt. Doch das merken wir uns für den nächsten Teil, denn da brauchen wir etwas Hilfe von PHP.

Wir gehen also davon aus, daß wir uns über die Identität des Blattes sicher sind. Dann löschen wir es doch einfach:

SELECT @rgt := rgt, @root_id := root_id
FROM node
WHERE node_id = NODE_ID;

DELETE FROM node
WHERE node_id = NODE_ID;

UPDATE node
SET lft = lft - 2
WHERE root_id = @root_id
AND lft > @rgt;

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

Nach dem Löschen des Blattes müssen wieder alle verbleibenden rechten und linken Seiten in die richtige numerische Reihenfolge gebracht werden.

Ok, das ist nicht mehr so ganz leicht. Darum mach ich nur noch ein Statement und dann ist erstmal Schluß. Puhh ... Erleichterung!

Was ist bei dem Fall, daß wir einen gesamten Teilbaum löschen wollen? Ein Board wird geschlossen, ein Teil eins Unternehmens verkauft oder ausgegliedert ... praktisch denkbare Fälle gibts es da viele.
Doch wie reagiert unser Datenbank oder anders gefragt: wie muss unser Statement aussehen, damit alle linken und rechten Seiten so nachgerueckt werden, daß der Preorder-Walk wieder funktioniert?

Für diesen Teil hab ich mal wieder ein Statement geschrieben, welches ohne zusätzliche Hilfe der Programmiersprache auskommt:

SELECT DISTINCT @NODES := floor((RGT-LFT)/2), @STEPS := 2 * (1 + @MOVE), @root_id = root_id
FROM node
WHERE rgt = RGT;
# wir erinnern uns: alle RGT und LFT Werte sind eindeutig!

DELETE FROM node
WHERE root_id = @root_id
AND lft BETWEEN LFT
AND RGT;

UPDATE node
SET lft = lft - @STEPS
WHERE root_id = @root_id
AND lft > RGT;

UPDATE node
SET rgt = rgt - @STEPS
WHERE root_id = @root_id
AND rgt > RGT;

Zuerst ermitteln wir also die Anzahl der Knoten im Zweig. Aus ihr ermitteln wir die Schritte, um die die verbleibenden Knoten korrigiert werden müssen, damit unser Preorder-Walk wieder funktioniert.
Danach löschen wir alle Knoten des Zweiges und ändern dann alle linken und rechten Seiten.


So ... ich hoffe die Fraktion der Nested-sets-Ablehner ist nach diesem Teil nicht noch größer geworden.
Für das Durcharbeiten laß ich Euch jetzt ein paar Tage länger Zeit und dann machen wir mit PHP weiter. Wir bauen eine Seite mit Nested sets auf und ich zeig Euch dann gleich dazu noch einen Treemanager, mit dem Ihr die Navigation administrieren könnt.

Viel Spaß beim Testen und Üben.
Wenn Ihr Fragen haben solltet ... ich bin hier bzw. im icq (113-763-544) zu erreichen.

Hardy


PS: Ein netter Moderator hat mich darauf hingewiesen, daß ich doch noch einen Satz zu SQL und MySQL anfügen sollte.
Die Statements beziehen sich alle auf MySQL und können in anderen Datenbanksystemen (vor allem die Variablen) ganz anders aussehen. Den Sinn hinter den Statements sollte jeder nachvollziehen können. Die Schreibweise aber gegebenenfalls anpassen.

[SMURF]

hi,

sehr schön geschriebenes Tutorial. Kompliment ... Habe eine kleine Ergänzung an folgender Stelle

floor((RGT – LFT) / 2) = Anzahl der Kindknoten im Zweig (incl. Der Blätter)
zieht man von der rechten die linke Seite ab und teil sie durch 2, so entspricht das gerundete Ergebnis der Anzahl der Blätter im Zweig.

ich fände es geschickter auf die "floor-Funktion" im Statement zu verzichten und statdessen folgendes zu schreiben:

( (RGT-1) – LFT) ) / 2)

als Ergänzung zum Tutorial wäre vielleicht noch interessant, wie man beim Verschieben eines Blattes bzw. Teilbaums vorgeht. Z.B. für Teil 3

Gruß

SMURF

[theo]

hi smurf,

erstmal vielen dank fuer die blumen! auch allen anderen, die sich per pm, mail oder icq gemeldet haben.

wie es aussieht, werde ich tatsaechlich eine ergaenzung machen muessen. doch die wird sich auf den zweiten teil beziehen und auf einige fragen eingehen, die beim durcharbeiten aufgetaucht sind. das thema scheint komplexer und schwieriger, als ich erst angenommen hatte.
daher ... anfang der woche teil IIa und mitte bis ende der woche teil III - nested stes und php.

ich denke bereits ueber einen vierten teil nach, in dem ich auf die restlichen statements, funktionen und eine suchmaschinenoptimierung mittels nested sets eingehen koennte.
das haengt dann von euch ab und ob ihr dann ueberhaupt noch bock habt.

gruss
hardy

[theo]

Nachdem Ihr den ersten Teil so widerspruchslos hingenommen hattet, kamen zum Teil II dann doch Fragen. Einiges hat mich zu weiterem Nachdenken angeregt mir aber auch gezeigt, daß es auch mir nicht gelungen ist, das "Nested-sets-Problem" einfach und für jeden leichtverständlich zu formulieren.

Auf ein paar der Fragen und Überlegungen möchte ich in dieser Ergänzung eingehen.

Zunächst ein paar Worte zu meinem Statement zum Wurzelposting. Ich habe bei meiner ersten intensiveren Berührung mit dem Thema "Bäume und Datenbanken" das Statement zum Erzeugen einer Wurzel gesehen und nicht verstanden, warum man nicht mehrere Wurzel erzeugen kann. Es schien mir unlogisch, ein Script in einer übergeordneten Programmiersprache zu schreiben, ein Statement damit ausführen zu lassen und es dann nie wieder zu verwenden. Klingt auch nicht sonderlich clever.

Doch war mein Ausgangspunkt ein anderer: ich programmiere seit anderthalb oder fast zwei Jahren an einem Webportal. In mal größeren und kleineren Abständen ergänze ich Funktionen, Inhalte, Seiten. Für mich drehen sich "ernsthafte" Webprojekte um diese Dimension Präsenz. Für den Aufbau einer solchen Seite war mir sofort klar, daß ich nicht mit einer Wurzel auskomme. Ich brauch mehrere! Keine Angst, die nächste Grafik verdeutlicht meine verschrobenen Gedankengänge etwas besser.

Nach dem Hinweis auf "üblicherweise vorkommende Einwurzelsysteme" und mein "Mehrwurzelsystem" habe ich mir die Vor- und Nachteile durch den Kopf gehen lassen und bin zu folgenden Ergebnissen gekommen:

• in Einwurzellösungen kann man jeden beliebigen Knoten (samt seiner Kinder) in der Hierarchie bis max. auf Ebene 1 schieben
• bei Mehrwurzelsystemen sind Aufbau und Handhabung der Statements einfacher
• bei Mehrwurzelsystemen kann ein Zweigknoten nie den gleichen Status einer Wurzel erlangen
• bei Einwurzelsystemen kann ein Zweigknoten das oberste Niveau erreichen, wenn die Wurzel ausgeblendet wird

Und schon bin ich wieder in Erklärungsnot, aber das war mir klar und daher hab ich bunte Bildchen, um mangelnde Rhetorik auszugleichen.



Abbildung1: möglicher Aufbau von Webseiten mit Bäumen


Eine Webseite, aufgebaut wie in Abbildung1 links, kommt mit einem Baum aus, der über lediglich eine Wurzel verfügt.

Was aber bei einer Webpräsenz, wie sie in Abbildung2 rechts zu sehen ist? Die Navigation läßt sich nur mit einem Baum lösen, dessen Wurzelposting nicht angezeigt wird bzw. wenn man mehrere Wurzeln einsetzen kann.

Für mich war von vornherein die "Mehrwurzellösung" der Favorit und bleibt es auch solange, wie man nicht einen Teilzweig auf Rootniveau schieben muß. Kommt sicher selten vor, aber kann passieren. Dann ist meine Variante machtlos und ich muß den gesamten Baum neu aufsetzen.

Das Ganze, was wir hier durchspielen, lehnt sich gedanklich schon sehr an die mögliche Anwendung an und praktische Gesichtspunkte verändern unseren Blick auf die Theorie.

Noch ein Gedanke, bevor ich wieder im Off verschwinde und Euch Ruhe zum Nachdenken lasse. Die Aufteilung in mehrere Wurzeln kann auf den ersten Blick nicht nur Verwirren, sondern auch die Funktion der Verschachtelten Mengen in Frage stellen. Die Abfragen von linken und rechten Seiten stiftet Verwirrung und dann hab ich auch zweimal darauf hingewiesen, daß sie eindeutig sind. Und nun komme ich und zerstöre diese schöne Ordnung. Innerhalb unserer Tabelle tauchen mehrmals die gleichen Werte bei links und rechts auf (bei mehreren Wurzeln!). Was ist daran noch eindeutig? Die root_id und … vor allem … die node_id. Wir verlieren während der Abfragen der DB den Kontakt zu unseren Datensätzen nicht. Also ... don´t panic!


So, laßt Euch die Sachen noch mal in Ruhe durch den Kopf gehen. Wir machen dann diese Woche mit dem PHP-Teil weiter.


PS: Statements zum Verschieben von Teilbäumen hatte ich für einen späteren Zeitpunkt vorgesehen. An der Stelle versuche ich dann auch, ein Statement für einen Baum ohne Wurzelposting nachzulegen.

[gromok]

ahoi,

mich würde interessieren ob denn hier noch fortgesetzt wird, da mich das tutorial sehr angesprochen hat

[theo]

ahoi auch,

hab es auch schon anderen versprochen: dieses wochenende arbeite ich dran!
anfang der woche geht es weiter.

[gromok]

super! schön, das zu hören. Ich freu mich drauf *mutmach* *motivier*

[fettmme]

Danke auch von mir. Interessantes Thema

[theo]

danke, danke! ihr macht mir echt mut und baut mich auf

[theo]

Ok! Machen wir weiter.

Danke erstmal an alle, die mir geschrieben haben. Vor allem an die, welche sich so intensiv mit dem Thema auseinander gesetzt und mich mit ihren Fragen bis zur Verlegenheit gebracht haben.

Von hier aus auch einen Gruß an die Leute von (noch) außerhalb des Forums. Besonders an den "Zerstoiber". Ich hab die statements nochmal bearbeitet und umgeschrieben. Damit dürften sich die Fragen vielleicht schon erledigt haben. Ansonsten ... icq.

Aber jetzt gehts los!

Wir brauchen eine Datenbank. Also brauchen wir einen Zugang (die Profis "hören" hier mal bitte weg!). Dafür legen wir alle Zugangsdaten in eine nestedSets.inc.php und diese in unser erstes Unterverzeichnis /inc.

$DB['host']    = "localhost";
$DB['user']    = "root";
$DB['pass']    = "";
$DB['name']    = "nested_sets"; 

Und die wird jetzt in die nestedSets_fnc.inc.php eingebunden. Das sieht dann so aus:

require_once "inc/nestedSets.inc.php";

 /** connect zur datenbank **/
 function connectDB() {
     global $DB;
    
    $linkID = mysql_connect($DB['host'],$DB['user'],$DB['pass']) or 
                die("Hilfe, kann Server nicht erreichen!");
              mysql_select_db($DB['name']) or 
                  die("keine Datenbank erreichbar, Käpt´n!");
                
    return $linkID;    // ja dennis, ich weiss, dass man das nicht muss!  *fg*
 } 

Ab jetzt wirds denk ich wieder für alle interessant.

Als erstes lesen wir die Navigation aus. Erstmal nur auslesen. Wir bringen das Ganze später in Form.

/** navigation aufbauen **/
 function getNavi() {
     $sql = "SELECT DISTINCT root_id AS roots
            FROM node";
    
    $result = mysql_query($sql, connectDB());
    $count    = mysql_num_rows($result);
    
    while($row = mysql_fetch_array($result)){
        $root[] = $row[0];
    } // while
 
     $sql= "SELECT n.*,
           floor((n.rgt-n.lft-1)/2) AS childs,
           count(*)+(n.lft>1) AS level,
           ((min(p.rgt)-n.rgt-(n.lft>1))/2) > 0 AS lower,
           (((n.lft-max(p.lft)>1))) AS upper
           FROM node n, node p ";
        if ($count > 1) {    // fuer mehrere wurzeln
            $sql.= "WHERE n.lft BETWEEN p.lft AND p.rgt
                    AND (p.root_id = n.root_id)
                    AND (p.node_id != n.node_id OR n.lft = 1)
                    AND (p.root_id IN (".implode(",",$root)."))
                    GROUP BY n.root_id,n.node_id
                    ORDER BY n.root_id,n.lft";
        } elseif ($count == 1) {    // ... oder eben nur eine
            $sql.= "WHERE n.lft BETWEEN p.lft AND p.rgt
                    AND (p.root_id = n.root_id)
                    AND (p.node_id != n.node_id OR n.lft = 1)
                    AND (p.root_id = ".$root[0].")
                    GROUP BY n.node_id
                    ORDER BY n.lft";
        } else {    // alle wurzeln ... der defaulf-fall eben
            $sql.= "WHERE n.lft BETWEEN p.lft AND p.rgt
                    AND (p.root_id = n.root_id)
                    AND (p.node_id != n.node_id OR n.lft = 1)
                    GROUP BY n.root_id,n.node_id
                    ORDER BY n.root_id,n.lft";
        }


        $result = mysql_query($sql, connectDB());
        
        return $result;
 } 

Ganz schöner Brocken. Ich hab mal wieder auf floor zurückgegriffen. Der Rest müßte soweit drinstehen (siehe Kommentare).
Bringen wir das Ganze jetzt in eine Form. Und wundert Euch bitte nicht über die "seltsamen" Formatierungen. Das Rätsel löse ich später. Danke auf jeden Fall an Jan und bereits hier möchte ich auf seine Urheberschaft an dem Javascript hinweisen. Von ihm bekommt mein PHP-Scrpit sein Mojo.

/** navigation ausgeben **/
 function showNavi() {
     $result = getNavi();
    
    // diese funktion ist dermassen unsauber  *ganzrotwerd*
    // die muss unbedingt noch ueberarbeitet werden!
     if ($_REQUEST['site'] == "admin"):
        $tree = "<table border=\"0\" cellspacing=\"0\" cellpadding=\"0\"><form action=\"\" method=\"post\">";
        $tree.= "<tr id=\"top\"><th>Wurzel</th>";
        $tree.= "<th>Name</th><th>Ebene</th>";
        $tree.= "<th>Verschieben</th><th>Löschen</th>";
        $tree.= "<th>Einfügen</th>";
        $tree.= "<th>Editieren</th></tr>";
        while($row = mysql_fetch_array($result)) {
            ($race/2 == floor($race/2)) ? $class = "line1" : $class = "line2";
            $tree.= "<tr><td align=\"center\" class=\"".$class."\">".$row[1]."</td>";
            $tree.= "<td class=\"".$class."\">".$row[2]."</td>";
            $tree.= "<td align=\"center\" class=\"".$class."\">".$row[6]."</td>";
            $tree.= "<td align=\"center\" class=\"".$class."\"><a href=\"".$PHP_SELF."?site=admin&action=moveup&id=".$row[0]."\" onfocus=\"blur()\"><img src=\"img/up.png\" border=\"0\"></a> ";
            $tree.= "<!-- <a href=\"".$PHP_SELF."?site=admin&action=movedown&id=".$row[0]."\" onfocus=\"blur()\"><img src=\"img/down.png\" border=\"0\"></a> --></td>";
            $tree.= "<td align=\"center\" class=\"".$class."\"><a href=\"".$PHP_SELF."?site=admin&action=del&id=".$row[0]."\" onfocus=\"blur()\"><img src=\"img/del.png\" border=\"0\"></a></td>";
            $tree.= "<td align=\"center\" class=\"".$class."\"><a href=\"".$PHP_SELF."?site=admin&action=insert&id=".$row[0]."\" onfocus=\"blur()\"><img src=\"img/insert.png\" border=\"0\"></a></td>";
            $tree.= "<td align=\"center\" class=\"".$class."\"><a href=\"".$PHP_SELF."?site=admin&action=edit&id=".$row[0]."\" onfocus=\"blur()\"><img src=\"img/edit.png\" border=\"0\"></a></td></tr>";
            $race+=1;
        } // while
        $tree.= "</form></table>";
    else:
        // bei diesem teil darf ich mich fuer die hilfe von jan bedanken
        $level = 1;
                         $tree.= "<ul id=\"NewTree\">";
        
        while($row = mysql_fetch_array($result)) {
            if ($row['level'] > $level)
                $tree.= "<ul>";
            else if ($row['level'] < $level)
                $tree.= str_repeat("</li></ul>", $level-$row['level']);
            else if ($level > 1)
                $tree.= "</li>";
                
            $tree.= "<li value_id=\"".$row['node_id']."\" level=\"".$row['level']."\" input_id=\"".$row['root_id']."\" productgroupname=\"\" input_type=\"\"><span>".$row[2]."</span>";
            $level = $row['level'];
        } // while
        $tree.= str_repeat("</ul>", $level-1);
    endif;
    
    return $tree;
 } 

So, kommen wir jetzt zu den Manipulationen. Fügen wir zuerst neue Knoten ein. Das Script funzt sowohl für Knoten, Blätter und Wurzel.

/** fuegt einen neuen knoten ein **/
 function nodeIns($id,$name) {
    if (!empty($id)) $node = getNode($id);
    
    if (!empty($id)) {
        if ($id == $node[0]) {
            if ($brother == "left"):    // noch ungetestet!
            $sql = "UPDATE node
                    SET lft = lft + 2
                    WHERE root_id = ".$node[1]."
                    AND lft > ".$node[4]."
                    AND rgt >= ".$node[4]."";
            $result = mysql_query($sql, connectDB());
            $sql = "UPDATE node
                    SET rgt = rgt + 2
                    WHERE root_id = ".$node[1]."
                    AND rgt >= ".$node[4]."";
            $result = mysql_query($sql, connectDB());

            $sql = "INSERT INTO node (root_id,payload,lft,rgt)
                    VALUES (".$node[1].",'".$name."',".$node[3].",".($node[3]+2).")";
            $result = mysql_query($sql, connectDB());
            else:    // bruder rechts
            $sql = "UPDATE node
                    SET lft = lft + 2
                    WHERE root_id = ".$node[1]."
                    AND lft > ".$node[4]."
                    AND rgt >= ".$node[4]."";
            $result = mysql_query($sql, connectDB());
            $sql = "UPDATE node
                    SET rgt = rgt + 2
                    WHERE root_id = ".$node[1]."
                    AND rgt >= ".$node[4]."";
            $result = mysql_query($sql, connectDB());

            $sql = "INSERT INTO node (root_id,payload,lft,rgt)
                    VALUES (".$node[1].",'".$name."',".$node[4].",".($node[4]+1).")";
            $result = mysql_query($sql, connectDB());
            endif;
        }
    } else {
        $sql = "SELECT     max(root_id) as maxroot
                FROM node";
        $result = mysql_query($sql, connectDB());

        $row = mysql_fetch_row($result);
        $root_id = $row[0];
        
        $sql = "INSERT INTO node (root_id,payload,lft,rgt)
                VALUES (".($root_id+1).",'".$name."',1,2)";
        $result = mysql_query($sql, connectDB());
    }
 } 

Damit wir das Ganze nachher umbenennen können (hier wird als default-Wert "neuer Knoten" als Name eingesetzt) hier der Update eines Knoten.

function nodeUpdate($id,$name) {
     $sql = "UPDATE node 
            SET payload = '".$name."'  
            WHERE node_id = '".$id."'";    
    $result = mysql_query($sql, connectDB());
 } 

Und weil das so klein und niedlich war gleich unseren Helfer hinterher. Einige von Euch haben ihn vielleicht schon vermißt.

/** infos ueber den knoten **/
 function getNode($id) {
    // alle wichtigen angaben zu einem knoten (root_id,
    // node_id, payload, lft, rgt und die kinderchen)
    $sql = "SELECT *, floor((rgt - lft)/2) AS childs
            FROM node
            WHERE node_id = ".$id."";
            
    $result = mysql_query($sql, connectDB());
    
    $row = mysql_fetch_row($result);

    return $row;
 } 

Was wir eingefügt haben möchten wir auch wieder löschen. Oder das, was andere geschrieben haben ... nicht wahr Paul!

/** knoten loeschen - mit und ohne kinder **/
 function nodeDel ($id) {
    $node = getNode($id);
    
    if (($node[4]==$node[3]+1)): // wenn es ein blatt ist
        $sql = "UPDATE node
                SET lft = lft - 2
                WHERE lft > ".$node[3]."
                AND root_id = ".$node[1];
        $result = mysql_query($sql, connectDB());

        $sql = "UPDATE node
                SET rgt = rgt - 2
                WHERE rgt > ".$node[4]."
                AND root_id = ".$node[1];
        $result = mysql_query($sql, connectDB());

        $sql = "DELETE
                FROM node
                WHERE node_id = ".$id;
        $result = mysql_query($sql, connectDB());
    else: // ... oder ein knoten
        // VORSICHT! diese funktion loescht alle
        // knoten und blaetter im zweig mit!
        $sql = "DELETE
                FROM node
                WHERE rgt <= ".$node[4]."
                AND    lft >= ".$node[3]."
                AND    root_id = ".$node[1];
        $result = mysql_query($sql, connectDB());

        $sql = "UPDATE node
                SET    rgt = rgt - ".($node[4]-$node[3]+1)."
                WHERE rgt > ".$node[4]."
                AND    root_id = ".$node[1];
        $result = mysql_query($sql, connectDB());

        $sql = "UPDATE node
                SET    lft = lft - ".($node[4]-$node[3]+1)."
                WHERE lft > ".$node[4]."
                AND    root_id = ".$node[1];
        $result = mysql_query($sql, connectDB());
    endif;
 } 

Und seid bitte vorsichtig! Ich habs schon geschrieben: das Script löscht ganze Zweige ohne Nachfrage mit allem drum und dran.

Bleibt erstmal nur noch das Verschieben von Knoten. Hier wird zunächst nur nach oben gerückt.

/** knoten verschieben **/
 function nodeMove($id,$direction) {
        $sql = "SELECT    n1.root_id,
                n1.payload n1payload, n1.lft n1lft, n1.rgt n1rgt,
                n2.payload n2payload, n2.lft n2lft, n2.rgt n2rgt
                FROM node AS n1
                LEFT OUTER JOIN
                node AS n2
                ON (n1.lft = (n2.rgt+1) 
                    AND    n1.rgt > n2.rgt
                    AND n1.root_id = n2.root_id)
                WHERE n1.node_id=".$id."";
        
        $result = mysql_query($sql, connectDB());
        
        $nodes = mysql_fetch_row($result);
        $result = mysql_query($sql, connectDB());

        if (!$nodes[5]) $error = "<p>Kein übergeordneter Knoten vorhanden!</p>";

        $desc = (($nodes[2]-$nodes[5]));
        $inc = (($nodes[3]-$nodes[6]));
        
            $sql = "UPDATE node
                    SET    lft = lft + IF(lft<".$nodes[2].",".$inc.",-".$desc."),
                    rgt = rgt + IF(rgt<".$nodes[2].",".$inc.",-".$desc.")
                    WHERE root_id = ".$nodes[0]."
                    AND lft >= ".$nodes[5]."
                    AND rgt <= ".$nodes[3]."";

        $result = mysql_query($sql, connectDB());
        
        return $error;
 } 

Wer das Ganze in Funktion testen möchte: hier läuft es schon (im Augenblick noch IE only ... zumindest das javascript). Bitte zum Ein- und Ausklappen der Verzweigungen neben die Knoten klicken (werdet Ihr schon finden ).

Ich pack die Sachen jetzt noch zusammen und leg sie dann zum downloaden und testen bereit.

Um noch ein paar Sachen zu erläutern:
Die Idee mit den Variablen innerhalb der Statements hab ich erstmal aufgegeben (nehme ich vielleicht für eine zukünftige Klasse wieder auf). Während der Scripttest zu diesem Workshop hatte ich zu viele Fehlerausgaben mit den Variablen und nicht genügend Zeit, diesen auf den Grund zu gehen.
Die Frage nach dem "Aufwärtsschieben" der Knoten muß ich auch noch schuldig bleiben. Mein Testscript macht das zwar bereits, verdirbt dabei allerdings sämliche linke und rechte Werte.
Das Löschen bräuchte noch einen Warnhinweis und eine Bestätigung. Und dann ist die Funktion zum Aufbau der Navigation noch eine Katastrophe.

So, jetzt fällt mir nix mehr ein. Probierts aus und dann ... schlagt mich ans Kreuz.

Einen lieben Gruß Euch allen
Euer Hardy

[theo]

Beinahe hätte ich es vergessen:
Den TreeManager findet Ihr unter dem kleinen "Pi" links unten. Das war eigentlich als kleiner Scherz in Anlehnung an "Das Netz" gedacht. Jetzt hat es seinen Weg bis in die Demo gefunden und die meisten bereits seine Bedeutung.

Fettes sorry an alle, die es nicht gleich gefunden haben!

[rigo2]

Hi,

ich beschäftige mich auch gerade mit Nested Sets, um eine Datenbankstruktur darzustellen und einzelne Sets zu verschieben/löschen/editieren.

Ich haben unter folgendem Link gerade eine Klasse gefunden, die mir recht brauchbar erscheint. Was meint Ihr dazu?

Ich muss jetzt nur noch mal ein Beispiel basteln, um das Ganze zu testen.

http://dev.e-taller.net/dbtree/

Mein längerfristiges Ziel ist es, eine Open-Source-Kleinanzeigenscript für Postnuke zu entwickeln, dass sich durch höchstmögliche Flexibilität und Erweiterbarkeit auszeichnet. Vielleicht hat ja jemand Zeit und Lust mitzumachen.

CU
rigo2

[theo]

hi rigo2,

ich hab in ner ruhigen minute mal reingeschaut. sieht nicht schlecht aus.
langfristig waere ne klasse sicher die beste loesung fuer die baeume.

fuer alle, die den thread mit dem link zu den beispieldateien verpasst haben:
hier nochmal der link.

viel spass
hardy