E-learn.ro
Panou utilizatori
Utilizator Parola
Creeaza cont nou    Recupereaza parola
Login
Newsletter
Introdu adresa ta de email
Inscrie-te
Inchide panoul de utilizatori
Add to Google

Tutoriale MySQL

Descarca toolbar

Toolbar E-learn.ro Facebook Twitter

BAZE DE DATE  /  MySQL  /  Diverse (3)

Arbori si ierarhii in SQL

12.02.2009
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.

Total vizualizari: 7687 7687 afisari   |   Comentarii  0   |   Rating   |   (2 voturi)   |   Timp necesar: 30 min 30 min   |   Nivel de cunostiinte necesar: Avansat  Avansat

Sursa:  www.sqlteam.com  
Autor:  Rob Volk
Adauga la tutoriale favorit Adauga la tutoriale favorite
Pagina:
1
comenteaza printeaza

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:

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:

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:

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:

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:

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:

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;

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:

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 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.

Pagina:
1
comenteaza printeaza
Alte tutoriale MySQL:
Noteaza acest tutorial
Rating tutorial
 
(2 voturi)
Pentru a nota acest tutorial, trebuie sa fii logat!
Posteaza un comentariu
Pentru a posta un comentariu, trebuie sa fii logat!
0 TOP UTILIZATORI* 0 0
Tutoriale scrise de claibornelara
claibornelara Rang utilizator claibornelara - Incepator
4175
Tutoriale scrise de ellarichards
ellarichards Rang utilizator ellarichards - Incepator
4085
Tutoriale scrise de kheops
kheops Rang utilizator kheops - Mediu
4084
Tutoriale scrise de mcuemica
mcuemica Rang utilizator mcuemica - Incepator
4055
Tutoriale scrise de emonclercheap
emonclercheap Rang utilizator emonclercheap - Incepator
3875
* Acest top reprezinta punctajele acumulate in ultimele 30 de zile.
XML COREL DRAW Lightroom CSS RoR Illustrator Bridge Word XHTML Swift 3D AJAX Action Script Flash Java MySQL SWF HTML PSD PHP Outlook StyleSheet Fireworks Excel Dreamweaver SEO Ruby on Rails Fotografie Gimp Vista Python Sony Vegas Verilog Photoshop Javascript JSON Powerpoint
Promovare:
Daca faci parte din comunitatea E-learn.ro si doresti promovarea acesteia, poti accesa pagina de promovare.
Arhiva newsletter:
Daca ai ratat un numar mai vechi, sau vrei sa revezi care au fost noutatile E-learn.ro la un moment dat, poti accesa arhiva de newslettere.
  Copyright © 2008-2013 E-LEARN.ro. Toate drepturile rezervate. Termeni si conditii.
Conceput si realizat de Neokinetics Software