Baumzusammenstellung mit Hilfe von SQL (MS SQL)

[omata]

Ausgehend von diesem Thread, hier mal die Version für MsSQL...

Folgende Tabelle habe ich für den Baum angelegt...

SQL-Code:

CREATE TABLE [nodes] (
   [id] [int] NOT NULL ,
   [parentid] [int] NULL ,
   [Bezeichnung] [varchar] (50) COLLATE Latin1_General_CI_AS NOT NULL ,
   [Reihenfolge] [int] NOT NULL ,
   CONSTRAINT [PK_nodes] PRIMARY KEY  CLUSTERED 
   (
      [id]
   )  ON [PRIMARY] 
) ON [PRIMARY]

Beispielinhalt...

SQL-Code:

+----+----------+-----+-------------+
| id | parentid | bez | reihenfolge |
+----+----------+-----+-------------+
| 1  | NULL     | A   | 1           |
| 2  | 1        | AA  | 1           |
| 3  | 1        | AB  | 2           |
| 4  | NULL     | B   | 2           |
| 5  | 4        | BA  | 1           |
| 6  | 4        | BB  | 2           |
| 7  | 1        | AC  | 3           |
| 8  | 7        | ACA | 1           |
+----+----------+-----+-------------+

Dann habe ich folgende Prozedur angelegt...

SQL-Code:

CREATE PROCEDURE proc_node (@ParentID INT, @NurBlaetter BIT) AS

DECLARE @id INT
DECLARE @bezeichnung VARCHAR(1000)

DECLARE cursor_nodes CURSOR LOCAL FOR
  SELECT id, bezeichnung
  FROM nodes
  WHERE COALESCE(parentid, 0) = @ParentID
  ORDER BY reihenfolge

OPEN cursor_nodes
FETCH NEXT FROM cursor_nodes INTO @id, @bezeichnung
WHILE @@FETCH_STATUS = 0 BEGIN
  IF    (SELECT COUNT(*) FROM nodes WHERE parentid = @id) = 0
     OR @NurBlaetter = 0
  BEGIN
    INSERT INTO ##temp (ID, Bezeichnung) VALUES (@id, @bezeichnung)
  END
  EXEC proc_node @id, @NurBlaetter

  FETCH NEXT FROM cursor_nodes INTO @id, @bezeichnung
END

CLOSE cursor_nodes
DEALLOCATE cursor_nodes

und dann diese Prozedur...

SQL-Code:

CREATE PROCEDURE proc_main (@ParentID INT, @NurBlaetter BIT) AS

CREATE TABLE ##temp (
  ID  INT,
  Bezeichnung VARCHAR(1000)
)

EXEC proc_node @ParentID, @NurBlaetter
SELECT *
FROM ##temp

DROP TABLE ##temp

Ausgabe des gesamten Baums...

SQL-Code:

EXEC proc_main 0, 0

+------+-------------+
| ID   | Bezeichnung |
+------+-------------+
| 1    | A           |
| 2    | AA          |
| 3    | AB          |
| 7    | AC          |
| 8    | ACA         |
| 4    | B           |
| 5    | BA          |
| 6    | BB          |
+------+-------------+

Ausgabe aller Elemente und Unterelemente, die zum Element mit der ID = 1 gehören...

SQL-Code:

EXEC proc_main 1, 0

+------+-------------+
| ID   | Bezeichnung |
+------+-------------+
| 2    | AA          |
| 3    | AB          |
| 7    | AC          |
| 8    | ACA         |
+------+-------------+

Ausgabe des gesamten Baums (nur die Blätter)...

SQL-Code:

EXEC proc_main 0, 1

+------+-------------+
| ID   | Bezeichnung |
+------+-------------+
| 2    | AA          |
| 3    | AB          |
| 8    | ACA         |
| 5    | BA          |
| 6    | BB          |
+------+-------------+

Ausgabe aller Blatt-Elemente, die zum Element mit der ID = 1 gehören...

SQL-Code:

EXEC proc_main 1, 1

+------+-------------+
| ID   | Bezeichnung |
+------+-------------+
| 2    | AA          |
| 3    | AB          |
| 8    | ACA         |
+------+-------------+

Lieder ist die maximale Rekursionstiefe bei MsSQL 32, tiefere Baumstrukturen sind dadurch leider nicht möglich. (Bei MySQL kann bzw. muss man diesen Wert manuell setzen)

Gruss
Thorsten

[edit=CalganX]Titel und Klassifizierung angepasst. Mfg, CalganX[/edit]

[omata]

Hier mal ein Beispiel wie man einen Baum in einen TreeView einlesen kann, mit nur einer Datenbankabfrage...

Dafür sind allerdings noch ein paar kleine Änderungen an obiger Struktur nötig...

SQL-Code:

CREATE PROCEDURE proc_node (@ParentID INT, @Level INT, @NurBlaetter BIT) AS

DECLARE @id INT
DECLARE @bezeichnung VARCHAR(1000)

DECLARE cursor_nodes CURSOR LOCAL FOR
  SELECT id, bezeichnung
  FROM nodes
  WHERE COALESCE(parentid, 0) = @ParentID
  ORDER BY reihenfolge

SET @level = @level + 1

OPEN cursor_nodes
FETCH NEXT FROM cursor_nodes INTO @id, @bezeichnung
WHILE @@FETCH_STATUS = 0 BEGIN
  IF    (SELECT COUNT(*) FROM nodes WHERE parentid = @id) = 0
     OR @NurBlaetter = 0
  BEGIN
    INSERT INTO ##temp (ID, Level, Bezeichnung) VALUES (@id, @level, @bezeichnung)
  END
  EXEC proc_node @id, @level, @NurBlaetter

  FETCH NEXT FROM cursor_nodes INTO @id, @bezeichnung
END

CLOSE cursor_nodes
DEALLOCATE cursor_nodes

SQL-Code:

CREATE PROCEDURE proc_main (@ParentID INT, @NurBlaetter BIT) AS

CREATE TABLE ##temp (
  ID  INT,
  Level INT,
  Bezeichnung VARCHAR(1000)
)

EXEC proc_node @ParentID, 0, @NurBlaetter
SELECT *
FROM ##temp

DROP TABLE ##temp

Datenbankzugriff über DBExpress...

Delphi-Quellcode:

procedure fillTreeview(Tree:TTreeview; SQLConnection:TSQLConnection);

  procedure fill(Level:byte; ANode:TTreeNode; SDS:TSimpleDataSet);
  var abbruch:boolean;
      Node:TTreeNode;
  begin
    abbruch:=false;
    while not SDS.Eof and not abbruch do begin
      Node:=Tree.Items.AddChild(
        ANode,
        SDS.FieldByName('bezeichnung').AsString
      );
      SDS.Next;
      if SDS.FieldByName('level').AsInteger > Level then
        fill(Level+1, Node, SDS);
      if SDS.FieldByName('level').AsInteger < Level then
        abbruch:=true;
    end;
  end;

var SDS:TSimpleDataSet;
begin
  Tree.Items.Clear;
  SDS:=TSimpleDataSet.Create(nil);
  try
    SDS.Connection:=SQLConnection;
    SDS.DataSet.CommandType:=ctStoredProc;
    SDS.DataSet.CommandText:='proc_main';
    SDS.DataSet.ParamByName('parentid').AsInteger:=0;
    SDS.DataSet.ParamByName('nurblaetter').AsBoolean:=false;
    SDS.Open;
    fill(SDS.FieldByName('level').AsInteger, nil, SDS);
    SDS.Close;
  finally
    SDS.free;
  end;
end;

Aufruf...

Delphi-Quellcode:

procedure TForm.ButtonClick(Sender: TObject);
begin
  fillTreeview(TreeView, SQLConnection);
end;

Gruss
Thorsten

[alzaimar]

Das ist ok, dauert aber zu lange und versagt bei tiefen Bäumen.
Nimm folgenden Ansatz:
1. Am Anfang enthält die Resultatmenge genau eine Zeile 'ID' und 'ParentID' des Knotens, dessen Unterbaum geliefert werden soll
2. Solange die Resultatmenge noch nicht abgearbeitet ist (Ja, ein Cursor)
2.1 Füge ALLE Knoten der Baumtabelle in die Resultatmenge mit ID = CurrentParentID
2.2 Gehe zum nächsten Eintrag der Resultatmenge

Mit jedem Durchlauf wächst die Resultatmenge also, bis eben keine Blätter mehr gefunden werden

SQL-Code:

Create Procedure ListSubTree @ID int
as
set nocount on
declare @ChildID int,
declare @Table Table (
  ID  INT,
  ParentID INT,
  Bezeichnung VARCHAR(1000)
)
-- 1.Zeile in die Tabelle
--
insert into @Table
  select @ID, ParentID from TreeTable where ID = @ID

Declare c Cursor local for select ID from @Table
open c
fetch next from c into @ChildID 
while @@Fetch_status = 0 begin
--
-- Mit jedem Schleifendurchlauf werden in einem Abwasch ALLE Kindknoten eingefügt
--
  insert into @Table
    select ID,ParentID from TreeTable where ParentID = @ChildID 
  fetch next from c into @ChildID 
end
close c
deallocate c
set nocount off
select * from @Table

Ich liefere noch den ParentNode aller Einträge, damit der Baum auch aufgebaut werden kann. Wenn man vorher noch einen Clustered Index auf die ParentID legt, und @Table nach dieser Spalte sortiert zurückliefert, kann man den Baum in linearer Zeit in einer TTreeView konstruieren und muss nicht für jeden Knoten den Elternknoten suchen. Das ist bei sehr großen Bäumen durchaus nützlich.

Das sollte funktionieren, ist aber nicht getestet. Table-Variablen funktionieren ab MSDE2000. Mit der 2005'er kann man auch rekursive Joins machen, die hab ich aber nicht. Es gibt darüber einen Artikel auf www.sqlcentral.com (sowieso ganz nett, die Site).

[EDIT] Nochwas: SQL ist mengenbasiert, denke also immer in Mengen, nie in Records! [/EDIT]

[generic]

hier eine variante ohne cursor:

http://www.falafel.com/Blogs/tabid/1...6/Default.aspx

[omata]

Ich habe gerade festgestellt, dass der angegebene Link nicht mehr geht.

Hier ein Beispiel mit Ideen von da...

SQL-Code:

CREATE TABLE [Tree] (
   NodeID int NOT NULL,
   ParentNodeID int NULL,
   NodeName varchar (50) COLLATE Latin1_General_CI_AS NOT NULL,
   Reihenfolge int NULL,
   CONSTRAINT PK_Tree PRIMARY KEY CLUSTERED (NodeID) ON PRIMARY,
   CONSTRAINT FK_Tree_Tree FOREIGN KEY (ParentNodeID) REFERENCES Tree (NodeID)
) ON PRIMARY

SQL-Code:

CREATE PROCEDURE GetSortedSubTree(@NodeID INT)
AS
DECLARE @IDS   TABLE (id INT PRIMARY KEY, Depth INT, NodePath VARCHAR(1000))
DECLARE @Depth INT
DECLARE @Done  BIT

SET @Depth = 1
SET @Done = 0

INSERT @IDS(id, Depth, NodePath) 
SELECT NodeID, @Depth, CONVERT(VARCHAR(1000), Reihenfolge)
FROM Tree 
WHERE NodeID = @NodeID

IF @@ROWCOUNT = 0 SET @Done = 1 
WHILE @Done = 0 BEGIN
  SET @Depth = @Depth + 1
  INSERT @IDS(id, Depth, NodePath)
  SELECT NodeID, @Depth, ids.NodePath + '|' + CONVERT(VARCHAR(1000), Reihenfolge)
  FROM Tree t
  INNER JOIN @IDS ids 
    ON ids.id = t.ParentNodeID 
  WHERE ids.Depth = @Depth-1
  IF @@ROWCOUNT = 0 SET @Done = 1 
END

SELECT t.NodeID, t.NodeName, ids.Depth, ids.NodePath
FROM Tree t
INNER JOIN @IDS ids 
  ON ids.id = t.NodeID
ORDER BY ids.NodePath

Gruss
Thorsten

[Jelly]

Zitat von omata:

Lieder ist die maximale Rekursionstiefe bei MsSQL 32, tiefere Baumstrukturen sind dadurch leider nicht möglich.

Das stimmt so nicht. Im SQL Server 2005 ist die Rekursionstiefe standardmässig auf 100, kann aber sehr leicht geändert werden:

select * from Tabelle Option (Maxrecursion 1000) Maximal sind 32767 Verschachtelung möglich. Das sollte reichen