Reprezentowanie struktur drzewiastych w SQL Server

Czasami istnieje potrzeba reprezentacji drzewa za pomocą tabeli. Klasycznym przykładem jest hierarchia pracowników w firmie. Bardzo popularną reprezentacją jest:

ID_EMPLOYEE int,
ID_MANAGER int,
Title nvarchar(50).

ID_EMPLYOEE jest oczywiście kluczem głównym, z kolei ID_MANAGER stanowi klucz obcy wskazujący na ID_EMPLOYEE. Przykład wypełnionej tabeli:

ID_EMPLOYEE ID_MANAGER Title
1 NULL Project Manager
2 1 Senior Software Developer
3 2 Junior Developer
4 1 Senior database developer

Rozwiązanie jak najbardziej poprawne. Wykorzystując jednak SQL Server możemy zrobić to w sposób bardziej elegancki, wydajniejszy oraz w znaczący sposób ułatwiający przyszłe operacje na strukturze.

Służy do tego nowy typ kolumny – HIERARCHY ID. Nowa tabela powinna zatem zawierać następujące kolumny:

ID int,
Node hierarchyid,
Title nvarchar(50).

HierarchyID jest specjalnym typem stworzonym dla struktur hierarchicznym. Za pomocą tego typu można zbudować m.in. wspomniane drzewo. Typ się charakteryzuje wysokim stopniem kompresji. Operację na stworzonej tabeli będą zatem dużo efektywniejsze. Spróbujmy dodać pierwszy wiersz – korzeń:

insert into Tree (Node,Title) Values(hierarchyid::GetRoot(),'Project Manager');

Klucz główny(ID) pomijamy ponieważ jest on typu IDENTITY (autoinkrementacja). Warto jednak przyjrzeć się metodzie statycznej GetRoot. Zwraca ona oczywiście identyfikator korzenia. Następnie dodajemy pierwsze dziecko (Senior Software Developer):

DECLARE @Manager hierarchyid           
set @Manager=hierarchyid::GetRoot();
insert into Tree (Node,Title) Values(@Manager.GetDescendant(null,null),'Senior Software Developer');

Najpierw pobieramy identyfikator korzenia a potem tworzony jest potomek na podstawie funkcji GetDescendant. Funkcja przyjmuje dwa parametry (child1, child2). Warto więc przyjrzeć się jej działaniu dokładniej. W zależności od dostarczonych argumentów, GetDescendant zwraca różne wyniki:

  1. Jeśli obydwa parametry wejściowe równe są NULL, funkcja zwraca bezpośredniego potomka. Jeśli rodzic równy jest /1 wtedy zwrócony potomek będzie wynosił /1/1.
  2. Jeśli child1 jest różny od NULL, funkcja zwraca potomka większego od child1 czyli utworzony węzeł będzie bratem child1. Załóżmy, że parent==/1, child==/1/1 to wtedy zwrócona wartość będzie wynosić /1/2.
  3. Jeśli obydwa parametry są różne od NULL, wtedy funkcja zwraca węzeł znajdujący się pomiędzy child1 a child2. Załóżmy, że parent==/1, child1==/1/1, child2==/1/2 to wynikowy węzeł==/1/1.1.

Jeśli child1 nie jest potomkiem parent, wtedy wyrzucany jest wyjątek. Pozostałe przypadki wyglądają analogicznie.

Bazując na powyższych warunkach spróbujmy dodać węzeł dla “Senior database developer”:

DECLARE @Manager hierarchyid   
DECLARE @FirstChild hierarchyid;        
set @Manager=hierarchyid::GetRoot();
set @FirstChild=@Manager.GetDescendant(null,null);

insert into Tree (Node,Title) Values(@Manager.GetDescendant(@FirstChild,null),'Senior database developer');

Pobierany jest korzeń oraz pierwszy potomek.  Konstrukcja może wydawać się dziwaczna (po co podawać FirstChild?) jednak należy pamiętać, że hiearchyid został utworzony dla dowolnych struktur – nie tylko drzew. Dodanie Junior Developer’a nie powinno już zaskakiwać:

DECLARE @Manager hierarchyid   
DECLARE @FirstChild hierarchyid;        
set @Manager=hierarchyid::GetRoot();
set @FirstChild=@Manager.GetDescendant(null,null);

insert into Tree (Node,Title) Values(@FirstChild.GetDescendant(null,null),'Junior Developer');

W następnym poście przedstawię kilka operacji na hierarchyid. Wtedy dopiero okaże się jak bardzo hierarchyid ułatwia życie programiście. Na zakończenie screen z utworzonej struktury:

image