Hlavní navigace

SQL a rekurze

7. 5. 2014 13:30 | zboj

Pořád dokola mě překvapuje, jak málo programátorů zná množinové operace v SQL. Možná ještě méně jich zná “common table expressions”. A pokud už znají obojí, nevědí, jak vše použít s rekurzí. A jen malá hrstka ví, jak to vše funguje uvnitř. Proto tento malý přehled (od jednoduššího ke složitějšímu).

Množinové operace

Základy teorie množin zná asi každý. Ostatně SQL nenabízí o mnoho více než průnik, sjednocení a rozdíl. Jsou popsány v každém úvodu do SQL, ale uvedu zde příklad, protože bude potřeba dále. Mějme tedy tabulku edges se sloupci a a b, jež reprezentuje hrany nějakého orientovaného grafu. Získat SELECTem hrany začínající ve vrcholu 1 je triviální. Jak ale získat ty, které ve vrcholu 1 nezačínají? Zde pomůže rozdíl množin:

SELECT a, b FROM edges EXCEPT SELECT a, b FROM edges WHERE a = 1

Je jasné, že obě tabulky musí mít stejnou signaturu (počet sloupců a jejich typ). Jak říkám, je to triviální příklad, ale poslouží jako výchozí bod pro složitější aspekty dotazů do relačních databází.

Common table expressions (CTEs) a rekurze

CTEs jsou náhledy (views) existující pouze po dobu vyhodnocování dotazu. Pokud se nevyužije rekurze (zavedená v SQL3), jde jen o syntaktický cukr. S rekurzí jde ale o mocný nástroj. Pokud chceme získat všechny cesty v grafu (tj. tranzitivní uzávěr), použijeme právě CTE:

WITH paths AS ( SELECT a, b FROM edges UNION SELECT e.a, p.b FROM edges e, paths p WHERE e.b = p.a ) SELECT a, b FROM paths

První SELECT znamená, že hrana z a do b je cesta z a do b (to je dno rekurze). Druhý SELECT říká, že pokud máme hranu z a do b a cestu z b do c, máme také cestu z a do c. Sjednocením množin (UNION odstraní případné duplicity) získáme konečný výsledek dotazu.

Vyhodnocování rekurzívních dotazů

Nyní se konečně dostáváme k něčemu zajímavému. Jak se rekurzívní dotaz vyhodnucuje? Nejjednodušší by bylo vyhodnotit dotaz prostou rekurzí (backtrackingem). Pro názornost uvedu odpovídající pravidla v Prologu:

path(X, Y) :- edge(X, Y). path(X, Z) :- edge(X, Y), path(Y, Z).

To je z pohledu logiky prvního řádu naprosto správně, ovšem pokud graf obsahuje cyklus, výpočet se zacyklí. A protože žádná databáze se na uvedeném příkladu nezacyklí, je zřejmé, že použitý algoritmus je poněkud (v některých databázích značně) složitější.

Jen o trochu komplikovanější je vyhodnocení dotazu výpočtem pevného bodu (tak funguje například sqlite). Začne se od nerekurzívní části dotazu (první argument operace UNION) a postupně se v cyklech přidávají další výsledky podle rekurzívní definice. Duplicity se odstraňují a pokud již není do přidat, je výsledek dotazu kompletní (z pohledu logiky se jedná o stabilní model uvažovaných relací a pravidel).

Ani tento algoritmus nelze bohužel použít vždy, nefungují s ním dotazy s operací EXCEPT. V nejobecnějším případě se používá algoritmus založený na principu “producer/consumer” (některé publikace uvádějí “server/requester”). Každý (rekurzivní) poddotaz se vyhodnocuje pouze jednou a mezivýsledky se ukládají do pomocných tabulek. Pokud nějaký poddotaz obsahuje rekurzívní “podpoddotaz”, zapíše se k němu jako “consumer”, resp. “requester”. Odpovídající pomocná tabulka následně funguje jako “producer” a posílá zprávy a nových mezivýsledcích. Někdy se tento postup nazývá “delayed evaluation”, protože vyhodnocování poddotazů se pozastavuje (v angličtině se poddotaz nazývá “suspended”) a pokračuje se později, jakmile je k dispozici další mezivýsledek. Implementace je značně komplikovaná, ale uvedený algoritmus zaručuje, že se výpočet na žádném dotaze nezacyklí (v obecnější verzi pro logické programování s negací se nazacyklí na žádném programu bez funkčních symbolů, jenž je “non-floundering”).

Pro zajímavost uveďme, že z pohledu výpočetní složitosti (a ta je u velkých databází extrémně důležitá) je řádově výhodnější použít levou rekurzi. V Prologu tedy něco, na čemž se většina implementací zacyklí:

path(X, Z) :- path(X, Y), edge(Y, Z). path(X, Y) :- edge(X, Y).