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 |
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
$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∙
{
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
{
$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 |
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
$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 |
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)
$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)
$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Θ.
