(20.09.2018)

Baumstrukturen sind in der Programmierung in vielen Variationen vorhanden, z.B. in Treeviews oder Menüs. Die Speicherung der Knotendaten in einer Datenbank ist dabei einfacher als die Abfrage: mittels eines "Parent"-Feldes kann der Primärschlüssel des übergeordneten Elements angegeben werden. Bei der Erzeugung der Baumstruktur dagegen tritt das Problem auf, daß die Rückgabemenge sinnvollerweise so sortiert ist, daß zunächst die oberste Ebene zurückgeliefert wird, dann die zweite, dann die dritte usw. und das sinnvollerweise Kreisstrukturen verhindert werden.

In einer Abfrage läßt sich das ganz leicht mittels Tabellenvariablen realisieren. Dazu werden aus der Quelldatenmenge zunächst die Tupel ausgewählt, die keinen Parentknoten haben. Danach die, deren Parentknoten in der vorherigen Auswahl war usw.:

declare @nodes table(id int,item varchar(10),parent int);
insert into @nodes(id,item,parent)
values(1,'1',null)
     ,(2,'2',null)
     ,(3,'3',null)
     ,(4,'4',1)
     ,(5,'5',7)
     ,(6,'6',4)
     ,(7,'7',5)
     ,(8,'8',null)
     ,(9,'9',null);

declare @stageres table(id int,item varchar(10),parent int);
declare @temp  table(id int,item varchar(10),parent int);
declare @result table(id int,item varchar(10),parent int,[level] int);

declare @level int;
set @level=0;

insert into @stageres(id,item,parent) select id,item,parent from @nodes where parent is null;
while exists (select * from @stageres) Begin
    insert into @result(id,item,parent,[level]) select id,item,parent,[level]=@level from @stageres;
    delete from @temp;
    insert into @temp(id,item,parent) select nodes.id,nodes.item,nodes.parent from @stageres stageres inner join @nodes nodes on stageres.id=nodes.parent;
    delete from @stageres;
    insert into @stageres(id,item,parent) select ID,item,parent from @temp;
    set @level=@level+1;
End
select * from @result order by [level];

Ausgabe:

id item parent level
1 1 NULL 0
2 2 NULL 0
3 3 NULL 0
8 8 NULL 0
9 9 NULL 0
4 4 1 1
6 6 4 2

Dabei wird die Schleife zwischen den Nodes 5 und 7 nicht mit ausgegeben, weil es bei einer Schleife schlichtweg keinen Knoten ohne Parent geben kann.