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