Metody ukládání stromových dat v relačních databázích

Stromové datové struktury představují pro relační databáze poměrně těžko stravitelné sousto. Problémy vyplývají ze samotné podstaty relačního databázového modelu, který není pro ukládání tohoto typu dat příliš vhodný. Dosáhnout toho, aby byla práce s těmito strukturami efektivní, představuje nelehký úkol. Tento článek se snaží přiblížit několik přístupů k ukládání stromových dat v relační databázi.

Úskalí relačních databází

Relační databázové systémy stále zůstávají nejpoužívanějším typem databázových systémů, i když máme již několik let k dispozici v mnoha ohledech pokročilejší objektové databáze (například gemstone). Jedna z největších výhod objektových databází je snadná práce se složitě strukturovanými daty. Naopak relační databáze využívající k ukládání dat plochých relačních tabulek mají s těmito daty značné potíže.

Konkrétním případem obtížně zpracovatelných dat jsou data s hierarchickou, respektive stromovou strukturou. V objektové databázi mohou být stromová data uložena přímo v takové podobě, jakou využívá aplikace, která se k této databázi připojuje. Naopak při použití relační databáze musíme data transformovat tak, abychom je mohli uložit do ploché relační tabulky, a při čtení dat z databáze je musíme zpětně transformovat do podoby stromu. Tento článek popisuje několik přístupů, které se dají použít pro ukládání stromových dat v relační databázi.

Úvod do popisu metod

Hlavní pozornost jsem věnoval datové struktuře a algoritmům, kterými se mohou stromová data zpracovávat (získávat a editovat). Příklady jsem realizoval v jazyce PHP pro jeho jednoduchost, úspornost a rozšířenost. Uvedené příklady ale není problém realizovat v jakémkoli jiném procedurálním jazyce. Rád bych zdůraznil, že veškerý programový kód v článku je zaměřen především na algoritmy, proto berte s nadhledem například způsob formátování výpisu stromu pomocí tvrdých mezer a <br />. Každý si samozřejmě tuto část může napsat dle svých potřeb. Jako ukázkový příklad stromové struktury jsem vybral strom kategorií zboží, se kterým se můžeme setkat v libovolném eShopu. Takový strom může vypadat například takto:

Obrázek č. 1: Příklad stromové struktury

Klasický přístup

Nejznámějším a také nejčastěji využívaným způsobem, který lze při ukládání stromových struktur do relační databáze použít, je model, kdy je součástí každého prvku stromu také reference na prvek rodičovský. Nejvýše postavený prvek stromu, zvaný kořen, má referenci nastavenou na 0 nebo NULL.

ID	NAME	PARENT_ID
1	Kategorie zboží	0
2	Procesory	1
3	Intel	2
4	Pentium IV	3
5	Celeron	3
6	AMD	2

Tabulka č. 1: Klasická datová struktura pro uložení stromu v relační tabulce

Získávání dat rekurzí

Pro získávání dat z takovéto tabulky se dá s úspěchem využít rekurzivní funkce, viz ukázka č. 1. Tato funkce se může volat z jakéhokoli uzlu stromu. Vypíše potomky příslušného uzlu s ID rovným argumentu $parent a pro všechny potomky je posléze volaná rekurzivně. Argument $level udává zanoření příslušného uzlu, který slouží pro rozlišení uzlu při výpisu stromu. Pro zobrazení celého stromu by se funkce volala s oběma argumenty nastavenými na nulu.

Ukázka č. 1: Rekurzivní funkce pro získání stromu z DB

function getTree($parent, $level) {
  $result = mysql_query(‚SELECT * FROM TREE WHERE PARENT_ID=‘.$parent);
  while ($row = mysql_fetch_assoc($result)) {
    echo str_repeat(„&nbsp;“,$level).$row[‚NAME‘].“<br />“;
    getTree($row[‚ID‘], $level++);
  }
}

Je zřejmé, že v době objektového programování bychom se s uvedeným příkladem asi nespokojili. Pravděpodobně bychom pro reprezentaci uvedeného stromu vytvořili třídu. Jednotlivé uzly stromu by vznikaly jako instance této třídy a každý uzel by současně skládal své podřízené uzly. Výsledkem by tedy byl rekurzivní objekt představující celý strom nebo jeho libovolnou část. Principy získání dat potřebných pro naplnění tohoto objektu by ovšem zůstaly zcela stejné. Uvedený algoritmus by se ale použil v rekurzivním konstruktoru této třídy. Následuje příklad třídy implementované v jazyce PHP.

Ukázka č. 2: Třída pro vytvoření rekurzivních objektů

Class CTreeNode
{
  var $id = 0;
  var $name =“;
  var $level = 0;
  var $childNodes = array();
  function CTreeNode($id,$name,$level)
  {
    $this->id=$id;
    $this->name=$name;
    $this->level=$level;
    $result = mysql_query(„SELECT * FROM TREE WHERE PARENT_ID=$id“);
     while ($r = mysql_fetch_assoc($result)) {
      $this->childNodes[] = new CtreeNode($r[‚ID‘], $r[‚NAME‘], $level++);
    }
  }
}

Třídu bychom samozřejmě museli doplnit o metody pro prezentaci dat, které by opět musely být rekurzivní a fungovaly by na obdobném principu. (Eventuelně by mohly využívat XSLT, pak by byl problém přenesen na transformační procesor.)

Získávání dat s využitím zásobníku

Druhou alternativou, kterou můžeme s úspěchem použít pro získání dat z databáze, je použití zásobníku. Využití zásobníku nám nepřináší žádnou úsporu SQL dotazů, ale přináší zvýšení efektivity aplikačního kódu. Místo rekurzivního volání funkce či metody se použije pouze obyčejný „while“ cyklus. Je zřejmé, že pro větší objem dat bude metoda s využitím zásobníku efektivnější. Následuje funkce implementovaná v jazyce PHP. Pro zásobník bylo využito pole, pro které jsou definovány funkce potřebné k práci se zásobníkem (push a pop).

Ukázka č. 3: Využití zásobníku pro získání stromu z DB

function getTree($nodeId)
{
  $stack = array();
  $level = 0;
  $res = mysql_query(‚SELECT ID, NAME FROM TREE WHERE ID=‘.$nodeId);
  $row = mysql_fetch_assoc($result);
  $row[‚LEVEL‘] = 0;
  array_push($stack, $row);
  while(count($stack)>0)
  {
    $r = array_pop($stack);
    echo str_repeat(„&nbsp;“,$r[‚LEVEL‘]).$r[‚NAME‘].“<br />“;
    $res = mysql_query(‚SELECT ID, NAME FROM TREE WHERE PARENT_ID=‘.$r[‚ID‘]);
    if(mysql_num_rows($res)>0) {
      $level = $r[‚LEVEL‘]+1;
    }
    while($row = mysql_fetch_assoc($result)) {
      $row[‚LEVEL‘] = $level;
      array_push($stack, $row);
    }
  }
}

Editace dat

Editace dat je v tomto případě naprosto triviální. Při ukládání nového uzlu stačí znát ID nadřazené kategorie. Přesun větve do jiné části stromu je také velice jednoduchý, stačí pouze změnit PARENT_ID daného uzlu.

Zhodnocení metody

Tato metoda je velice jednoduchá, snadno pochopitelná i realizovatelná. Editace dat je nenáročná a rychlá. Jediným problémem je získávání dat. V uvedeném příkladu by použití rekurzivní funkce na získání dat znamenalo provést pro n uzlů také n dotazů do databáze. Využití rekurzivní funkce je sice elegantní, ale není příliš efektivní. Určité zlepšení by mohlo přinést použití zásobníku. Počet dotazů do databáze ovšem zůstává stejný.

Možné modifikace metody

Pro zmenšení počtu dotazů bychom mohli využít způsob, kdy celý strom získáme jedním dotazem do pole polí a funkce, respektive konstruktor, by využily toto pole pro naplnění rekurzivního objektu. Zatížení databáze by se snížilo, ale zase bychom radikálně zvýšili paměťovou náročnost aplikace, která by takto data musela zpracovávat.

Další způsob, který bychom mohli použít ke snížení zátěže databáze, je v podstatě univerzální pro veškeré přístupy uvedené v tomto článku. Získaný strom bychom mohli v serializované podobě držet v databázi a naše aplikace by si ho načítala jako BLOB položku, na kterou by následně musela provést deserializaci. Při jakékoli změně stromu by se do databáze musela ukládat jeho aktuální podoba. Takto ale můžeme pracovat pouze se stromem jako celkem, což může být někdy nedostačující. Dalšímu možnému rozšíření se věnuje následující metoda.

Rozšíření ploché tabulky

Pro zvýšení efektivity modelu z předchozí části, můžeme datovou strukturu rozšířit o další atributy, které nám umožní rychlejší přístup k datům. Bude to atribut ORD, který představuje pořadí uzlu v daném stromu, a atribut LEVEL, který představuje zanoření, respektive úroveň uzlu.

ID	NAME	PARENT_ID	ORD	LEVEL
1	Kategorie zboží	0	1	0
2	Procesory	1	2	1
3	Intel	2	3	2
4	Pentium IV	3	4	3
5	Celeron	3	5	3
6	AMD	2	6	2

Tabulka č. 2: Rozšíření klasického přístupu o pořadí a hloubu zanoření

Získávání dat

Takto uložená data můžeme samozřejmě vypisovat stejným způsobem jako v prvním případě, ale můžeme také použít velice jednoduchý způsob výpisu, při kterém využijeme přidané atributy.

Ukázka č. 4: Přímý výpis stromu z databáze

function getTree() {
  $result = mysql_query(‚SELECT * FROM TREE ORDER BY ORD ASC‘);
  while ($row = mysql_fetch_array($result)) {
    echo str_repeat(„&nbsp;“,$row[‚LEVEL‘]).$row[‚NAME‘].“
„;
  }
}

Jak je vidět z příkladu, výpis je velice jednoduchý a rychlý. Na databázi stačí poslat pouze jeden dotaz.

Editace dat

Jednoduchost, kterou jsme dosáhli při získávání dat, byla vykoupena náročností vkládání nových dat, a to především kvůli nutnosti dopočítat údaje o hloubce a hlavně pořadí. Zjištění hloubky představuje triviální přičtení čísla 1 k hloubce nadřazeného uzlu. Při vložení ale musíme také zadat pořadí. Pokud se záznamy řadí podle času, přidáme jednoduše záznam na první nebo poslední místo mezi dětmi v příslušné úrovni. Jedinou podmínkou je následný UPDATE všech záznamů s větším a stejným pořadím, než je pořadí vkládaného záznamu. Při vkládání záznamů řazených dle abecedy je situace trochu složitější, musíme totiž nejprve setřídit děti daného uzlu a zjistit, na jaké místo přijde náš nový záznam.

Zhodnocení metody

Popsaná metoda umožňuje jednoznačně nejrychlejší způsob výpisu dat. Rychlost výpisu je ale vykoupena složitostí vkládání. Jelikož ve většině případů preferujeme rychlost výpisu před rychlostí editace, nepředstavuje toto omezení příliš velký problém.

Traverzování kolem stromu

Traverzování kolem stromu, respektive Modified Preorder Tree Traversal Algoritmus, je dalším ze způsobů, kterým můžeme rozšířit datovou strukturu pro uložení stromové struktury do relační databáze. Princip spočívá v ohodnocení uzlů stromu dvěma hodnotami tím způsobem, že od kořenu obcházíme všechny větve stromu a postupně doplňujeme pravou a levou hodnotu uzlu, dokud se nevrátíme zpět ke kořenu. Kořen má tím pádem nejmenší levou a největší pravou hodnotu ze všech uzlů stromu. Náš zkušební příklad bychom mohli ohodnotit způsobem, který ukazuje obrázek č. 1.

Obrázek č. 2: Způsob ohodnocení uzlů traverzováním kolem stromu

ID	NAME	PARENT_ID	LFT	RGT
1	Kategorie zboží	0	1	22
2	Procesory	1	2	15
3	Intel	2	3	8
4	Pentium IV	3	4	5
5	Celeron	3	6	7
6	AMD	2	9	14

Tabulka č. 3: Datová struktura a hodnoty získané traverzováním kolem stromu

Získávání dat

Z obrázku č. 1 můžeme vyčíst, že podřízené uzly mají pravou a levou hodnotu vždy v intervalu nadřízeného uzlu. Všechny uzly nacházející se pod daným uzlem se dají získat dotazem na všechny uzly s levou hodnotou v intervalu pravé a levé hodnoty daného uzlu.

Následující příklad představuje algoritmus, kterým získáme libovolnou část stromu z databáze pouze dvěma dotazy. Jelikož v tabulce neukládáme úroveň zanoření, musíme použít zásobník pravých hodnot k získání úrovně daného uzlu.

Ukázka č. 5: Výpis stromu z databáze (tree traversal)

function getTree($nodeId) {
  $result = mysql_query(‚SELECT LFT, RGT FROM TREE WHERE ID=‘.$nodeId);
  $row = mysql_fetch_array($result);
  $rightStack = array();
  $result = mysql_query(‚SELECT NAME, LFT, RGT FROM TREE WHERE LFT BETWEEN ‚.$row[‚LFT‘].‘ AND ‚.$row[‚RGT‘].‘ ORDER BY lft ASC‘);
  while ($row = mysql_fetch_array($result)) {
    if (count($rightStack)>0) {
      while ($rightStack[count($rightStack)-1]<$row[‚RGT‘]) {
        array_pop($rightStack);
      }
    }
    echo str_repeat(„&nbsp;“,count($rightStack)).$row[‚NAME‘].“<br >“;
    $rightStack[] = $row[‚RGT‘];
  }
}

Uvedený způsob nemá pouze výhodu rychlého získání stromu z databáze, ale můžeme poměrně efektivně získávat další informace. Například pokud chceme vědět, kolik uzlů je podřízených příslušnému uzlu, a známe přitom jeho pravou a levou hodnotu, zjistíme tuto hodnotu jednoduchým výpočtem (RGT-LFT-1)/2. Pokud chceme zjistit cestu od daného uzlu ke kořenu, stačí abychom se dotázali na všechny uzly s LFT menší než LFT daného uzlu a RGT větší než RGT tohoto uzlu. Takto získáme cestu pomocí jednoho dotazu. Například pro Duron bychom cestu ke kořenu získali dotazem SELECT * FROM TREE WHERE LFT<10 AND RGT>11.

Editace dat

Rychlost získávání dat je opět vykoupena složitostí modifikace struktury stromu. Nelze jednoduše vkládat nové záznamy. Po každém vložení je nutné přečíslovat levé a pravé hodnoty.

Ukázka č. 6: Aktualizace záznamů v databázi (tree traversal)

function rebuildTree($parent, $left) {
  $right = $left+1;
  $result = mysql_query(‚SELECT ID, NAME FROM TREE WHERE PARENT_ID=‘.$parent);
  while ($row = mysql_fetch_array($result)) {
    $right = rebuild_tree($row[‚ID‘], $right);
  }
  mysql_query(‚UPDATE TREE SET LFT=‘.$left.‘, RGT=‘.$right.‘ WHERE ID=‘.$parent);
  return $right+1;
}

Zhodnocení metody

Tato metoda je pravděpodobně nejkomplexnější ze všech uvedených metod a přináší nejvíce možností pro jednoduché získávání dat z databáze. Tyto výhody jsou opět vykoupeny složitějším ukládáním a změnou struktury stromu.

Zhodnocení probrané metodiky

Uvedené metody nejsou zcela určitě úplným výčtem všech možných přístupů, ale patří k těm nejčastěji používaným. Je zřejmé, že nasazení objektové databáze na tento typ dat by přineslo razantní zjednodušení práce a pravděpodobně také zrychlení aplikace.

Bohužel většímu nasazení objektových databází brání především důvody historické (valná většina starších systémů využívá relační databáze) a ekonomické. Využití objektových databází rovněž ubližuje obecná představa, že co je objektové, to je pomalé.

Starší komentáře ke článku

Pokud máte zájem o starší komentáře k tomuto článku, naleznete je zde.