Z rekurencją w języku T-SQL jest trochę jak z Yeti. Każdy wie, że jest ale kiedy trzeba ją wykorzystać to przeważnie nie wiadomo jak się za nią zabrać. Przyznaję się, iż kiedyś sam miałem z tym problem i stąd pomysł na niniejszy wpis. Według mnie przyczyną owych problemów był nie tylko mój brak pełnego zrozumienia tematu ale również to, iż zwykle materiały poświęcone rekurencji w T-SQL skupiają się na samym wykorzystaniu CTE (Common Table Expression) bez przyglądania się bliżej rozwiązywanemu problemowi. Ja chciałbym dla odmiany podejść do tego tematu trochę inaczej i zaprezentować dwa konkretne zagadnienia związane z odtwarzaniem hierarchii przy pomocy rekurencji oraz pokazać w jaki sposób można sobie z nimi poradzić.

Do rozważań pozwolę sobie przedstawić małą firmę, w której prezesem jest pan Mateusz Orzechowski. Firma posiada dwa działy gdzie kierownikami są Karolia Malinowska oraz Julian Kubicki. W dziale pani Karoliny pracują Amelia Przybylska oraz Maja Wesołowska a w dziale pana Juliana panowie Jakub Witkowski, Karol Tomaszewski oraz Krzysztof Jankowski. Oczywiście imiona i nazwiska są zmyślone i wszelkie ich podobieństwo do osób prawdziwych jest zupełnie przypadkowe 🙂

Powyższą strukturę organizacyjną możemy odtworzyć przy pomocy następującego kodu i będzie to punkt wyjścia do naszych dalszych działań.

declare @pracownicy as table (
    idPracownika int,
    idManagera int,
    nazwa nvarchar(100)
)
insert into @pracownicy values
(1, null, N'Mateusz Orzechowski'),
(2, 1, N'Karolina Malinowska'),
(3, 1, N'Julian Kubicki'),
(4, 2, N'Amelia Przybylska'),
(5, 2, N'Maja Wesołowska'),
(6, 3, N'Jakub Witkowski'),
(7, 3, N'Karol Tomaszewski'),
(8, 3, N'Krzysztof Jankowski');

Jak łatwo zauważyć pan prezes nie ma nad sobą zwierzchnika i dlatego w jego przypadku pole z identyfikatorem managera jest puste.

Dwa chyba najbardziej naturalne pytania w przypadku zagadnień związanych z hierarchią, jakie może postawić sobie każdy pracownik to:

1. kto jest w hierarchii niżej ode mnie,
2. kto jest w hierarchii wyżej ode mnie.

Pierwszy przypadek nazwę podejściem od góry ponieważ wyjdziemy od osoby stojącej wyżej w hierarchii i będziemy poruszać się w dół. Drugi przypadek nazwę przez analogię podejściem od dołu ponieważ punktem wyjścia będzie osoba stojąca niżej w hierarchii i poruszać będziemy się w górę (aż do osoby stojącej najwyżej w hierarchii - czyli w naszym przypadku prezesa Mateusza).

Zanim pójdziemy dalej poświęćmy chwilę czasu na teorię. Każde zapytanie rekurencyjne w T-SQL wygląda podobnie - dwa najważniejsze elementy pojawiające się w każdym z takich zapytań to WITH, który definiuje CTE oraz UNION ALL, który pozwala na łączenie kolejnych wyników rekurencji do jednej tabeli wynikowej. Przykładowe zapytanie w rozpatrywanym przez nas problemie hierarchii może wyglądać tak

declare @osoba int = 3;
with hierarchia as (
    select *, 0 as poziom
    from @pracownicy
    where idPracownika = @osoba
    union all
    select p.*, (poziom + 1) as poziom
    from @pracownicy as p
    join hierarchia as h on p.idManagera = h.idPracownika
)
select *
from hierarchia;

Jak widać zapytanie w części CTE składa się z dwóch elementów. Pierwszym z nich jest zapytanie o pierwszy element (czyli ten, od którego zaczynamy budowanie hierarchii). W powyższym przykładzie budowanie drzewa rozpoczniemy od pracownika o identyfikatorze 3, czyli od pana Juliana Kubickiego. Kolejną częścią jest drugie zapytanie połączone z pierwszym poprzez operator UNION ALL - w zapytaniu tym pobieramy dane pracownika będącego w odpowiedniej relacji z już znalezionymi wcześniej pracownikami, co zostało wyrażone poprzez złączenie JOIN. W tym konkretnym przypadku będziemy szukać wszystkich pracowników, którzy mają identyfikator managera równy identyfikatorom pracowników znalezionych we wcześniejszych krokach (stąd połączenie właśnie z tabelą hierarchia).

Kilka słów wyjaśnienia należy się również polu o nazwie poziom. Pole to ma wartość 0 dla elementu, od którego zaczynamy przeszukiwanie - możemy go więc nazwać elementem poziomu zero. Dla każdego kolejnego kroku rekurencji wartość tego pola ulega zwiększeniu (ale tylko jeden raz w ramach "pętli" a nie dla każdego rekordu) co pozwala nam zobrazować na którym poziomie rekurencji dany rekord został odnaleziony.

Efektem działania powyższego kodu będzie następujący zbiór rekordów

Widzimy, iż odnalezione zostały rekordy osoby, od której rozpoczęliśmy poszukiwanie oraz rekordy wszystkich jego podwładnych. Gdybyśmy dodatkowo zmodyfikowali nasze zapytanie eliminując z niego rekordy z poziomu 0 wtedy efektem działania byłaby lista wszystkich podwładnych pana Juliana.

Nie trudno domyślić się, iż uzyskany przez nas efekt to realizacja wspomnianego wyżej podejścia od góry. Gdybyśmy chcieli teraz osiągnąć efekt podejścia od dołu to nasze powyższe zapytanie musiałoby ulec lekkiej modyfikacji. Do pokazania tego na przykładzie zaprosimy panią Amelię Przybylską (osoba o identyfikatorze 4) z zaprezentowanej wyżej firmy.

declare @osoba int = 4;
with hierarchia as (
    select *, 0 as poziom
    from @pracownicy
    where idPracownika = @osoba
    union all
    select p.*, (poziom + 1) as poziom
    from @pracownicy as p
    join hierarchia as h on h.idManagera = p.idPracownika
)
select *
from hierarchia;

Gdyby ktoś nie zauważył co zmieniło się względem wcześniejszego zapytania to podpowiadam, iż chodzi o linię nr 9 gdzie zamieniłem ze sobą miejscami aliasy h oraz p przy operacji porównania. Mówiąc inaczej tym razem szukamy osób, które są managerami wszystkich znalezionych wcześniej (w tej relacji znaleziona będzie tylko jedna osoba w każdym kroku rekurencji ponieważ każda osoba ma tylko jednego managera).

Efektem działania naszego zmodyfikowanego kodu będzie następujący zbiór rekordów

Gdybyśmy podobnie jak wcześniej wyeliminowali rekordy z poziomu 0 wtedy efektem działania byłaby lista wszystkich managerów stojących w hierarchii wyżej od pani Amelii.

Jak widać na powyższych przykładach, budowanie hierarchii przy pomocy rekurencji wcale nie jest rzeczą tak banalną jakby się mogło wydawać i nawet potencjalnie niewielka zmiana w samym zapytaniu może doprowadzić nas do zupełnie innych rezultatów niż byśmy oczekiwali. Zauważyłem, iż często wpisy poświęcone rekurencji w T-SQL skupiają się na budowaniu hierarchii tylko w jedną stronę gdyż według mnie traktują ją tylko jako narzędzie dla pokazania działania CTE przez co zatraca się samą istotę rozwiązywanego problemu. Moim zdaniem rozwiązywany problem powinien być ważniejszy od narzędzia i dlatego uważam, iż CTE powinno być ukazywane właśnie jako narzędzie do osiągnięcia celu a nie cel sam w sobie.

Mam nadzieję, iż pomimo banalnego tematu wpis ten okazał się dla kogoś mimo wszystko przydatny 🙂

Gdyby drogi czytelniku zainteresował Cię temat rekurencji w TSQL i chciałbyś zobaczyć do czego jeszcze można ten mechanizm wykorzystać, to zapraszam do lektury mojego innego wpisu poświęconego przygotowywaniu danych dla potrzeb raportów.