Nepříliš chytrý blog Od programování po jezevce

29Led/1223
Databáze

Closure Table – stromy v MySQL trochu jinak

database_tree

Ukládání stromové struktury do relační databáze je celkem běžným požadavkem při návrhu aplikací. Typicky se setkáme například s požadavkem realizovat kategorie, jejich podkategorie, podkategorie podkategorií atd. nebo prostě jen komentáře s možností reakce na kohokoli. Možností, jak řešit tento problém, je několik a každá se hodí pro jiný případ. Jistě znáte řešení v podobě Adjencency Listu, což je prostá reference na rodiče, které je v databázových systémech bez rekurzivních dotazů (MySQL) ukázkovým anti-patternem. Dalším často používaným řešením je například Modified Preorder Tree Traversal Algorithm známý jako traverzování kolem stromu. O těchto způsobech reprezentace stromu v relační databázi toho bylo již napsáno dost a dost. Já se ale, jak už napovídá název článku, budu věnovat metodě známé jako Closure Table, o které toho v našich končinách ještě nebylo moc napsáno.

Mějme například tuto stromovou strukturu kategorií.

alt

Jak můžeme vidět na tabulkách níže, princip této metody spočívá v oddělení vazeb mezi daty do samostatné tabulky. Každý prvek struktury pak má specifikovánu vazbu na sebe a všechny prvky pod sebou.

ancestor descendant depth
1 1 0
1 2 1
1 3 2
1 4 2
1 5 1
1 6 2
1 7 2
1 8 1
1 9 2
1 10 2
2 2 0
2 3 1
2 4 1
3 3 0
4 4 0
5 5 0
5 6 1
5 7 1
6 6 0
7 7 0
8 8 0
8 9 1
8 10 1
9 9 0
10 10 0
category_id name
1 PC příslušenství
2 Tiskárny
3 Laserové
4 Inkoustové
5 Myši
6 Optické
7 Laserové
8 Klávesnice
9 Drátové
10 Bezdrátové

Stáhnout Tabulky – SQL skript

Pomocí obrázku získáte ještě lepší představu o principu. Červenými šipkami jsou znázorněny vazby ukládané v oddělené tabulce. Čísla vyjadřují hloubku zanoření.

alt

Na první pohled se může zdát, že se v Closure Table ukládá zbytečně moc dat. Je pravda, že v extrémních případech to může být až n2 záznamů. Tato situace ale nastane pouze v případě, kdy ze stromu vyrobíme jakýsi lineární seznam, takže každý prvek (kromě posledního) má právě jednoho potomka. V praxi je situace mnohem lepší a minimálně v 95% případů nebude nutné paměťovou náročnost řešit.

Operace s Closure Table

Situace 1: Získání celého podstromu od daného prvku

Tento požadavek může nastat například pokud chceme uložené kategorie použít jako menu.

Řešení:

SELECT c.*, cc.depth FROM category c
  JOIN category_closure cc
    ON (c.category_id = cc.descendant)
  WHERE cc.ancestor = 2;

Výsledek:

id name depth
2 Tiskárny 0
3 Laserové 1
4 Inkoustové 1

Situace 2: Získání všech nadřazených prvků daného prvku až ke kořeni

Vhodné například pro výpis drobečkové navigace.

Řešení:

SELECT c.*, depth
  FROM category c
  JOIN category_closure cc
    ON (c.category_id = cc.ancestor)
  WHERE cc.descendant = 4;

Výsledek:

id name depth
1 PC příslušenství 2
2 Tiskárny 1
4 Inkoustové 0

Situace 3: Vložení nového záznamu na libovolné místo

Zde už je situace o něco komplikovanější. Jako příklad k řešení zvolím vložení potomka k prvku s id 10. Od kořene to tedy bude PC příslušenstvíKlávesniceBezdrátovéBluetooth.

Řešení:

INSERT INTO category (name) VALUES ('Bluetooth'); -- vrátí prvek s id 11

INSERT INTO category_closure (ancestor, descendant, depth) VALUES (11,11,0);

INSERT INTO category_closure (ancestor,descendant, depth)
  SELECT ancestor, 11, depth+1 FROM category_closure
    WHERE descendant = 10;

Situace 4: Smazání jednoho prvku a navázání jeho potomků na jeho rodiče

Tento případ není tak častý, ale jako ukázku ho zde použiji. Požadavek bude například smazat prvek s id 8 a jeho potomky (9 a 10) navázat na jeho rodiče (1). Pro zjednodušení celého postupu je vhodné mít nastavené ON DELETE pravidlo u cizích klíčů v Closure Table na CASCADE.

Řešení:

UPDATE category_closure SET depth = depth-1
        WHERE ancestor != descendant
                AND descendant IN (SELECT descendant FROM (SELECT * FROM category_closure) as did WHERE ancestor = 8);
DELETE FROM category WHERE category_id = 8;

Situace 5: Smazání celého podstromu

Smazání celého podstromu je o poznání častější požadavek, nesmí tu tedy chybět. Budeme opět mazat prvek s id 8. Tentokrát ale smažeme i všechny jeho potomky (9,10 a v situaci 3 vložený prvek 11). Typicky by stačilo spustit příkaz DELETE s vnořeným SELECTem, ale narazíme zde ale na problém s MySQL (u jiného DB systému jsem to nezaznamenal). Nemůžeme totiž použít DELETE a SELECT nad stejnou tabulkou v jednom příkazu. Abychom tuto nepříjemnou vlastnost obešli, stačí nám využít tzv. multi-table delete, který slouží k mazání záznamů z více tabulek jedním příkazem.

Typické řešení:

DELETE FROM category WHERE category_id IN (SELECT descendant FROM category_closure AS category_id WHERE ancestor = 8);
DELETE FROM category WHERE category_id = 8;

Řešení v MySQL:

DELETE cc_a FROM category_closure cc_a JOIN category_closure cc_d USING (descendant) WHERE cc_d.ancestor = 8;
DELETE FROM category WHERE category_id = 8;

Situace 6: Přesunutí podstromu

Představme si, že chceme vytvořit novou kategorii „Perifierie“ (pod „PC příslušenství“) a přesunout do ni kategorie „Myši“ a „Klávesnice“. Kategorii už vytvářet umíme, takže nám zbývá přesunout do ní kategorie stávající. Pro ilustraci budeme pracovat pouze s kategorií „Myši“ (id 5).

Před tím, než budeme moci přesunout podstrom, musíme ho „odpojit“ původního stromu. K tomu lze použít lehce upravený příkaz z předchozí situace. Stačí smazat všechny vazby kromě těch v odebíraném podstromu (abychom zachovali hierarchii). Typické řešení pomocí vnořených SELECTů by bylo opět velice jednoduché, ale MySQL nám v tomhle prostě hází klacky pod nohy, takže výsledkem je tento příkaz.

Vyjmutí podstromu ze struktury:

DELETE cc_a FROM category_closure cc_a
  JOIN category_closure cc_d USING(descendant)
  LEFT JOIN category_closure cc_x
    ON cc_x.ancestor = cc_d.ancestor AND cc_x.descendant = cc_a.ancestor
  WHERE cc_d.ancestor = 5 AND cc_x.ancestor IS NULL;

Následně musíme vložit nové vazby mezi celým naším podstromem a všemi jeho novými nadřazenými kategoriemi (kategorie „Perifierie“ má id 12).

Začlenění podstromu na nové místo:

INSERT INTO category_closure (ancestor, descendant, depth)
  SELECT supertree.ancestor, subtree.descendant, supertree.depth+subtree.depth+1
    FROM category_closure AS supertree JOIN category_closure AS subtree
    WHERE subtree.ancestor = 5
    AND supertree.descendant = 12;

Situace 7: Identifikace kořene a listu

Dalšími často se vyskytujícími požadavky jsou právě na identifikaci, zda je daný uzel kořen nebo naopak list stromu. Z vlastností Closure Table vyplývá, že kořenový prvek má pouze jednoho „rodiče“ – sám sebe a list má naopak pouze jednoho potomka – opět sebe sama. Pomocí jednoduché podmínky a vnořeného SELECTu pak můžeme zjistit tyto požadované informace.

Identifikace kořene a listu:

SELECT c.*, cc.depth,
  IF((SELECT COUNT(*) FROM category_closure WHERE descendant = c.category_id)=1,1,0) is_root,
  IF((SELECT COUNT(*) FROM category_closure WHERE ancestor = c.category_id)=1,1,0) is_leaf
    FROM category c
    JOIN category_closure cc
      ON (c.category_id = cc.descendant)
    WHERE cc.ancestor = 1;

Závěr

Jak můžete vidět, je Closure Table poněkud netypickým a kostrbatým řešením. Důležité ale je, že je toto řešení funkční a oproti traverzování kolem stromu nemusíte myslet v „matematických počtech“. Pokud máte jakékoli nápady na vylepšení, optimalizaci či odstranění nějakých chyb, nebojte se přispět do komentářů.

Na můj článek navazuje Miroslav Paulík se svým článkem Dolování strukturovaných dat z databáze pomocí Closure Table – díl 1..

 
  • Filip Procházka (@HosipLan)

    Přece jenom, pořád je to zdaleka nejvhodnější řešení pro relační databáze.

    Díky moc za přehled, bude se hodit, až si budu dodělávat Closure Table pro Doctrine :)

    • Jan Voráček

      Možná bych to označil jako nejvhodnější univerzální řešení. Nicméně pokud databázový systém podporuje hierarchické dotazy, nebude lepší je využít?

      Jinak je ale zvláštní, že ačkoli se jedná o celkem zajímavé řešení, shánějí se o něm dost špatně nějaké informace.

  • Ahoj,

    díky za článek, doteď jsem používal metodu s parent_id a tohle je zajímavější :).

    Akorát u té 4. situace jsem dotaz trošku upravil (MySQL):

    UPDATE category_closure SET depth = depth-1 WHERE ancestor != descendant AND descendant IN (SELECT descendant FROM (SELECT * FROM category_closure) as did WHERE ancestor = 8;

    Nevím, jestli jsem něco nepřehlédl, ale podle tvého dotazu by hloubka u řádků s ancestor = 1 AND descendant IN (8, 9) zůstala dva, což po smazání kategorie s id 8 neplatí.

    Přehlížím něco? :)
    Díky a měj se.

    • Jan Voráček

      Výborně, máš pravdu :) Nevím, na co jsem myslel. Fixed.

      • Bumprask

        Čau, díky za článek a rozšíření obzoru ;-). Dle výše uvedených algoritmů jsem se snažil closure table implementovat a dospěl jsem k závěru, že tento dotaz (odstranění prvku a navázání potomků) nefunguje správně. Výše uvedený dotaz nenaváže potomky správně, pokud smažeme uzel, který má pod sebou více jak dvě větve. Je třeba změnit hloubku pouze u záznamů nadřazených danému uzlu tzv.

        UPDATE category_closure SET depth = depth-1
        WHERE ancestor != descendant
        AND descendant IN (SELECT descendant FROM (SELECT * FROM
        category_closure) as did WHERE ancestor = 8)
        AND ancestor NOT IN (SELECT descendant FROM (SELECT * FROM
        category_closure) as did WHERE ancestor = 8)

  • venoušek

    Ahoj, ještě, dodám odkaz na nesmrtelnou prezentaci.
    http://www.slideshare.net/…-strike-back#…
    na straně 77 je souhrn všech 4 metod

    closure table
    traverz. strom
    pomocí path (1/2)
    naivně pomocí parent

  • Ale oproti MPTT je to brutálně neefektivní, ne? Pokud budem mít stovky kategorií, zanořených třeba 5 úrovní, tak to budou tisíce řádků! Třeba na levneucebnice.cz je 3000 kategorí, zanořených do max. 4 úrovní. Tam se tohle musí splašit. Nota bene s tou hromadou joinů.

    • Diskobolos

      Testoval jsem closure table na stromu dmoz.org v MySQL a běhá to rychle (s patřičnými indexy).

  • Martin

    A co treba razeni, to se resi u tohoto navrhu jak?

    • Honza

      Taky by mě zajímalo, jak se řeší řazení

  • František

    Ad.Vložení nového záznamu na libovolné místo
    Neměly by se ještě nějak updatovat již existující následníci pro případ že bych prodlužoval řetěz?
    Např. kdybych do řetězu PC příslušenství → Klávesnice → Bluetooth vkládal „Bezdrátové“ a vzniklo tak PC příslušenství → Klávesnice → Bezdrátové → Bluetooth

    • František

      Omlouvám se, beru dotaz zpět – řeší to situace 6.

  • duskohu

    Ahoj, dakujem za clanok, nebolo by mozne pridat aj nejaky priklad na spracovanie vystupu z DB do ul-li stromu?

  • Ondřej Profant

    Pokud správně pozoruji, tak u Situace 5: Smazání celého podstromu je chyba. Smaže to relace celého podstromu a vrchol podstromu. Avšak již ne uzly v podstromu.

  • Stromy kupodivu vůbec neřeším. Nicméně tohle řešení jsem ještě neznal, takže díky za fajn článek!

  • hAssassin

    Ahoj, začínám si s closure tables trochu hrát a líbí se mi to. Když už nic, tak je to super na zopakování sql :-) A souhrn taky super…

    Každopádně mám dotaz. Dejme tomu že mám výše uvedený kategorie, ale kořenů může být víc (ala např. http://www.czc.cz, kde taky mají PC příslušenství, Komponenty a Počítače na jedniný kořenový úrovni). A otázka zní: jak vyberu celý strom se všemi kořenovými uzly, a ideálně i s informací o nejbližším kořenu?

    Po docela úsilném snažení (google na tuto tématiku mlčí jak hrob), jsem dospěl k něčemu takovému:

    SELECT c., cc2.ancestor as parent, cc.depth
    FROM category c
    JOIN category_closure cc ON (c.category_id = cc.descendant)
    LEFT JOIN category_closure cc2 ON (cc.descendant = cc2.descendant AND cc2.depth = 1)
    WHERE cc.ancestor IN (SELECT c.category_id FROM category c JOIN category_closure cc ON (c.category_id = cc.ancestor) GROUP BY cc.descendant HAVING COUNT(
    ) = 1)
    ORDER BY cc.depth, c.name;

    Tento dotaz mi pak vrátí:

    ±--------------±--------------------------±--------±--------+

    category_id name parent depth

    ±--------------±--------------------------±--------±--------+

    kde parent obsahuje ID nejbližšího předchůdce nebo NULL a depth hloubku zanoření od kořene.

    Celé to sice funguje, ale nevím jestli to je nejoptimálnější dotaz. Jak tedy vytáhnout celý strom přes všechny kořenové uzly (přidání jednoho globálního superkořenu se mi nelíbí)? Díky.

    • Jan Voráček

      Ahoj, closure table je způsob ukládání stromové struktury, nikoli více stromových struktur, tj. lesa. Closure table by měla obsahovat pouze jeden kořen, protože pokud ne, dostaneme se k dotazům, jaké jsi napsal. Ve většině DB systémů by to nebyl problém (tam ostatně není problém ani ukládání stromů), ale MySQL neumí používat indexy ve vnořených selectech a vnořený select v restrikci se vykonává mnohokrát.

      Jediným správným řešením tedy je přidání onoho „globálního superkořenu“.

      Snad jsem to nějak obstojně vysvětlil.

      • hAssassin

        Ahoj, díky za objasnění, myslel jsem si že jsou primárně určeny pro stromy a s lesy se pracuje obtížněji. Což je škoda. Taky mě napadlo si tu informaci o aktuálním rodiči přidat do closure tabulky, ale nevím jestli by to mělo nějaký valný přínos (nezkoušel jsem) a hlavně jestli by to něco neporušovalo.

        Ohledně MySQL a subselektů, pak je tedy trochu problém i dotaz pro získání kořene a listů, ne?

  • hAssassin

    Ahoj, trochu si lámu hlavu se smazaním jednoho prvku a převázání podstromu (4ka – už ji tu někdo opravoval). Myslím, že je špatně.

    Jde o to, smazat pouze jediný prvek a ostatní převázat. Tento příklad je však nedostačující v tom, že se přesouvají pouze listy, které listy zůstanou i po přesunu. Pokud by ale při mazání prvku 8 měli jeho potomci 9 a 10 další potomky (např. prvek 9 bude mít potomka 20 a 21), pak dotaz tam uvedený sníží hloubku i mezi 9 a jeho potomky (z 1 na 0!) a to je špatně. Hloubka se musí snížit pouze mezi všemi rodiči 8ky a jejich následníky.

    Trochu jsem upravil dotaz (pouze pro select, ale zdá se, že selektí dobře):

    SELECT ancestor, descendant, depth, depth-1 as new_depth
    FROM category_closure
    WHERE ancestor IN (SELECT ancestor FROM category_closure cc WHERE descendant = 8 and ancestor != descendant)
    AND descendant IN (SELECT descendant FROM category_closure WHERE ancestor = 8 AND descendant != ancestor)
    ORDER BY ancestor;

    Takže je tam chyba nebo jsem to blbě pohopil a už mi v tuto hodinu hrabe? Díky.

  • dub

    menu ve kterém nelze určit pořadí? to není moc vhodné

  • Valekol

    Tak jak je to s tím řazením? Někde jsem četl, že to lze udělat pomocí „string padded path enumeration“ (http://prezi.com/…s-and-trees/) – tedy přidá se sloupec s hodnotou podobné této: 0001–0003–0010. Já mám však pocit, že to stejně nebude fungovat. Ta čísla jsou IDčka položek a když budu mít třeba dvě položky na stejné úrovni, tak je to seřadí podle toho, která má vyšší/nižší ID. Já však chci mít možnost seřadit je podle sebe. Máte nějaké řešení? Mě napadlo přidat sloupec, ve kterém by se ukládalo pořadí v úrovni položky plus pořadí ve všech nadřazených úrovních. Asi takto:
    1 – stromy
    1/1 – listnaté
    1/1/1 – jasan
    1/1/2 – javor
    1/2 – jehličnaté
    1/2/1 – smrk
    1/2/2 – jedle …
    Ale ještě jsem to nezkoušel.

    • Rick from Sanatorium

      Closure table respektuju jako řešení pro obecné ukládání stromů – teoreticky (prakticky, např. s desetitisíci uzlů to může začít být zajímavé, z hlediska výkonnosti apod.).
      Řešení, které popisuješ ty, je vhodné pro ukládání stromů, u kterých víš, že např. počet poduzlů v uzlu reálně nepřekročí nějakou hranici (třeba milion) nebo nebude mít víc než např. tisíc úrovní (což jsou skoro všechny případy z ‚reálného světa‘). Pak si „cestu“ ke každému uzlu můžeš uložit takto a pak máš většinu zde popisovaných operace řádově jednodušších než closure table. Jo, a navíc nejen že druhá tabulka se ti kvadraticky nenafukuje – máš informace o uložení v jedné tabulce.

      • T_xy

        Closure table se nafukuje řádově stejně jako string path enumeration. Kvadraticky je to jen v případě, že se strom nevětví. String path u uzlu 10000 ale pak bude mít 60kB. To už bude problém ukládat a indexovat to zřejmě nepůjde vůbec, prohledávání tak bude zoufalé. Closure table bude mít hodně řádků, ale jinak bude fungovat bez větších problémů. Osobně bych doporučoval mít v primární tabulce odkaz na rodiče, v datech nebude žádná redundance a budou vždy konzistentní. Vedle této tabulky lze pak přidávat další struktury pro optimalizaci dotazů, třeba právě tabulku tranzitivního uzávěru uložené kostry grafu neboli closure table.