Există mai multe moduri de a stoca un arbore într-o tabelă. Cel mai uzual mod este numit „Adjacency list” şi un exemplu ar arăta astfel: 

 

CREATE TABLE Salariati (
      ID int PRIMARY KEY,
      Nume nvarchar(20) NOT NULL,
      Prenume nvarchar(30) NOT NULL,
      ID_Sef int NULL REFERENCES Salariati (ID)
)

INSERT INTO Salariati VALUES (1, 'Popescu', 'Ion', NULL)
INSERT INTO Salariati VALUES (2, 'Ionescu', 'George', 1)
INSERT INTO Salariati VALUES (3, 'Vasilescu', 'Marian', 1)
INSERT INTO Salariati VALUES (4, 'Vasilescu', 'Mihai', 3)
INSERT INTO Salariati VALUES (5, 'Popescu', 'Marian', 3)
INSERT INTO Salariati VALUES (6, 'Popescu', 'Vasile', 4)
 

Dacă vrem să aflăm lista tutor subordonaţilor (direcţi sau indirecţi) ai unei anumite persoane, putem folosi o funcţie de genul următor:

 

CREATE FUNCTION Subordonati(@ID int)
RETURNS @Rezultat TABLE (
      ID int PRIMARY KEY,
      Nume nvarchar(20) NOT NULL,
      Prenume nvarchar(30) NOT NULL
) AS BEGIN
      INSERT INTO @Rezultat
      SELECT ID, Nume, Prenume FROM Salariati
      WHERE ID_Sef=@ID 

      WHILE @@ROWCOUNT<>0 BEGIN
            INSERT INTO @Rezultat
            SELECT ID, Nume, Prenume FROM Salariati
            WHERE ID_Sef IN (SELECT ID FROM @Rezultat)
            AND ID NOT IN (SELECT ID FROM @Rezultat)
      END 

      RETURN
END

GO

SELECT * FROM Subordonati(3) 

 

Un alt model de a stoca un arbore este cel numit „Materialized paths”, care ar fi ceva de genul următor: 

 

CREATE TABLE Salariati (
      ID int PRIMARY KEY,
      Nume nvarchar(20) NOT NULL,
      Prenume nvarchar(30) NOT NULL,
      Path varchar(10)
) 

INSERT INTO Salariati VALUES (1, 'Popescu', 'Ion', 'A')
INSERT INTO Salariati VALUES (2, 'Ionescu', 'George', 'AA')
INSERT INTO Salariati VALUES (3, 'Vasilescu', 'Marian', 'AB')
INSERT INTO Salariati VALUES (4, 'Vasilescu', 'Mihai', 'ABA')
INSERT INTO Salariati VALUES (5, 'Popescu', 'Marian', 'ABA')
INSERT INTO Salariati VALUES (6, 'Popescu', 'Vasile', 'ABAA')

 

În acest caz, funcţia care returnează toţi subordonaţii unei persoane poate fi implementată mult mai uşor (şi mai eficient), printr-o căutare cu operatorul LIKE:

 

CREATE FUNCTION Subordonati(@ID int)
RETURNS TABLE AS RETURN
SELECT ID, Nume, Prenume FROM Salariati
WHERE Path LIKE (
      SELECT Path FROM Salariati
      WHERE ID=@ID
)+'_%' 

GO

SELECT * FROM Subordonati(3) 

 

Dezavantajul acestei metode este că limitează adâncimea şi lăţimea arborelui (de exemplu, în acest caz am limitat la maximum 10 nivele, iar fiecare persoană poate avea maximum 26 de subordonaţi direcţi, pt că am folosit câte o literă pentru codificarea fiecărui nivel; desigur, codificarea poate fi modificată să permită de exemplu câte două litere pentru fiecare nivel şi un număr mult mai mare de nivele, dar trebuie totuşi să se stabilească de la început nişte limite maxime).

 

Al treilea model este cel numit „Nested sets” şi a fost popularizat destul de mult de către Joe Celko. Acest model presupune „proiecţia” arborelui pe o axă a numerelor întregi şi stocarea două valori pentru fiecare nod, de exemplu: 

 

/                       Popescu Ion                                           \
   / Ionescu George \   / Vasilescu Marian                                \
                           / Vasilescu Mihai      \  / Popescu Marian \
                              / Popescu Vasile \
1  2                3   4  5  6                7  8  9                10  11  12

CREATE TABLE Salariati (
      ID int PRIMARY KEY,
      Nume nvarchar(20) NOT NULL,
      Prenume nvarchar(30) NOT NULL,
      L int NOT NULL,
      R int NOT NULL,
      CHECK (L<R)
)

INSERT INTO Salariati VALUES (1, 'Popescu', 'Ion', 1, 12)
INSERT INTO Salariati VALUES (2, 'Ionescu', 'George', 2, 3)
INSERT INTO Salariati VALUES (3, 'Vasilescu', 'Marian', 4, 11)
INSERT INTO Salariati VALUES (4, 'Vasilescu', 'Mihai', 5, 8)
INSERT INTO Salariati VALUES (5, 'Popescu', 'Marian', 9, 10)
INSERT INTO Salariati VALUES (6, 'Popescu', 'Vasile', 6, 7)
 

Funcţia care returnează subordonaţii unei persoane arată astfel: 

 

CREATE FUNCTION Subordonati(@ID int)
RETURNS TABLE AS RETURN
SELECT A.ID, A.Nume, A.Prenume
FROM Salariati A, Salariati B
WHERE B.ID=@ID
AND A.L>B.L AND A.R<B.R 

 

De asemenea, căutarea tuturor subordonaţilor se poate face mai eficient decât în primul model, însă adăugarea de noduri noi este mult mai dificilă, deoarece trebuie renumerotate toate valorile (pentru a asigura faptul că sunt întregi şi consecutive).

 

Un model asemănător cu cel precedent, este „Nested intervals”, care permite şi valori fracţionare, uşurând astfel adăugarea de noi noduri.

 

Pentru mai multe informaţii, vezi următoarele articole:
http://www.dbazine.com/oracle/or-articles/tropashko4
http://www.intelligententerprise.com/001020/celko.jhtml?_requestid=1266295

Răzvan