Closure Table – stromy v MySQL trochu jinak

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í.

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é |
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í.

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ávesnice → Bezdrá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)
-
Tomáš Pešek (@pesovo)
-
venoušek
-
Tomáš Fejfar
-
Diskobolos
-
-
Martin
-
Honza
-
-
František
-
František
-
-
duskohu
-
Ondřej Profant
-
Patrik Šíma
-
hAssassin
-
hAssassin
-
dub
-
Valekol
-
Rick from Sanatorium
-
T_xy
-
-