Perspektywy i rekursja

No dobrze, umiemy wypisywać już całkiem sporo, ale jak na przykład wypisać wszystkich (niekoniecznie bezpośrednich) podwładnych danego pracownika, niezależnie od liczby poziomów hierarchii?

Aby zapisać takie zapytania, trzeba mieć możliwość policzenia domknięcia przechodniego. Inaczej mówiąc, potrzebna jest rekursja. SQL dość długo nie pozwalał na zapytania rekurencyjne: stwarzają kłopoty zarówno teoretyczne (negacja) jak i praktyczne (wydajność).

Perspektywy

Zacznijmy od perspektywy: konstrukcji, która nie zwiększa mocy zapytań, ale pozwala wygodniej je zapisywać. Przypuśćmy, że chcemy znaleźć imię najcięższego zwierzaka dla każdego gatunku 

  SELECT imie, Zwierzaki.gatunek 
  FROM Zwierzaki JOIN (SELECT gatunek, MAX(waga) mw FROM Zwierzaki
                       GROUP BY gatunek) Maksy
                 ON Zwierzaki.gatunek = Maksy.gatunek
  WHERE waga = mw;

Jeśli takiego wewnętrznego zapytania używamy w wielu miejscach, to warto zdefiniować perspektywę 

  CREATE VIEW Maksy AS
  SELECT gatunek, MAX(waga) mw FROM Zwierzaki
  GROUP BY gatunek;

Powstaje wirtualna tabela Maksy, której możemy używać jak zwykłej tabeli 

  SELECT imie, Zwierzaki.gatunek 
  FROM Zwierzaki JOIN Maksy ON Zwierzaki.gatunek = Maksy.gatunek
  WHERE waga = mw;

Perspektywy lokalne

Jednak materialnie tabela taka nie istnieje -- jest wyliczana przy każdorazowym użyciu, podobnie jak procedury czy funkcje w konwencjonalnych językach programowania.

Perspektywy są bardzo wygodne, ale zaśmiecają przestrzeń nazw, ponieważ są definiowane globalnie w schemacie. Jeśli chcemy perspektywy użyć tylko przez chwilę, trzeba po sobie posprzątać 

  DROP VIEW Maksy;

Z pomocą przychodzi konstrukcja WITH, pozwalającą definiować perspektywy lokalne (jak bloki w zwykłych językach programowania). Czasem nazywa się ją Common Table Expression (CTE).

Podstawowa składnia: 

WITH
    lokalna-relacja AS (
        definicja  -- najczęściej wyrażenie SELECT
    )[, ...)]
zapytanie-z-lokalna-relacją;

Banalny przykład: jeśli globalną perspektywę zapisujemy używając 

CREATE VIEW gatavg(gat, m) AS
  (SELECT gatunek, avg(waga) FROM zwierzaki GROUP BY gatunek);

i potem możemy napisać 

SELECT gat FROM gatavg WHERE m = (SELECT max(m) FROM gatmaks);

To samo z perspektywą lokalną (CTE) wygląda następująco 

WITH gatavg(gat, m) AS
  (SELECT gatunek,avg(waga) FROM Zwierzaki GROUP BY gatunek)
SELECT gat FROM gatavg WHERE m = (SELECT max(m) FROM gatavg);

Inny przykład 

WITH stud_mat AS (
  SELECT * FROM students
    WHERE wydz='MIMUW'
  )
SELECT * FROM stud_mat
WHERE rok != 1
ORDER BY nazwisko, imie;

Równoważna postać bez CTE 

SELECT *
FROM (SELECT * FROM students
      WHERE wydz = 'MIMUW') AS stud_mat
WHERE rok != 1
ORDER BY nazwisko, imie;

Perspektyw lokalnych może być więcej 

WITH gatmaks(gat,kont,m) AS
  (SELECT nazwa,kontynent,max(waga)
   FROM zwierzaki JOIN gatunki ON nazwa = gatunek
   GROUP BY nazwa), 
     kontmaks(kont,mk) AS 
  (SELECT kont, max(m) from gatmaks group by kont)
SELECT kont FROM kontmaks WHERE mk = (SELECT max(mk) FROM kontmaks);

a także 

WITH stud_mat AS (
  SELECT * FROM students
    WHERE wydz='MIMUW'
  ),
  stud_mat_inf AS (
  SELECT * from stud_mat
    WHERE kierunek = 'Informatyka'
  )
SELECT * FROM stud_mat_inf
WHERE rok != 1
ORDER BY nazwisko, imie;

Rekursja i WITH RECURSIVE

Przejdźmy do obiecanych zapytań rekurencyjnych. Potrzebna nam będzie baza danych z zależnościami hierarchicznymi. Taka ,,oficjalna'' demonstracyjna baza danych Oracle znajduje się na pliku demobld.sql.

Aby zdefiniować zapytanie rekurencyjne należy dodać po WITH słowo kluczowe RECURSIVE. Najprostszy format wygląda tak: 

WITH RECURSIVE nazwa ([nazwy kolumn]) AS (
    zapytanie inicjujące
  UNION
    zapytanie poszerzające, korzystające z nazwa
  )
zapytanie korzystające z nazwa;

Koncepcyjnie działa to wtedy następująco. Najpierw do lokalnej perspektywy wstawiamy wartość zapytania inicjującego. Następnie, korzystając z aktualnej zawartości perspektywy wyliczamy wartość zapytania poszerzającego i dodajemy te krotki do perspektywy . Kontynuujemy tak długo, aż zapytanie poszerzające nic nowego nie zwróci.

Prześledźmy ten proces na przykładzie zapytania liczącego sumę liczb od 1 do 100: 

WITH RECURSIVE t (liczba) AS (
  SELECT 1
  UNION
  SELECT liczba + 1 FROM t WHERE liczba < 100
  )
SELECT sum(liczba) FROM t;

Jeżeli chcemy wypisać wszystkie osoby, za które odpowiada KING (czyli jego podwładnych i jego samego) możemy napisać coś takiego: 

  WITH RECURSIVE sub (empno, ename) AS (
    SELECT empno, ename FROM emp WHERE ename = 'King'
  UNION
    SELECT emp.empno, emp.ename FROM emp, sub WHERE emp.mgr = sub.empno
)
SELECT * FROM sub;

W każdym kolejnym kroku dodajemy teraz kolejny poziom podwładnych.

Zadanie 1

1. Wypisz wszystkich podwładnych Kinga bez niego samego

2. Wypisz wszystkich podwładnych Kinga bez Blake'a i jego podwładnych

3. Wypisz wszystkich pracowników którzy mają ,,pod sobą'' SALESMANa

4. Wypisz dla każdego pracownika sumę zarobków jego i jego podwładnych

5. [Trudne!] Wypisz imiona wszystkich podwładnych Kinga (razem z nim) w taki sposób aby uzyskać strukturę drzewa: 

    King
      Jones
        Scott
          Adams
        Ford
          Smith
          ...

Może się przydać funkcja rpad().

Odpowiedzi

  1. with recursive sub (empno, ename) as (
    select empno, ename from emp where ename = 'King'
  union
    select emp.empno, emp.ename from emp, sub
    where emp.mgr = sub.empno
)
select * from sub where ename != 'King';

  2. with recursive sub (empno, ename) as (
    select empno, ename from emp where ename = 'King'
  union
    select emp.empno, emp.ename from emp, sub
    where emp.mgr = sub.empno and emp.ename != 'Blake')
select * from sub;

  3. WITH RECURSIVE sub (empno, ename, mgr, job) AS (
    SELECT empno, ename, mgr, job FROM emp WHERE job = 'SALESMAN'
  UNION
    SELECT emp.empno, emp.ename, emp.mgr, emp.job FROM emp, sub
    WHERE sub.mgr = emp.empno
)
SELECT * FROM sub;

  4. SELECT p.ename,
        (WITH RECURSIVE sub (empno, ename, sal) AS (
          SELECT empno, ename, sal FROM emp WHERE ename =p.ename
          UNION
          SELECT emp.empno, emp.ename, emp.sal  FROM emp, sub 
          WHERE emp.mgr = sub.empno)
SELECT SUM(sal) FROM sub) FROM emp p;

albo

with recursive foo as (select empno as p,empno as c,sal from emp
                       union
                       select foo.p, emp.empno, emp.sal
                       from foo join emp on foo.c = emp.mgr)
select p, sum(sal) from foo group by p;

 p   |   sum    
------+----------
 7844 |  1500.00
 7900 |   950.00
 7369 |   800.00
 7566 | 10875.00
 7876 |  1100.00
 7782 |  3750.00
 7902 |  3800.00
 7788 |  4100.00
 7654 |  1250.00
 7934 |  1300.00
 7521 |  1250.00
 7839 | 29025.00
 7499 |  1600.00
 7698 |  9400.00
(14 wierszy)

  5.