[kampfgnom]

Hei ho,
ich bin mal wieder dabei eine Breadcrumb Navigation zu erstellen. Diese Soll diesesmal allerdings unendlich weit nachu nten gefächert werden können.
Also hab ich nochmal in meinem alten Beitrag gelesen (Umsetzung einer Breadcrumb Navigation mit PHP/MySQL)
und bin auf Nested Sets gekommen. Also mal angeschaut und versucht umzusetzen.
Dabei bin ich bei diesem Tutorial gelandet:
http://www.klempert.de/nested_sets/artikel/
Und da gibt es ein SQL-Statement:

CREATE TABLE tree (
    id    INT(12)      UNSIGNED NOT NULL AUTO_INCREMENT,
    name  VARCHAR(50)  NOT NULL,
    lft   INT(12)      UNSIGNED NOT NULL,
    rgt   INT(12)      UNSIGNED NOT NULL, 
    PRIMARY KEY (id),
    key lft (lft),
    key rgt (rgt),
);

Soweit so gut, jetzt hab ich versucht das mit meinem PHPmyAdmin auszuführen aber da kommt folgende Fehlermeldung:

MySQL meldet:
#1064 - You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near ')' at line 9

Ich kann da aber keinen Fehler finden. Könnt ihr mir Helfen?

[Ben]

Das letzte Komma ist zu viel.

[kampfgnom]

Oha, ich hab immer nur auf die Grafik mit dem "X" geschaut und die war an der Zeile mit der aussage:

 rgt   INT(12)      UNSIGNED NOT NULL,

und da hab ich mich gefragt, was daran falsch sein soll

Danke, jetzt kann ich weiterlesen.

Ich werd sicher noch die eine oder andere Frage zu Nested Sets stellen. Bin nich so Fit in SQL

[Ben]

Schon öfters verlinkt: http://reeg.junetz.de/DSP/node11.htm...00000000000000

Ist eigentlich ein tolles Tutorial (im Gesamten).

[ex³]

Das hat mir das mit den NestedSets geholfen:

http://phpperformance.de/nested-sets...eume-in-mysql/

[kampfgnom]

Danke für die Links, allerdings hatte ich ja schon ein Tutorial, es war lediglich dieser Fehler der mich zum Verzweifeln gebracht hat =)

[Ben]

Irgendwie passt es und passt gleichzeitig nicht ... egal: *spam*

Neusortieren / Neuordnen von NestedSets mit PHP und JavaScript
http://www.dotvoid.com/view.php?id=78

[ex³]

Auf der PHP Perfomance Page sowie bei der Seite von Arne Klempert ist folgender Query, nötig wenn Kategorien gelöscht werden:

DELETE FROM kategorien WHERE lft BETWEEN $LFT AND $RGT;

Danach kommt noch:

UPDATE kategorien SET lft=lft-1, rgt=rgt-1 WHERE lft BETWEEN $LFT AND $RGT;
UPDATE kategorien SET lft=lft-2 WHERE lft>$RGT;
UPDATE kategorien SET rgt=rgt-2 WHERE rgt>$RGT;

Mit diesen vier Queries soll erzielt werden das eine Kategorie gelöscht wird und die darunterliegenden auf die Ebene der gelöschten Kategorie kommen. Allerdings funktioniert das bei mir nicht da der DELETE Query ja die darunterliegenden Kategorien sofort killt. Ich hab den DELETE Query geändert und dadurch scheint es zu funktionieren:

DELETE FROM kategorien WHERE lft = $LFT AND rgt = $RGT;

Versteht das einer? Oder muss es wirklich BETWEEN heißen?

Außerdem hat jemand noch einen Ansatz wie ich Kategorien verschiebe?

[Basti]

Zitat von ex³

DELETE FROM kategorien WHERE lft BETWEEN $LFT AND $RGT;

Danach kommt noch:

UPDATE kategorien SET lft=lft-1, rgt=rgt-1 WHERE lft BETWEEN $LFT AND $RGT;
UPDATE kategorien SET lft=lft-2 WHERE lft>$RGT;
UPDATE kategorien SET rgt=rgt-2 WHERE rgt>$RGT;

Scheint mir ziemlich unsinnig. Die erste Update-Query macht genau nichts, das ja alle Datensätze, die die WHERE-Klausel erfüllen bereits gelöscht sind. Danch werden alle Werte oberhalb der entstandenen Lücke um 2 verringert, was nur dann Sinn macht, wenn der gelöschte knoten ein "Endknoten" war, wenn also nicht ein Teilbaum, nicht mehrere Knoten gelöscht wurden. Auch wenn kein Knoten gelöscht wurde, gibt es hier Probleme.

Hier eine Umsetzung aus meinem Alltag:

PHP-Code:

<?php

    public function removeNode($sNodeId)
    {
        $sQuery = '

            LOCK TABLES `tree` WRITE
        ';

        $this->query($sQuery);

        $sQuery = "

            SELECT
                `left`,
                `right`

            FROM
                `tree`

            WHERE
                id = '%s'
        ";

        $this->query($sQuery, array($sNodeId));

        $aNode  = $this->fetch();
        $sLeft  = $aNode['left'];
        $sRight = $aNode['right'];

        $sMove = (string) floor(((int) $sRight - (int) $sLeft) / 2);
        $sMove = 2 * (1 + $sMove);

        $sQuery = "

            DELETE FROM
                `tree`

            WHERE
                `left` between '%s' AND '%s'
        ";

        $this->query($sQuery, array($sLeft, $sRight));

        $sQuery = "

            UPDATE
                `tree`

            SET
                `left` = `left` - '%s'

            WHERE
                `left` > '%s'
        ";

        $this->query($sQuery, array($sMove, $sRight));

        $sQuery = "

            UPDATE
                tree

            SET
                `right` = `right` - '%s'

            WHERE
                `right` > '%s'
        ";

        $this->query($sQuery, array($sMove, $sRight));

        $sQuery = "

            UNLOCK TABLES;
        ";

        $this->query($sQuery);

    }

Ich prüfe also erst, wie groß die Lücke sein wird, lösche dann den Teilbaum und verringere die Werte oberhalb der Lücke um den entsprechenden Wert.

Basti

[ex³]

Hi Basti. Ich hab dein Code mal ausprobiert und bei mir wird der jeweilige Knoten (und die darunterliegenden gelöscht) wie es sein soll.

Hast du noch ein paar andere Ansätze? Wie z.B. einen Ast an einen anderen hängen oder einen Ast eine Ebene nach oben verschieben?

Ich versuche eben allgemein Grade mir eine Schnittstelle für sowas zu bauen, wo man die Kategorien so hin und herschieben, kann wie die Überschriften im Navigator von OpenOffice.

Ach Basti, dein Code ist recht simple, hast du das geschrieben? Das bin ich garnicht gewohnt von deinen Posts. Normalerweise sind die immer so kompliziert.

[Basti]

Zitat von ex³

Hast du noch ein paar andere Ansätze? Wie z.B. einen Ast an einen anderen hängen oder einen Ast eine Ebene nach oben verschieben?

Für mich war die härteste Nuss, einen Teilbaum/Knoten zu verschieben. Hab da mit lauter Zetteln gesessen und die auf dem Büroboden rumgeschoben, um da einen Algorithmus rauszudestilieren - dabei ist es eigentlich ganz einfach:

PHP-Code:

    public function move($sNodeId, $sTargetId, $cRelation)
    {

        $this->query('LOCK TABLES `tree` WRITE');

        $this->query("

SELECT
    `id`,
    `left`,
    `right`

FROM
    `tree`

WHERE
    `id` = '%s'
OR
    `id` = '%s'

        ", array($sNodeId, $sTargetId));
    
        while($Record = $this->fetchObject()) {
        
            if ($Record->id === $sNodeId)
                $Node = $Record;
        
            if ($Record->id === $sTargetid)
                $Target = $Record;
        }
    
        if (!isset($Node) || !isset($Target))
            die('Fehlerhafte Knoten-IDs uebergeben');
        
        if ($Target->left > $Node->left && $Target->left < $Node->right)
            die('Bezugspunkt darf nicht im zu verschiebenden Teilbaum liegen');
        
        $iSpace  = $Node->right - $Node->left + 1;
        $iOffset = 0;

        switch ($cRelation) {
        
            case APPEND_CHILD:
            $iDiff = $Target->left;
            break;
            
            case INSERT_LEFT:
            $iDiff = $Target->left - 1;
            break;
            
            case INSERT_RIGHT:
            $iDiff = $Target->right;
            break;
                
            default:
            die('Ungueltigen Wert alt dritten Parameter angegeben');
        }

        if ($Node->left > $iDiff)
            $iOffset = $iSpace;

        // platz schaffen
        $this->query('UPDATE ´tree´ SET `left`  = `left`  + %s WHERE `left`  > %s', array($iSpace, $iDiff));
        $this->query('UPDATE `tree` SET `right` = `right` + %s WHERE `right` > %s', array($iSpace, $iDiff));

        // Teilbaum verschieben
        $this->query(
            'UPDATE `tree` SET `left` = `left` + %s, `right` = `right` + %s WHERE `left` >= %s AND `right` <= %s',
            array(
                $iDiff + 1 - $Node->left - $iOffset,
                $iDiff + 1 - $Node->left - $iOffset,
                $Node->left  + $iOffset,
                $Node->right + $iOffset));
    
        //Rest runterdruecken
        $this->query('UPDATE `tree` SET `left`  = `left`  - %s WHERE `left`  > %s', array($iSpace, $Node->right));
        $this->query('UPDATE `tree` SET `right` = `right` - %s WHERE `right` > %s', array($iSpace, $Node->right));

        $this->query("UNLOCK TABLES");
    } 


Ach Basti, dein Code ist recht simple, hast du das geschrieben? Das bin ich garnicht gewohnt von deinen Posts. Normalerweise sind die immer so kompliziert.

Ja, der Code ist von mir, allerdings hatte ich da sicher auch ein Tutorial als Grundlage. Ich hoffe, der hier ist nun wieder etwas komplizierter *g. Hier hatte ich eben keine Vorlage zur Hand.

Basti

PS:
In der Regel wird es geschickter sein, die Knoten mit ihren Rechts- und Links-Werten in Objekten zu speichern. In meinem Kontext hier war das aber nicht sinnig, daher muss ich immer erst die Werte auslesen.

[kampfgnom]

Hallo,
bei der Umsetzung des Nested-Sets in PHP code hab ich ein Problem.
Wenn cih jetzt ein erstes Kind des Root-Punktes Setzen möchte dann mach cih das mit folgendem Code:

PHP-Code:

    public function setFirstChild ($name)
    {
        $root = $this->getRoot();
        $sql = "UPDATE tree SET rgt=rgt+2 WHERE rgt >= ".$root['rgt'].";";
        $this->data->sql($sql);
        $sql = "INSERT INTO tree (name,lft,rgt) VALUES ('".$name."',".$root['rgt'].",".$root['rgt']."+1);";
        $this->data->sql($sql);
    }
    
    public function getRoot ()
    {
        $sql = "SELECT rgt, lft FROM tree WHERE lft = 1";
        
        $root = $this->data->fetch($this->data->sql($sql));
        return $root;
    } 


Aber wenn cih jetzt einen zweiten unterpunkt des Roots erstellen möchte, klappt es mit dieser Funktion nicht.
Es ensteht dann Folgende konstruktion:

PHP-Code:

Säugetiere 1 6 // Root
Primaten 2 3
Nagetiere 4 5 


Aber es müsste eigentlich

PHP-Code:

Säugetiere 1 6
Primaten    2 5
Nagetiere   3 4 


heißen.
Was muss ich an meinem SQL-Statement ändern?

[Basti]

Was machst du? Du fragst nach dem rechten Wert des Root-Knotens. Dann erhöhst du alle Knoten, deren rechter Knoten größer oder gleich diesem rechten Root-Knoten-Wert ist. Größer gibt es nicht, da der rechte Root-Knoten-Wert ja bereits der größte Wert ist, also wird nur der rechte Wert des Root-Knotens um zwei vergrößert. In die entstandene Lücke packst du nun den neuen Knoten rein. Die Funktion müsste also genaugenommen appendRootChild() oder so heißen.

Wenn du Nagetiere als Unterknoten von Primat definieren magst (warum auch immer), dann musst du Primat als Bezugspunkt angeben und anstatt getRoot() eben eine Funktion getNode() benutzen. Dann allerdings musst du auch alle Links-Werte die größer als dem alten rechten Wert des Bezugsknotens sind um zwei hochzählen (oder wie groß der Teilbaum auch immer sei, falls mal ein Teilbaum eingebunden werden soll).

- Bestehender Baum sei TreeA, einzufügender Baum sei TreeB.
- Der Knoten in TreeA, an den TreeB als Kind angehängt werden soll, sei NodeP

- Neuen Baum ausmessen:
Wie breit ist der Baum der eingefügt werden soll? Rechter minus linker Wert des Wurzelknotens des neuen Baumes: TreeB.width = TreeB.getRoot().right - TreeB.getRoot().left + 1

- NodeP.right sei r
Das ist der jetzige rechte Wert des Eltern-Knotens. Da sich dieser ändern wird, macht es Sinn, diesen in eine Variable zu kopieren.

- Platz machen:
Damit der neue Baum reinpasst müssen nun alle Werte ab einem bestimmten Wert um die Breite des einzufügenden Baumes hochgezählt werden. Dieser bestimmte Wert ist r, der jetzige rechte Wert des Eltern-Knotens.

Nimm also alle left- und right-Werte in TreeA, die größer oder gleich r sind und erhöhe sie um TreeB.width.

- TreeB.getRoot().left muss auf r und alls anderen Werte in TreeB entsprechend hochgezählt werden. Die Differenz ist also r - TreeB.getRoot().left. Zu jedem Wert in TreeB addierst du nun also diesen Wert.

- Jetzt schiebst du die Daten von TreeB noch in TreeA rein und fertig.

Beispiel:

Baum A:

A.a  1  8
A.b  2  5
A.c  3  4
A.d  6  7

Baum B:

B.1  1  6
B.2  2  5
B.3  3  4

B soll als Kind von A.b eingefügt werden:

B.width = B.1.right - B.1.left + 1 (=6)
r = A.b.right (=5)

UPDATE A SET right = right + B.width WHERE right => r
UPDATE A SET left = left + B.width WHERE left > r (gleich gibts ja nicht)

Jetzt sieht a so aus:

A.a  1 14
A.b  2 11
A.c  3  4
A.d 12 13


B-Werte um 4 hochzählen (A.b.right - B.1.left, also 5 - 1:(

B.1  5 10
B.2  6 9
B.3  7 8

Passt genau rein:

A.a  1 14
A.b  2 11
A.c  3  4
B.1  5 10
B.2  6  9
B.3  7  8
A.d 12 13

Wenn du nur einen Knoten einfügen willst ist das natürlich einfacher, genaugenommen aber nur ein Sonderfall von dem gezeigten. Aber hier der Algo.:

- r = parent.right
- rechts = rechts + 2 wo rechts >= r
- links = links +2 wo links > r
- Knoten einfügen mit left = r und right = r+1

Also eben genau dein Code, nur mit parent anstatt root, falls nicht root der Bezugsknoten sein soll.

Basti

[kampfgnom]

Danke Basti, dein Post muss ich jetzt erstmal solange durchlesen bis ich alles verstanden habe...

Allerdings, ich wollte Nageitere nicht als Unterpunkt von Primaten einfügen sondern als Unterpunkt von Säugetiere.

Letztend endes sollte dann sowas rauskommen:

Quelle: http://www.klempert.de/nested_sets/artikel/#abb3

Jetzt werd ich erstmal deinen Post auseinander nehmen

[ex³]

Der untere Query gibt mir den Baum komplett aus. Allerdings nicht sortiert nach Name (als für jeden Ast von A-Z). Etwas an das Order By zu hängen hilft auch nichts.

PHP-Code:

    public function getDepth() {
        $res = $this->mdb2->queryAll('SELECT n.id,  n.name, COUNT(*)-1 AS ebene ' .
        'FROM kategorien AS n, kategorien AS p ' .
        'WHERE n.lft BETWEEN p.lft AND p.rgt ' .
        'GROUP BY n.lft ' .
        'ORDER BY n.lft', null, MDB2_FETCHMODE_ASSOC);

        if (PEAR :: isError($res)) {
            throw new Exception($res->getMessage() . ' - ' . $res->getUserinfo());
        }

        return $res;
    } 


Mit der folgenden Funktion kann ich zumindest die einzelnen Kategorien in einem Array gruppieren, da die einzelnen Elemente allerdings multi Arrays ist das für mich recht kompliziert zu sortieren. Ich schon einiges versucht und ich brauch mindestens 4 Schleifen, auch nicht so toll

Dachte mir ich könnte auf $ebenen ein array_multisort machen, aber ich wie ich das dafür einsetze und ob es an der Stelle überhaupt geschickt ist weiß ich nicht.

PHP-Code:

foreach ($res as $cat) {
            $ebenen[$cat['ebene']][] = $cat;
        } 


[Basti]

Zitat von kampfgnom

Allerdings, ich wollte Nageitere nicht als Unterpunkt von Primaten einfügen sondern als Unterpunkt von Säugetiere.

Dann stimmt doch dein oben zitiertes Ergebnis:

Säugetiere 1 6 // Root
Primaten 2 3
Nagetiere 4 5


Hier sind "Primaten" und "Nagetiere" direkte Kinder von "Säugetiere". "Nagetiere" ist rechter Geschwisterknoten von "Primaten".

@"ex2":
Nach welchem Wert willst du denn sortieren?

Basti

[kampfgnom]

Ach dummer Denkfehler, ich hatte nicht mehr dran gedacht, dass der Wurm ja am Blatt des Baumes von LFT gleich zum RGT wert springt...
Danke für die aufklärung

Weiter gehts...

[ex³]

Derzeit werden die ganzen Knoten glaube ich von links nach rechts aufgelistet (ORDER BY left) Demnach wird der Wurzelknoten ganz oben gelistet da er ja 1 hat.

Ich hatte aber vor das nach Namen jedes Knotens zu sortieren. Also die Hierachie soll schon beibehalten werden, allerdings auf jedem Knoten soll dies nach Namen sortiert werden ungefähr so:

Exotisches
   Mango
   Papaya
   Ananas
Aus der Heimat
   Birne
   Apfel

soll zu:

Aus der Heimat
   Apfel
   Birne
Exotisches
   Ananas
   Mango
   Papaya

[Ben]

Ich hau hier einfach noch einen Blogeintrag rein: http://ishouldbecoding.com/2007/09/1...cal-data-sets/