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

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é

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

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ž n² 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..