Rekurencja w SQL Server czyli Common Table Expressions - drzewa

Zarządzanie drzewiastymi strukturami

SQL Server to relacyjna baza danych. Nie przeszkadza to jednak w tym, aby w pozornie płaskiej tabeli zapisać drzewiastą strukturę. Jak w takim przypadku pobrać dane z takiej tabeli? Dane wyjściowe też muszą być płaskie, bo takie wyniki zwraca SQL Server. Pierwsza myśl zwykle jest taka, aby pobrać jednym zapytaniem elementy nadrzędne, dla każdego z nich wyszukać jego dzieci, dla każdego z dzieci jego poddzieci. Każda z tych operacji wymaga jednego zapytania SQL. Jedną z najprostszych technik przeszukiwania drzew jest technika rekurencyjna i taką właśnie zastosujemy.

Aby testować nasze skrypty przygotujmy sobie tabelę z danymi. Skrypt tworzący strukturę i dane pokazany jest poniżej:

CREATE TABLE Std(
ID int,
Parent int,
Name nvarchar(16)
)

INSERT INTO Std VALUES (1,NULL,'Ssaki')
INSERT INTO Std VALUES (2,NULL,'Płazy')
INSERT INTO Std VALUES (3,NULL,'Gady')
INSERT INTO Std VALUES (4,1,'Gryzonie')
INSERT INTO Std VALUES (5,4,'Bobrowate')
INSERT INTO Std VALUES (6,5,'Bóbr europejski')
INSERT INTO Std VALUES (7,1,'Drapieżne')
INSERT INTO Std VALUES (8,7,'Łasicowate')
INSERT INTO Std VALUES (9,8,'Borsuk')
INSERT INTO Std VALUES (10,8,'Kuna domowa')
INSERT INTO Std VALUES (11,8,'Rosomak')

Spróbujmy teraz określić poziomy zagłębienia poszczególnych elementów. Skrypt może wyglądać mniej więcej tak:

WITH CTE AS
(SELECT ID, Name, Parent, 0 Rec FROM Std WHERE Parent IS NULL
UNION ALL
SELECT S.ID, S.Name, S.Parent, (Rec+1) FROM
CTE C JOIN Std S ON S.Parent=C.ID
)
SELECT Name, Rec FROM CTE;

Teraz spróbujmy rozwiązać inne zadanie. Załóżmy, że potrzebujemy elementów z najniższego poziomu, ale potrzebujemy również pełnej ścieżki od rodzica do potomka. Przekładając to na nasz przykład potrzebujemy konkretnych zwierząt, a także informacji o grupach, do których te zwierzęta należą. Przyjrzyjmy się przykładowemu rozwiązaniu:

WITH CTE AS
(SELECT ID, CAST(Name AS NVARCHAR(1000)) Name, Parent, 0 Rec FROM Std WHERE Parent IS NULL
UNION ALL
SELECT S.ID, CAST((C.Name+' => '+S.Name) AS NVARCHAR(1000)) Name, S.Parent, (Rec+1) FROM
CTE C JOIN Std S ON S.Parent=C.ID
)
SELECT Name FROM CTE WHERE Rec=3

Wykonanie tych instrukcji pozwoli pobrać następujące wyniki:

Ssaki => Drapieżne => Łasicowate => Borsuk
Ssaki => Drapieżne => Łasicowate => Kuna domowa
Ssaki => Drapieżne => Łasicowate => Rosomak
Ssaki => Gryzonie => Bobrowate => Bóbr europejski

Kolejne zadanie będzie polegało na tym, aby wypisać całą strukturę drzewa. Należy jednocześnie zadbać o to, aby wszystko było przejrzyste, a każde dziecko przywiązane do swojego rodzica. Oczekujemy aby całość wyglądała mniej więcej tak:

Rodzic1
    Dziecko1
        Wnuk1
            Prawnuk1
    Dziecko2
Rodzic2
    Dziecko3
    Dziecko4
        Wnuk2

Przygotujmy sobie najpierw tabelę oraz zestaw danych. Niech będzie to hipotetyczna struktura banku i informacje kredytowe.

CREATE TABLE Kredyty(
ID int,
Parent int,
Name nvarchar(32)
)

INSERT INTO Kredyty VALUES (1,NULL,'Kredyt hipoteczny')
INSERT INTO Kredyty VALUES (2,NULL,'Kredyt gotówkowy')
INSERT INTO Kredyty VALUES (3,NULL,'Kredyt inwestycyjny')
INSERT INTO Kredyty VALUES (4,1,'Kredyt złotówkowy')
INSERT INTO Kredyty VALUES (5,4,'Styczeń')
INSERT INTO Kredyty VALUES (6,5,'Firma AAA')
INSERT INTO Kredyty VALUES (7,1,'Kredyt w Euro')
INSERT INTO Kredyty VALUES (8,7,'Luty')
INSERT INTO Kredyty VALUES (9,8,'BBB Bank')
INSERT INTO Kredyty VALUES (10,8,'Investment Ltd.')
INSERT INTO Kredyty VALUES (11,8,'Company CCC')

Teraz fragment skryptu, który pozwala wyświetlić dane o kredytach w wymagany sposób:

WITH CTE AS
(SELECT ID, Name, Parent, 0 Rec, CAST(ID AS NVARCHAR(128)) Ord
FROM Kredyty WHERE Parent IS NULL
UNION ALL
SELECT S.ID, S.Name, S.Parent, (Rec+1),
CAST(Ord+'|'+CAST(S.ID AS NVARCHAR(16)) AS NVARCHAR(128)) Ord FROM
CTE C JOIN Kredyty S ON S.Parent=C.ID
)
SELECT REPLICATE(' ', Rec)+Name FROM CTE ORDER BY Ord

Rezultat działania powyższego skryptu będzie następujący:

Kredyt hipoteczny
    Kredyt złotówkowy
        Styczeń
            Firma AAA
    Kredyt w Euro
        Luty
            Investment Ltd.
            Company CCC
            BBB Bank
Kredyt gotówkowy
Kredyt inwestycyjny

W ramach ćwiczeń można sobie napisać podobny skrypt. Dodatkowe założenie niech będzie takie, że na każdym z poziomów w ramach jednego rodzica elementy powinny być posortowane. W ramach rodzica Luty firmy będą zatem wyświetlane w kolejności alfabetycznej, czyli: BBB Bank, Company CCC, Investment Ltd., Kredyt w Euro będzie wyżej niż Kredyt złotówkowy w ramach grupy Kredyt hipoteczny. Same rodzaje kredytów też niech będą posortowane według nazwy, a nie według identyfikatora, jak to jest w ostatnim przykładzie.

Kategoria:Common Table Expression SQL Server

Paweł Dyl, 2013-12-20

Spis treści:

Rekurencja w SQL Server czyli Common Table Expressions - drzewa

Zarządzanie drzewiastymi strukturami

Brak komentarzy - bądź pierwszy