Arbori si ierarhii in SQL

Ierarhiile cum ar fi arborii, categoriile dintr-un forum, organigramele si altele asemanatoare sunt uneori dificil de stocat in tabele SQL.....si este de obicei si mai dificil sa extragi ierarhia o data ce ai stocat-o. In acest tutorial vei putea citi despre o metoda usor de inteles si de intretinut, care iti ofera o intreaga ierarhie (sau orice parte a sa) intr-un mod rapid si facil.

In timp ce XML manevreaza datele ierahice destul de bine, SQL-ul relational nu reuseste. Exista cateva metode diferite pentru a modela o structura ierarhica. Cea mai comuna si obisnuita este cunoscuta sub numele de model de adiacenta deoarece utilizeaza referinte la randuri din acelasi tabel:

Organigrama modelata de tabelul de mai sus are urmatoarea structura:

Denis Eaton-Hogg
  Bobbi Flekman
    Ian Faith
      David St. Hubbins
      Nigel Tufnel
      Derek Smalls

Dupa cum se poate observa, informatia despre parinte (sef) este stocata pe acelasi rand cu cea despre copil (angajat), intr-o coloana adiacenta (BossID). Este un model destul de simplu, usor de inteles de catre oricine, fara a necesita cunoasterea unor teorii relationale complexe. Poti afla cu usurinta cine este seful unei persoane sau colegii acesteia interogand coloana BossID.

Problema incepe cand vrei sa listezi cateva nivele ale unei ierarhii. Pentru a afla seful sefului, trebuie sa unesti tabelul Employees cu el insusi, astfel:

SELECT BigBoss.Name BigBoss, Boss.Name Boss, Employees.Name Employee
FROM Employees 
INNER JOIN Employees AS Boss ON Employees.BossID=Boss.EmployeeID
INNER JOIN Employees BigBoss ON Boss.BossID=BigBoss.EmployeeID

Si vei obtine:

In mod similar, pentru a afla fiecare nivel al organigramei ar trebui sa unesti tabelul cu el insusi ... o optiune nu foarte atractiva daca ai 5 sau mai multe niveluri. Ar fi minunat daca acest lucru s-ar putea realiza automat. Tipul acesta de uniune poarta numele de join recursiv . Desi unele baze de date il accepta (Oracle are sintaxa CONNECT BY), SQL Server nu este una dintre ele.

Pentru a obtine ierarhia, poti defini o procedura stocata care ruleaza printr-un tabel adiacent. Chiar daca functioneaza, este o metoda procedurala care necesita o stiva (utilizarea unui tabel temporar) si poate dura ceva timp pentru a parcurge ierarhii vaste. De asemenea, rezultatul este afisat, nu returnat, astfel incat pentru a-l utiliza sub forma de tabel/ interogare, trebuie sa retii datele intr-un alt tabel temporar.

Oricum, una dintre problemele cu structurile arborescente este complexitatea mult prea mare pentru a efectua sarcini relativ simple, cum ar fi adaugarea, stergerea sau mutarea de noduri in arbore. Chiar si gasirea supraveghetorului imediat superior unui angajat sau subordonatii acestuia necesita 2 auto-join-uri si o subinterogare!

Desi seturile de date ierarhice au o logica foarte atragatoare, fiind usor de efectuat operatii complicate cu arbori asupra acestora, ele sunt mai putin intuitive decat modelul de adiacenta. Este mai dificil de vizualizat o ierarhie sau o organigrama cu ajutorul acestora.

Deci, cum sa reprezinti o ierarhie, utilizand adiacenta si evitand recursivitatea atunci cand este posibil? Este destul de usor de fapt ..o construiesti si o stochezi in tabel!

Aceasta este definitia tabelului pentru structura de tip arbore:

CREATE TABLE Tree (
Node int NOT NULL IDENTITY(100, 1),
ParentNode int, 
EmployeeID int NOT NULL,  
Depth tinyint,
Lineage varchar(255) )

Tabelul Tree a fost creat separat din cateva motive bine intemeiate pe care le vom discuta mai tarziu, dar acum poti adauga pur si simplu coloanele Depth (adancime) si Lineage (descendenta) la tabelul Employees de mai sus si poti inlocui BossID cu ParentNode. (Nu am utilizat o coloana pentru nume deoarece nu influenteaza structura arborelui, iar daca ai nevoie de ea, o poti crea mai tarziu). Termenii nod si descendenta pot parea nefamiliari dar am vrut sa-i generalizez pe cei de "copil", "parinte" si "ierarhie".

Pe baza tabelului Employees, iata cum poate fi completat tabelul Tree:

Primul lucru care trebuie facut este popularea nodurilor parinte, ceea ce nu este necesar daca folosesti un singur tabel, dar este oricum usor de facut:

UPDATE T SET T.ParentNode=P.Node
FROM Tree T 
INNER JOIN Employees E ON T.EmployeeID=E.EmployeeID
INNER JOIN Employees B ON E.BossID=B.EmployeeID
INNER JOIN Tree P ON B.EmployeeID=P.EmployeeID

Si vei obtine:

Aceasta operatie trebuie efectuata doar o singura data si apoi nu mai este nevoie sa mentii coloana BossID in tabelul Employees. Partea urmatoare este gasirea nodului radacina al arborelui, cunoscut si ca nivelul cel mai de sus, sau marele sef din organigrama. Acest nod nu are parinte (Null), deci vom incepe de acolo si vom stabili coloana Lineage ca radacina;

UPDATE Tree SET Lineage='/', Depth=0 WHERE ParentNode Is Null

O data ce ai terminat, poti actualiza randurile care sunt copiii imediati ai nodului radacina:

UPDATE T SET T.depth = P.Depth + 1, 
T.Lineage = P.Lineage + Ltrim(Str(T.ParentNode,6,0)) + '/' 
FROM Tree AS T 
INNER JOIN Tree AS P ON (T.ParentNode=P.Node) 
WHERE P.Depth>=0 
AND P.Lineage Is Not Null 
AND T.Depth Is Null

De fapt putem scrie o bucla while pentru a actualiza toti copiii/ nepotii etc. din arbore:

WHILE EXISTS (SELECT * FROM Tree WHERE Depth Is Null) 
UPDATE T SET T.depth = P.Depth + 1, 
T.Lineage = P.Lineage + Ltrim(Str(T.ParentNode,6,0)) + '/' 
FROM Tree AS T 
INNER JOIN Tree AS P ON (T.ParentNode=P.Node) 
WHERE P.Depth>=0 
AND P.Lineage Is Not Null 
AND T.Depth Is Null

Nu te ingrijora cu privire la bucla, ruleaza doar o data pentru fiecare nivel al ierarhiei...10 bucle pentru 10 nivele sau generatii. Pentru o corporatie, 10 layere de management reprezinta ceva complex; in cazul unui arbore genealogic, poti afla descendentii unei familii americane pana la Razboiul de Independenta! Si in conditii normale, ar trebui sa rulezi aceasta procedura o singura data. Rezultatul final este:

Vei observa ca pentru fiecare nod, este memorata intreaga descendenta pana la radacina. Aceasta inseamna ca gasirea sefului cuiva, sau a sefului sefului, nu necesita vreun join sau recursivitate pentru a crea o lista indentata. De fapt, poate fi obtinuta cu un singur SELECT!

SELECT Space(T.Depth*2) + E.Name AS Name
FROM Employees E 
INNER JOIN Tree T ON E.EmployeeID=T.EmployeeID
ORDER BY T.Lineage + Ltrim(Str(T.Node,6,0))

Daca pastrezi totul intr-un singur tabel nici nu vei avea nevoie de JOIN! Coloana Depth este utila pentru efectuarea indentarii cu functia Space(). Utilizand ORDER BY Lineage, organigrama va fi sortata corespunzator, cu fiecare serie subordonata aflata sub parintele sau. Ordinea de sortare este mentinuta prin valorile ParentNode si poate fi schimbata usor prin actualizarea valorii nodului. Introducerea sau stergerea unui nou nod nu afecteaza restul arborelui. Coloana care retine descendenta poate fi actualizata in mod automat, deci mutarea sau promovarea unui nod este ceva banal.