Arbori si ierarhii in SQL

0

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:

EmployeeID

Name

BossID

1001

Denis Eaton-Hogg

NULL

1002

Bobbi Flekman

1001

1003

Ian Faith

1002

1004

David St. Hubbins

1003

1005

Nigel Tufnel

1003

1006

Derek Smalls

1003

Organigrama modelata de tabelul de mai sus are urmatoarea structura:

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:

Si vei obtine:

BigBoss

Boss

Employee

Denis Eaton-Hogg

Bobbi Flekman

Ian Faith

Bobbi Flekman

Ian Faith

David St. Hubbins

Bobbi Flekman

Ian Faith

Nigel Tufnel

Bobbi Flekman

Ian Faith

Derek Smalls

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:

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:

Node

ParentNode

EmployeeID

Depth

Lineage

100

NULL

1001

NULL

NULL

101

NULL

1002

NULL

NULL

102

NULL

1003

NULL

NULL

103

NULL

1004

NULL

NULL

104

NULL

1005

NULL

NULL

105

NULL

1006

NULL

NULL

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:

Si vei obtine:

Node

ParentNode

EmployeeID

Depth

Lineage

100

NULL

1001

NULL

NULL

101

100

1002

NULL

NULL

102

101

1003

NULL

NULL

103

102

1004

NULL

NULL

104

102

1005

NULL

NULL

105

102

1006

NULL

NULL

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;

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

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

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:

Node

ParentNode

EmployeeID

Depth

Lineage

100

NULL

1001

0

/

101

100

1002

1

/100/

102

101

1003

2

/100/101/

103

102

1004

3

/100/101/102/

104

102

1005

3

/100/101/102/

105

102

1006

3

/100/101/102/

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 singurSELECT!

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.

Leave A Reply