Jan 13 2009

Interogările recursive folosind Common Table Expressions (CTE)

Categorie: Metodologie | SQL Server | T-SQL | TutorialCatalin Dumitru @ 09:26

Marele avantaj al introgărilor recursive este acela că se pot referii  singure. Care este rostul acestora? Pentru a reprezenta date ierarhice aşa cum este o organigramă a departamentelor dintro companie sau un meniu pentru un site web etc.
Pentru a se rezolva acest aspect au apărut mai mulţi algoritmi pe care nu o să-i discut aici însă utilizând motoarele de căutare puteţi găsi singuri foarte mulţi algoritmi. Prin interogările recursive avem posibilitatea de a standardiza modul de lucru cu datele ierarhice şi cu interogări asupra acestora.
Sintaxa:
WITH nume_CTE (optional lista_coloane) AS
 (
   Membru_ancora
   UNION ALL
   Membru_recursiv
 )
INTEROGARE ASUPRA nume_CTE
OPTION (MAXRECURSION n)
 
Se poate observa că interogarea recursivă este formată din două interogări numite membru ancoră şi  membru recursiv. Membrul ancoră este interogarea al cărei rezultat  va fi folosit ca intrare pentru membrul recursiv. Aceasta se va autoapela până când niciun rând nu mai este întors (condiţie de încheiere). Ar mai fi de menţionat ca reguli pentru interogările recursive că “UNION ALL” este singura construcţie permisă între cei doi membrii şi că membrul recursiv poate referii doar o singura interogare recursivă (CTE).
Un exemplu folosit pentru a înţelege recursivitatea este calculul factorialului. Spre exemplificare se poate folosi urmatorul script:
CREATE FUNCTION dbo.Factorial(@Numar int)
RETURNS int AS BEGIN
 
      IF @Numar = 0 BEGIN
            RETURN 1
      END
 
      RETURN @Numar * dbo.Factorial(@Numar – 1)
END
 
Şi testarea:
SELECT  dbo.Factorial(1) AS [1!],          
                  dbo.Factorial(2) AS [2!],
                  dbo.Factorial(3) AS [3!],
                  dbo.Factorial(4) AS [4!],
                  dbo.Factorial(5) AS [5!]
Se poate observa că funcţia se autoapeleaza până când @Numar = 0 (pentru cine nu ştie: n! = 1*2*..(n-1)*n)
Să analizăm comparativ exemplul de mai sus cu CTE. Avem un parametru de intrare iar în CTE avem membru de intrare. Apoi după condiţia de continuitate se autoapelează funcţia cam în acelaşi mod în care membrul recursiv se autoapelează decrementând valoarea parametrului (în CTE se preia valoarea părintelui astfel se avanseaza cu un nivel). Când parametrul funcţiei va avea valoarea 0, se opreşte autoapelarea, iar în CTE ne oprim când nu mai avem părinte, am ajuns la condiţia de ieşire. Când s-a ajuns la nivelul maxim de iterare, valorile din stivă se vor asigna variabilei rezultat, se va combina cu membrul ancora iar rezultatul este afisat.
Exemplu:
CREATE TABLE Arbore (
      ID_Nod                    int IDENTITY(1,1) PRIMARY KEY CLUSTERED,
      ID_NodParinte     int NULL
            CONSTRAINT [FK_Arbire_ID_Nod] FOREIGN KEY REFERENCES dbo.Arbore(ID_Nod),
      Informatie              nvarchar(200) NOT NULL,
            CONSTRAINT  [CK_ID_NodParinte] CHECK (ID_Nod <> ID_NodParinte)
)
 
GO
INSERT INTO Arbore (ID_NodParinte, Informatie)
VALUES (NULL, N’Rădăcină’)
 
INSERT INTO Arbore (ID_NodParinte, Informatie)
VALUES (1, N’Nivelul 1 – primul nod’)
 
INSERT INTO Arbore (ID_NodParinte, Informatie)
VALUES (1, N’Nivelul 1 – al 2-lea nod’)
 
INSERT INTO Arbore (ID_NodParinte, Informatie)
VALUES (3, N’Nivelul 2 – primul nod’)
 
INSERT INTO Arbore (ID_NodParinte, Informatie)
VALUES (4, N’Informatie căutată’)
GO
Am creat şi populat o tabelă în care nodul părinte referă o valoare din cheia tabelei. Această structură ajută la reprezentarea unui arbore definit unic printro cheie, părinte şi informaţie (valoare). Ne propunem să aflăm toate nodurile prin care se trece de la rădăcină până la frunza cu o anumită informaţie. Un exemplu mai concret ar fi acela prin care dorim să aflăm toţi şefii unui angajat plecând de la seful imediat superior până la directorul general sau putem afla structura ierarhică a unui departament pornind de la acesta şi până la ultimul nivel de conducere.
Utilizare CTE pentru exemplul propus (frunza cu o informaţie dată):
WITH Arb (ID_Nod, ID_NodParinte, Informatie, Nivel) AS
(
      SELECT ID_Nod, ID_NodParinte, Informatie, 0
      FROM dbo.Arbore
      WHERE Informatie = N’Informatie căutată’
     
      UNION ALL
     
      SELECT a.ID_Nod, a.ID_NodParinte, a.Informatie, Nivel + 1 
      FROM dbo.Arbore a
      INNER JOIN Arb b ON b.ID_NodParinte = a.ID_Nod
      WHERE B.ID_NodParinte IS NOT NULL
)
SELECT ID_Nod, ID_NodParinte, Informatie, Nivel
FROM Arb
ORDER BY ID_Nod
 
Să analizăm:
Se crează membrul ancoră în care se crează o pseudocoloană (Nivel) ce ne va ajuta să identificăm nivelul ierarhic; rezultatul membrului ancoră se foloseşte ca intrare pentru membrul recursiv; se incrementează nivelul; se afişează rezultatul:
ID_Nod      ID_NodParinte Informatie          Nivel
———– ————- ————————— ——–
1           NULL          Rădăcină                    3
3           1             Nivelul 1 – al 2-lea nod    2
4           3             Nivelul 2 – primul nod      1
5           4             Informatie căutată          0
 
(4 row(s) affected)

Etichete: , ,