Stromy

CREATE TABLE treetest.data (
  id integer PRIMARY KEY,
  parent integer REFERENCES treetest.data(id) NULL,
  value varchar
);

INSERT INTO treetest.data VALUES(1, NULL, 'root');
INSERT INTO treetest.data VALUES(2, 1, 'A');
INSERT INTO treetest.data VALUES(3, 1, 'B');
INSERT INTO treetest.data VALUES(4, 2, 'AA');
INSERT INTO treetest.data VALUES(5, 2, 'AB');
INSERT INTO treetest.data VALUES(6, 3, 'BA');
INSERT INTO treetest.data VALUES(7, 3, 'BB');
INSERT INTO treetest.data VALUES(8, 4, 'AAA');
INSERT INTO treetest.data VALUES(9, 4, 'AAB');
INSERT INTO treetest.data VALUES(10, 7, 'BBA');
INSERT INTO treetest.data VALUES(11, 7, 'BBB');

Jak je u mne zvykem, jen se zmíním o tom, že řešení můžeme realizovat také na aplikační úrovni (dost často se řeší jednoduše využitím vizuálních komponent typů strom), a zaměřím se na SQL. PostgreSQL v tuto chvíli nepodporuje žádnou konstrukci SQL pro operace nad stromy – existují dvě různé syntaxe: Oracle a ANSI SQL99 (implementovaná v Db2). Nezbude než si napsat uloženou proceduru v PL/pgSQL. Vlastní procedura není nijak komplikovaná, je třeba si jen uvědomit, že se každá SRF funkce volá ve vlastním kontextu, takže nestačí jen vrátit hodnoty na odpovídající úrovni stromu, ale musí se převzít hodnoty z rekurzivních subvolání funkce. To proto, aby se všechny vrácené řádky dostaly do nadřazeného kontextu. Technika přebírání kontextu není vhodná pro hlubší stromy (s každou úrovní se kopírují data). V takových případech je potřeba použít dočasné tabulky. S nimi je ovšem spojena také určitá režie (založení tabulky, insert, smazání tabulky). Pro úplnost – jedná se o tzv. prohledávání stromu do hloubky.

CREATE OR REPLACE FUNCTION treetest.children(_parent integer, _deep
                           integer) RETURNS SETOF treetest._retlist AS $$
DECLARE _r RECORD; _rr RECORD;
BEGIN
  FOR _r IN SELECT id, parent, _deep, value FROM treetest.data
    WHERE parent = _parent LOOP
    RETURN NEXT _r;
    -- Prebirani obsahu rekurzivne volane fce
    FOR _rr IN SELECT * FROM treetest.children(_r.id, _deep + 1) LOOP
      RETURN NEXT _rr;
    END LOOP;
  END LOOP;
  RETURN;
END;
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION treetest.nodes(_id integer) RETURNS SETOF
                                             treetest._retlist AS $$
DECLARE _r RECORD; _rr RECORD;
BEGIN
  SELECT INTO _r id, parent, 0, value FROM treetest.data
    WHERE id = _id;
  RETURN NEXT _r;
  IF FOUND THEN
    -- Prebirani obsahu rekurzivne volane fce
    FOR _rr IN SELECT * FROM treetest.children(_r.id, 1) LOOP
      RETURN NEXT _rr;
    END LOOP;
  END IF;
  RETURN;
END;
$$ LANGUAGE plpgsql;

testdb=# SELECT * FROM treetest.nodes(2);
 id | parent | deep | value
----+--------+------+-------
  2 |      1 |    0 | A
  4 |      2 |    1 | AA
  8 |      4 |    2 | AAA
  9 |      4 |    2 | AAB
  5 |      2 |    1 | AB
(5 řádek)

Trochu ve stínu je modul ltree z doplňků (contrib), který obsahuje podporu (včetně indexů) pro datové hiearchické struktury. Modul používá metodu genealogických identifikátorů, o které se zmíním úplně na konci. Jinak se jedná o naprosto proprietární řešení, na které nikde jinde nenarazíte.

Počínaje PostgreSQL 8 můžeme používat přiřazení (kopírování) hodnot typu RECORD. Přiřazení je poměrně volné, není testována relevantnost typů, pouze hodnoty v originálním záznamu musí být konvertibilní na odpovídající hodnoty v kopii. Významné je pořadí položek, nikoliv název položky! Pokud má kopie více položek než originál, pak tyto „přebytečné“ položky budou obsahovat hodnotu NULL. Opačně, nadbytečné sloupce v originálu jsou ignorovány.

Je nespornou pravdou, že v Rusku se rodí zruční programátoři, navíc zvučných jmen. Evgen Potemkin připravil záplatu, která rozšiřuje funkcionalitu PostgreSQL o SQL operace nad stromy. Záplata původně obsahovala jen podporu syntaxe dle Oracle (hlavně z tohoto důvodu patch nebyl zařazen do distribuce, vývojáři preferují ANSI SQL). V únoru však byla zveřejněna nová verze podporující ANSI SQL 99, která snad bude s trochou štěstí zařazena do PostgreSQL 8.1 (v této verzi budou změny viditelnější pro vývojáře, např. podpora skutečných uložených procedur včetně IN, OUT parametrů (snad :-))). Začnu Oracle syntaxí, ANSI je opravdu v drsně prototypovém stádiu (záplata je zatím pouze pro obstarožní verzi 7.3.4).

Záplata přidává novou klauzuli do příkazu SELECT: CONNECT BY .. START WITH. Atribut PRIOR identifikuje sloupec předka. Výsledek obsahuje fiktivní sloupec _level_. Výpis všech podřízených uzlů root získáme dotazem (id předka je rovno sloupci parent):

SELECT * FROM treetest.data CONNECT BY PRIOR id = parent
  START WITH id = 1;

Opačně

testdb=# SELECT * FROM treetest.data CONNECT BY id = PRIOR parent
START WITH id=11;
 id | parent | value | _level_
----+--------+-------+---------
 11 |      7 | BBB   |       1
  7 |      3 | BB    |       2
  3 |      1 | B     |       3
  1 |        | root  |       4

vrací linii nadřazených prvků uzlu. Výkonnostně je použití klauzule CONNECT BY znatelně rychlejší než použití uložených procedur. Na mém počítači a ukázkových datech to bylo 0.5 ms vůči 1.2 ms. Původně jsem byl vůči této záplatě značně skeptický, svůj názor jsem si musel opravit. ANSI příkaz WITH je silnější, na druhou stranu syntaxeCONNECT BY je jasná a jednoduchá (neprováděl jsem žádné zátěžové testy, abych mohl posoudit kvalitu záplaty – na první pohled fungovalo vše, jak má). Je velice nepravděpodobné, že byste na web hostingu narazili na zazáplatovaný PostgreSQL, můžete si ale silně ušetřit práci při přenášení aplikací z Oraclu.

Syntaxe WITH je:

With t1 [jména sloupců] AS (SELECT d1) SELECT d2 FROM název

Klauzule WITH vytváří skrytou dočasnou tabulku t1, která je plněna dotazem d1. Výsledná množina se ještě zpracovává dotazemd2. Fígl je v tom, že dotaz d1 může jako zdroj obsahovat tabulku t1. Potom se dotaz d1 vyhodnocuje opakovaně – dokud se mění obsah tabulky t1. Dotaz d1 bude obsahovat sjednocení dvou dotazů – první vytváří počáteční obsah tabulky t1, druhý, který se „rekurzivně“ odkazuje na t1, doplňuje obsah tabulky t1. Výsledek této metody odpovídá prohledávání stromu do šířky.

WITH t AS (
  SELECT *, 0::int AS level FROM treetest.data WHERE id = 1
  UNION ALL
  SELECT d.*, level + 1 FROM treetest.data d JOIN t ON d.parent = t.id)
SELECT * FROM t;

 id | parent | value | level
----+--------+-------+-------
  1 |        | root  |     0
  2 |      1 | A     |     1
  3 |      1 | B     |     1
  4 |      2 | AA    |     2
  5 |      2 | AB    |     2
  6 |      3 | BA    |     2
  7 |      3 | BB    |     2
  8 |      4 | AAA   |     3
  9 |      4 | AAB   |     3
 10 |      7 | BBA   |     3
 11 |      7 | BBB   |     3
(11 rows)

Všimněte si, že pro určení hloubky nepotřebujeme žádný fiktivní sloupec. Pro zajímavost, zpracování příkazu trvalo 0.8 ms. Dohledání nadřazených uzlů provede příkaz:

WITH t AS (
  SELECT *, 0::int AS level FROM treetest.data WHERE id = 11
  UNION ALL
  SELECT d.*, level + 1 FROM treetest.data d JOIN t ON t.parent = d.id)
SELECT * FROM t;

Jiným příkladem použití klauzule WITH je generování testovacích tabulek (tento příkaz v tuto chvíli vede k pádu backendu, chybí reálná implementace klauzule WHERE).

WITH t AS (
  SELECT 0::int AS i
  UNION ALL SELECT i + 1 FROM t WHERE i < 100)
SELECT * FROM t;

Konečně trochu netypickým způsobem řešení úloh nad stromy je použití genealogického identifikátoru. Genealogický identifikátor uzlu získáme tak, že ke genealogickému identifikátoru rodičovského uzlu připojíme identifikátor potomka (čerpáno z článku Miguela Sofera). Příkladem genealogického identifikátoru je například určení souboru: cesta+jméno nebo url. Metoda je pojmenována na základě vlastnosti identifikátoru. Každý identifikátor totiž obsahuje úplnou genealogii uzlu. Jistým příkladem je gID je i sloupec value v ukázkových datech.

Způsob zápisu určuje maximální možný počet potomků uzlu. Pokud použijeme číslice, máme k dispozici 10 hodnot, pro velká písmena 32 hodnot atd. Pokud použijeme base64 kódování, můžeme ve dvou znacích dostat 4096 hodnot, ve třech 262144. Použití je primitivní:

testdb=# SELECT * FROM treetest.data WHERE value LIKE 'A%';
 id | parent | value
----+--------+-------
  2 |      1 | A
  4 |      2 | AA
  5 |      2 | AB
  8 |      4 | AAA
  9 |      4 | AAB

Přidáním podmínky AND length(value) = 2 omezíme výslednou množinu na přímé potomky uzlu 2. Hloubka uzlu je rovna délce identifikátoru. Pokud si budeme k uzlu udržovat i počet potomků, můžeme snadno dohledat koncové uzly (listy) – jejich počet potomků je roven nule. Relativně snadno můžeme určit, zda je určitý uzel potomkem jiného uzlu, pak potomek LIKE ‚předek%‘. Seznam všech předků získáme podmínkou gID LIKE value||‚%‘.

testdb=# select * from treetest.data where 'BBB' like value||'%' ;
 id | parent | value
----+--------+-------
  3 |      1 | B
  7 |      3 | BB
 11 |      7 | BBB

Použití genealog. identifikátoru je jednoduché. Horší to bude s efektivností, operátor LIKE rozhodně na Pg nepatří k nejrychlejším – něco jiného je v případě MySQL.

Chtěl jsem předvést a doufám, že jsem předvedl, že stromy nejsou v SQL žádný neřešitelný problém. Záleží jen na možnostech, které máme k dispozici, a tyto možnosti tady jsou.