Auf Baumstruktur vom Blatt aus per SP zugreifen

[xaromz]

Hallo,

ich möchte mir eine SP bauen, die auf eine Baumstruktur zugreift und von einem angegebenen Knoten nach oben zur Wurzel geht. Dabei sollen aus einer anderen Tabelle zu jedem besuchten Knoten Daten ausgelesen und zurückgegeben werden.
Ich stell mal die Tabellen schematisch dar:

SQL-Code:

CREATE TABLE Tree ( 
    ID           INTEGER NOT NULL, 
    PARENTID     INTEGER
);

SQL-Code:

CREATE TABLE TreeData ( 
    ID           INTEGER NOT NULL, 
    TreeID       INTEGER,
    Data         BLOB
);

Zu jedem Knoten können mehrerer Datensätze in der zweiten Tabelle vorhanden sein.

Ich möchte den Baum aufwärts gehen und zum Schluss eine Ergebnismenge mit sämtlichen Daten, die ich unterwegs finde, erhalten.
Beispiel:

Code:

Tree
ID | PARENTID
1  | 0
2  | 1
3  | 2
4  | 1
5  | 4
6  | 5

Code:

TreeData
ID | TreeID | Data
1  | 1      | A
2  | 3      | B
3  | 4      | C
4  | 4      | D
5  | 5      | E
6  | 6      | F

Wenn ich also den Knoten 6 übergebe, möchte ich als Ergebnis die Werte F, E, D, C, A erhalten.

Ich hoffe, da kann mir jemand helfen, ich bin in Sachen SP ziemlich eingerostet.

Gruß
xaromz

[Trigger2003]

Hallo,

mit C# habe ich leider wenig Erfahrung, Deine SQL-Problemstellung scheint mir aber ein Fall für "Nested Sets" zu sein. Google mal danach...

Gruß
Trigger

[Die Muhkuh]

Dazu gab es erst vor kurzem einen Thread. Vielleicht hilft der Dir weiter.

[xaromz]

Hallo,

Zitat:

Zitat von Trigger2003

mit C# habe ich leider wenig Erfahrung, Deine SQL-Problemstellung scheint mir aber ein Fall für "Nested Sets" zu sein. Google mal danach...

Nested Sets sieht tatsächlich sehr interessant aus. Danke für den Tipp. C# ist übrigens im Zusammenhang mit SP eher irrelevant :wink: .

Zitat:

Zitat von Die Muhkuh

Dazu gab es erst vor kurzem einen Thread. Vielleicht hilft der Dir weiter.

Leider hilft mir der Thread nicht weiter, da dort sehr schnell auf PHP ausgewichen wird. Ich will das ja komplett innerhalb des DBMS erledigen.

Gruß
xaromz

[omata]

Schade, das du dort meinem Link nicht gefolgt bist.

SQL-Code:

CREATE TABLE Tree (
  ID       INTEGER,
  PARENTID INTEGER,
  CONSTRAINT PK_Tree PRIMARY KEY (ID),
  CONSTRAINT FK_Tree FOREIGN KEY (PARENTID) REFERENCES Tree (ID)
);

CREATE TABLE TreeData (
  ID     INTEGER,
  TreeID INTEGER,
  Data   BLOB,
  CONSTRAINT PK_TreeData PRIMARY KEY (ID),
  CONSTRAINT FK_TreeData FOREIGN KEY (TreeID) REFERENCES Tree (ID)
);

Tree:

Code:

ID | PARENTID
1  | NULL
2  | 1
3  | 2
4  | 1
5  | 4
6  | 5

Ich würde für die Wurzelknoten den Parentwert NULL benutzen, dann ist auch eine saubere SQL-Definition (siehe oben) möglich.

TreeData:

Code:

ID | TreeID | Data
1  | 1      | A
2  | 3      | B
3  | 4      | C
4  | 4      | D
5  | 5      | E
6  | 6      | F

SP:

SQL-Code:

CREATE PROCEDURE `proc_GetParents`(NodeID INTEGER)
BEGIN
  DECLARE _Depth INT DEFAULT 1;
  DECLARE _Done INT DEFAULT 0;

  CREATE TEMPORARY TABLE tmpTable (
    id INT PRIMARY KEY, parentid INT, Depth INT, NodePath VARCHAR(1000)
  ) TYPE=HEAP;
  CREATE TEMPORARY TABLE tmpTable2 (
    id INT PRIMARY KEY, parentid INT, Depth INT, NodePath VARCHAR(1000)
  ) TYPE=HEAP;

  INSERT tmpTable (id, parentid, Depth, NodePath)
  SELECT id, parentid, _Depth, id
  FROM tree
  WHERE id = NodeID;
  IF ROW_COUNT() = 0 THEN
    SET _Done = 1;
  END IF;
  WHILE _Done = 0 DO
    SET _Depth = _Depth + 1;
    INSERT tmpTable2 (id, parentid, Depth, NodePath)
    SELECT t.id, t.parentid, _Depth, CONCAT(x.NodePath, '|', t.id)
    FROM tree t
    INNER JOIN tmpTable x
      ON t.id = x.parentid
    WHERE x.Depth = _Depth-1;
    IF ROW_COUNT() = 0 THEN
      SET _Done = 1;
    END IF;
    INSERT tmpTable
    SELECT *
    FROM tmpTable2;
    DELETE FROM tmpTable2;
  END WHILE;

  SELECT t.id, t.parentid, x.Depth, x.NodePath, td.data
  FROM tree t
  INNER JOIN tmpTable x
    ON t.id = x.id
  LEFT JOIN treedata td
    ON t.id = td.treeid
  ORDER BY x.NodePath DESC;

  DROP TEMPORARY TABLE tmpTable;
  DROP TEMPORARY TABLE tmpTable2;
END

Aufruf:

SQL-Code:

CALL proc_GetParents(6);

Ergebnis:

Code:

ID PARENTID Depth  NodePath Data
1  NULL     4      6|5|4|1  A
4  1        3      6|5|4    C
4  1        3      6|5|4    D
5  4        2      6|5      E
6  5        1      6        F

[xaromz]

Hallo,

Zitat:

Zitat von omata

Schade, das du dort meinem Link nicht gefolgt bist.

:oops: hatte ich doch glatt übersehen.

Danke für Deine Hilfe, die SP sieht genau nach dem aus, wass ich wollte :thumb: .

Gruß
xaromz