Nested Set Model – reprezentace hierarchických dat v relační databázi

Většina dnešních webových aplikací pracuje s hierarchickými daty. Nejčastějším úložištěm dat takových aplikací jsou relační databáze, ale ty nejsou uzpůsobeny k ukládání hierarchických struktur a s tímto problémem se musí programátor (databázový specialista) nějak vyrovnat.

Adjancency List Model

Adjancency List Model je vznešeným názvem nejpřímočařejšího a asi nejpoužívanějšího řešení tohoto problému. Trpí ale několika nedostatky.

Implementace je jednoduchá: v databázové tabulce je akorát potřeba přidat sloupec pro cizí klíč rodiče. Z toho plyne, že dál jak do hloubky jedna se s SQL dotazem obecně nedostaneme. Pokud tedy chceme vytvořit navigační lištu (breadcrumbs) s cestou z aktuální kategorie až na první úroveň, musíme postupně rekurzivně sérií SQL dotazů zjišťovat předka další a další nadřazené kategorie. (Za předpokladu, že naše hierarchie může být libovolně hluboká.)

Nested Set Model

Nested Set Model je složitější koncept, pomocí kterého už nebudeme muset rekurzivně volat mnoho SQL dotazů při získávání dat. Jak už to ale v programování bývá, lepší efektivita jedné operace je vyvážena horší efektivitou jiné operace. Černého Petra si v případě Nested Set Modelu vytáhlo insertování a mazání.

Princip

Obrázek znázorňující hierarchii jako množinový systém, podkategorie jdou podmnožinami.
Jak tedy Nested Set Model funguje? Hierarchickou strukturu si můžeme představit jako množinový systém (viz obrázek) a ke každé položce připojit dvě čísla left a right a to tak, aby pro každou položku A platilo, že interval tvořený A.left a A.right byl podintervalem všech B.left a B.right, kde B je předek A. Jasnější to bude na dalším obrázku. Například kategorie „sportovní“ má left=3 a right=4, což je podinterval intervalu [2,7] (left a right nadkategorie „osobní“) a [1,12] (root kategorie „vozidla“), ovšem [3,4] není podintervalem např. [8,11] („nákladní“).
Obrázek znázorňující hierarchii společně s hodnotami left a right.

Využití

K čemu je nám taková struktura dobrá? Tak například získání cesty z dané kategorie až do vrcholu už lze udělat na jeden SQL dotaz – vybereme ty řádky, jejichž left a right jsou nadintervaly left a right našeho vrcholu. Zní to hrozně, ale ve skutečnosti je to jednoduchý WHERE.

SELECT parent.name
FROM `category` AS node , `category` AS parent
WHERE parent.left < node.left AND parent.right > node.right
AND node.id = 'odkud hledam cestu'
ORDER BY parent.left

A co získat celou hierarchickou strukturu správně uspořádanou a se sloupečkem „deepth“, tak abychom ji mohli jednoduše (na jeden průchod) vypsat jako např. menu a to opět na jeden SQL dotaz? Když se pozorně podíváme na obrázek zjistíme, že stačí vrcholy uspořádat podle left. Hloubku už umíme spočítat, to je počet vrcholů na cestě do kořene. V dotazu ještě použijeme malou fintu: při počítání hloubky každý vrchol započítá i sám sebe, ale od výsledku nakonec odečte 1. Je to proto, abychom takovým dotazem zísali i kořen, který žádné předky nemá.

SELECT node.name, count(parent.name)-1 as 'deepth'
FROM  `category` AS node, `category` AS parent
WHERE node.left >= parent.left
AND node.right <= parent.right
GROUP BY node.name
ORDER BY node.left

Výstup pro příklad s vozidly by vypadal takto:

name deepth
vozidla 0
osobni 1
sportovni 2
rodinna 2
karavany 3
nakladni 1
kamiony 2

Úpravy hierarchie

Jak je to tedy s mazáním a přidáváním položek? Začněme přidáváním.

Insert

Když chceme přidat novou kategorii, označme ji „nová“, jako přímého potomka jiné kategorie, označme ji „předek“, potřebujeme si pro ni vytvořit „místo“ v našem číslování. Nejpreve posuneme předek.right a všechna větší čísla o 2, tedy všem vrcholům, které mají hodnoty left nebo right větší nebo rovny předek.right je zvětšíme o 2. Tímto posunem získáme „místo“ (předchozí hodnota předek.right a předek.right+1 jsou nyní volné), do kterého můžeme umístit nový vrchol. Nastavíme nová.left=předek.right, nová.right=předek.right+1 a jsme hotovi.
Obrázek znázorňující vložení prvku a přepočítání potřebných hodnot.

UPDATE `category` SET `right`=`right`+2 WHERE `right`>={parentRight}
UPDATE `category` SET `left`=`left`+2 WHERE `left`>{parentRight}
INSERT INTO category(..., left, right) VALUES (...,{parentRight}, {parentRight}+1)
Delete

Mohli bychom sice jednoduše kategorii smazat a dál nic neřešit, ale potom by rozsah hodnot v left a right mohl neúnosně narůst a vznikaly by „díry“, horší je ovšem, že bychom pak mohli v databázi ponechat sirotky – kategorie, do kterých z rootu nevede žádná cesta.

Odstranění dané kategorie společně s jejími následníky je s Nested Set Modelem hračka. Jsou to ty kategorie, jejichž left a right jsou podintervalem dané kategorie.

DELETE FROM `category` WHERE `left` >= {removeLeft} and `right` <= {removeRight}

Posunutí ostatních vrcholů je postavené na podobném principu jako při insertu.

UPDATE `category` SET
`right`=`right`-{removeRight-removeLeft+1},
`left`=`left`-{removeRight-removeLeft+1}
WHERE `left`>{removeRight}

Tímto příkazem posuneme všechny vrcholy, které jsou celé "vpravo" od odstraňovaného vrcholu. Ještě potřebujeme posunout vrcholy, které jsou "vpravo" jenom z části, tedy jen svojí hodnotou right - to jsou rodiče našeho odstraňovaného vrcholu.

UPDATE `category` SET
`right`=`right`-{removeRight-removeLeft+1},
WHERE `right`>{removeRight} AND `left`<{removeLeft}

Závěr

Použití Nested Set Model poskytuje efektivnější způsob uchování hierarchických struktur v relačních databázích, především když je z databáze čteno častěji, než do ní zapisováno.

Pro zájemce o pokusy s ukázkovou tabulkou uvádím i její SQL export pro MySQL.

CREATE TABLE `category` (
  `name` varchar(128) NOT NULL,
  `left` int(11) NOT NULL,
  `right` int(11) NOT NULL,
  PRIMARY KEY  (`name`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

INSERT INTO `category` (`name`, `left`, `right`) VALUES
('kamiony', 11, 12),
('karavany', 6, 7),
('nakladni', 10, 13),
('osobni', 2, 9),
('rodinna', 5, 8),
('sportovni', 3, 4),
('vozidla', 1, 14);

Comments 5

  1. Jiří Prexl wrote:

    Dotaz pro posunutí ostatních vrcholů po odstranění kategorie by měl být s podmínkou:
    WHERE `right`>{removeRight}
    aby došlo i k přepočtu nadřazené kategorie.

    Posted 01 Zář 2010 at 19.51
  2. Steves wrote:

    Děkuji za upozornění, článek jsem opravil.

    Posted 18 Zář 2010 at 20.01
  3. MD wrote:

    Da se to vyuzit i na nestromovou hiearchii? Tzn. kdyz existuje vice cest od listu ke korenu?

    Posted 04 Kvě 2011 at 8.55
  4. Steves wrote:

    Obávám se, že nějak jednoduše se to na nestromovou hierarchii předělat nedá. Nicméně, pokud bude tabulka zachycující hierarchii obsahovat pouze cizí klíče na opravdové záznamy, stačí pak takové listy prostě přidat tolikrát, kolik do nich vede cest z kořene — tedy povolit duplicity.

    Posted 05 Kvě 2011 at 15.55
  5. Maw wrote:

    Velmi pěkný a užitečný článek, děkuji..

    Posted 14 Kvě 2012 at 12.09

Trackbacks & Pingbacks 1

  1. From Anonymní on 28 Kvě 2013 at 17.30

    http://www.cashloanssimple.co.uk/...

    Really the only bad thing about these is that they cost a very payday advance since they aren…

Post a Comment

Your email is never published nor shared. Required fields are marked *