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(„ “,$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(„ “,$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(„ “,$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(„ “,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.
Mohlo by vás také zajímat
-
4 tipy, jak na efektivní úsporu při rozjezdu podnikání
3. ledna 2023 -
AI na dosah ruky: Jak je to s AI v osobních zařízeních?
22. ledna 2024 -
AI v programování: Jak používat GitHub Copilot (část 2)
19. února 2024
Nejnovější
-
Jak chránit webové stránky před Web/AI Scrapingem
27. listopadu 2024 -
Jaký monitor je nejlepší k novému Macu Mini?
25. listopadu 2024 -
Výkonný a kompaktní: ASOME Max Studio s výjimečným poměrem cena/výkon
11. listopadu 2024 -
Šokující data od Microsoftu: Kyberútoky rostou o stovky procent!
8. listopadu 2024
Stepan
Pro 6, 2009 v 2:30děkuji za moc pěkný článek,
jen mi není moc jasná jedna věc a tou je, že Váš příklad je trošku nerealistický. Dejme tomu, že máme 5 výrobců pamětí. Jeden vyrábí 6 druhů pamětí, další tři…(všechny na stejné úrovni). Jak to ovlivní strom přidávání a hledání ve stromu?
Děkuji.
Jan Turoň
Kvě 17, 2010 v 14:25Dobrý nápad, ale metodu rebuildTree je možno zapsat mnohem efektivněji pomocí addItem a removeItem:
function addItem($item, $parent, $parent_LFT) {
$parent_RTG = $parent_LFT+1;
mysql_query(„UPDATE TREE SET RTG=RTG+2 WHERE LFT>=$parent_LFT“);
mysql_query(„INSERT INTO TREE SET name=’$item‘,parent=$parent,LFT=$parent_LFT,RTG=$parent_RTG“);
}
removeItem analogicky. (Kód by měl být ještě uzavřen do transakce a ošetřen proti SQL inject, ale to už není podstata problému.)
Mario
Led 7, 2012 v 19:34Metoda „getTree“ u „Traverzování kolem stromu“ by mala mat osetrenu podmienku while:
while ($rightStack[count($rightStack)-1]<$row['RGT'] and !empty($rightStack)) {…
Jim
Čvn 17, 2012 v 14:05Super pomoc tato stranka… Ale v ukazke c.1 je chyba $level++ by mal byt ++$level ci? Ako zaciatocnik som bol s toho asi 2 dni hotovy :)
Jim
Čvn 17, 2012 v 14:12Aj snad by pomohlo tuto problematiku viac rozviest pre zaciatocnikov. Osobne uz co-to s php a sql viem ale toto mi pride aj tak dost zlozite. Mozno by pomohlo to este viac rozmenit na drobne… (Od prvotneho zadavania dat do stromu atd….) Ked do toho nevidite tak sa to celkom tazko chape…
SM4JL
Srp 28, 2012 v 11:22Nekomu by mohl pomoci k pochopeni clanek Jakuba Vrany: http://php.vrana.cz/traverzovani-kolem-stromu-prakticky.php
Petr
Kvě 20, 2013 v 15:57Dobrý den,
moc děkuji za tento článek, velice povedené. Rád bych poprosil o radu, pokud uvažujeme, že nechceme vypisovat celou strukturu, ale pouze určitou její část (úroveň). Jako příklad řekněme, že bych rád vypsal veškeré položky 3 úrovně. (tedy: Pentium, Celeron, Duron, Athlon…).
Děkuji moc za odpověď
Martin
Srp 23, 2018 v 14:37Pre male stromy (do niekolko MB) treba pouzit ukladanie celeho stromu (RAMky je dost a procesor je rychly). Pre velke stromy nepomoze relacna databaza nijako, treba pouzit grafove databazy (tie by mali fungovat v RAM a priebezne si ukladat stav po blokoch). Moze pomoct aj kombinacia – struktura stromu v RAM alebo ako celok v BLOBe a atributy v relacnej databaze. Nepoznam ziadnu beznu aplikaciu, ktora by potrebovala velky strom (naozaj velky a naozaj strom).