<meta http-equiv='pics-label' content='(pics-1.1 "http://www.icra.org/ratingsv02.html" comment "ICRAonline EN v2.0" l gen true for "http://interval.cz" r (nz 1 vz 1 lz 1 oz 1 cz 1) "http://www.rsac.org/ratingsv01.html" l gen true for "http://interval.cz" r (n 0 s 0 v 0 l 0))' />
<h2>Metody uklßdßnφ stromov²ch dat v relaΦnφch databßzφch</h2>
<p id='prepend'>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.</p>
<h3>┌skalφ relaΦnφch databßzφ</h3>
<p>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 <a href='http://www.gemstone.com'>gemstone</a>). 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.</p>
<p>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.</p>
<h3>┌vod do popisu metod</h3>
<p>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 <code><br /></code>. 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:</p>
<p>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.</p>
<span class='comment'>Tabulka Φ. 1: Klasickß datovß struktura pro ulo₧enφ stromu v relaΦnφ tabulce</span>
</div>
<h4>Zφskßvßnφ dat rekurzφ</h4>
<p>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 <samp>ID</samp> rovn²m argumentu <samp>$parent</samp> a pro vÜechny potomky je poslΘze volanß rekurzivn∞. Argument <samp>$level</samp> 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.</p>
<p>Ukßzka Φ. 1: <em>Rekurzivnφ funkce pro zφskßnφ stromu z DB</em></p>
<div class='sample'>
function getTree($parent, $level) {
<br /> $result = mysql_query('SELECT * FROM TREE WHERE PARENT_ID='.$parent);
<br /> while ($row = mysql_fetch_assoc($result)) {
<p>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.</p>
<p>Ukßzka Φ. 2: <em>T°φda pro vytvo°enφ rekurzivnφch objekt∙</em></p>
<div class='sample'>
Class CTreeNode
<br />{
<br /> var $id = 0;
<br /> var $name ='';
<br /> var $level = 0;
<br /> var $childNodes = array();
<br /> function CTreeNode($id,$name,$level)
<br /> {
<br /> $this->id=$id;
<br /> $this->name=$name;
<br /> $this->level=$level;
<br /> $result = mysql_query("SELECT * FROM TREE WHERE PARENT_ID=$id");
<br /> while ($r = mysql_fetch_assoc($result)) {
<br /> $this->childNodes[] = new CtreeNode($r['ID'], $r['NAME'], $level++);
<br /> }
<br /> }
<br />}
</div>
<p>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.)</p>
<h4>Zφskßvßnφ dat s vyu₧itφm zßsobnφku</h4>
<p>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 (<code>push</code> a <code>pop</code>).</p>
<p>Ukßzka Φ. 3: <em>Vyu₧itφ zßsobnφku pro zφskßnφ stromu z DB</em></p>
<div class='sample'>
function getTree($nodeId)
<br />{
<br /> $stack = array();
<br /> $level = 0;
<br /> $res = mysql_query('SELECT ID, NAME FROM TREE WHERE ID='.$nodeId);
<br /> $res = mysql_query('SELECT ID, NAME FROM TREE WHERE PARENT_ID='.$r['ID']);
<br /> if(mysql_num_rows($res)>0) {
<br /> $level = $r['LEVEL']+1;
<br /> }
<br /> while($row = mysql_fetch_assoc($result)) {
<br /> $row['LEVEL'] = $level;
<br /> array_push($stack, $row);
<br /> }
<br /> }
<br />}
</div>
<h4>Editace dat</h4>
<p>Editace dat je v tomto p°φpad∞ naprosto trivißlnφ. P°i uklßdßnφ novΘho uzlu staΦφ znßt <samp>ID</samp> nad°azenΘ kategorie. P°esun v∞tve do jinΘ Φßsti stromu je takΘ velice jednoduch², staΦφ pouze zm∞nit <samp>PARENT_ID</samp> danΘho uzlu.</p>
<h4>Zhodnocenφ metody</h4>
<p>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².</p>
<h4>Mo₧nΘ modifikace metody</h4>
<p>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.</p>
<p>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.</p>
<h3>RozÜφ°enφ plochΘ tabulky</h3>
<p>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 <samp>ORD</samp>, kter² p°edstavuje po°adφ uzlu v danΘm stromu, a atribut <samp>LEVEL</samp>, kter² p°edstavuje zano°enφ, respektive ·rove≥ uzlu.</p>
<span class='comment'>Tabulka Φ. 2: RozÜφ°enφ klasickΘho p°φstupu o po°adφ a hloubu zano°enφ</span>
</div>
<h4>Zφskßvßnφ dat</h4>
<p>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.</p>
<p>Ukßzka Φ. 4: <em>P°φm² v²pis stromu z databßze</em></p>
<div class='sample'>
function getTree() {
<br /> $result = mysql_query('SELECT * FROM TREE ORDER BY ORD ASC');
<br /> while ($row = mysql_fetch_array($result)) {
<p>Jak je vid∞t z p°φkladu, v²pis je velice jednoduch² a rychl². Na databßzi staΦφ poslat pouze jeden dotaz.</p>
<h4>Editace dat</h4>
<p>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 <samp>1</samp> 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² <samp>UPDATE</samp> 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.</p>
<h4>Zhodnocenφ metody</h4>
<p>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.</p>
<h3>Traverzovßnφ kolem stromu</h3>
<p>Traverzovßnφ kolem stromu, respektive <strong>Modified Preorder Tree Traversal Algoritmus</strong>, 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.</p>
<span class='comment'>Tabulka Φ. 3: Datovß struktura a hodnoty zφskanΘ traverzovßnφm kolem stromu</span>
</div>
<h4>Zφskßvßnφ dat</h4>
<p>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.</p>
<p>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.</p>
<p>Ukßzka Φ. 5: <em>V²pis stromu z databßze (tree traversal)</em></p>
<div class='sample'>
function getTree($nodeId) {
<br /> $result = mysql_query('SELECT LFT, RGT FROM TREE WHERE ID='.$nodeId);
<br /> $row = mysql_fetch_array($result);
<br /> $rightStack = array();
<br /> $result = mysql_query('SELECT NAME, LFT, RGT FROM TREE WHERE LFT BETWEEN '.$row['LFT'].' AND '.$row['RGT'].' ORDER BY lft ASC');
<br /> while ($row = mysql_fetch_array($result)) {
<br /> if (count($rightStack)>0) {
<br /> while ($rightStack[count($rightStack)-1]<$row['RGT']) {
<p>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 <samp>(RGT-LFT-1)/2</samp>. Pokud chceme zjistit cestu od danΘho uzlu ke ko°enu, staΦφ abychom se dotßzali na vÜechny uzly s <samp>LFT</samp> menÜφ ne₧ <samp>LFT</samp> danΘho uzlu a <samp>RGT</samp> v∞tÜφ ne₧ <samp>RGT</samp> tohoto uzlu. Takto zφskßme cestu pomocφ jednoho dotazu. Nap°φklad pro Duron bychom cestu ke ko°enu zφskali dotazem <samp>SELECT * FROM TREE WHERE LFT<10 AND RGT>11</samp>.</p>
<h4>Editace dat</h4>
<p>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.</p>
<p>Ukßzka Φ. 6: <em>Aktualizace zßznam∙ v databßzi (tree traversal)</em></p>
<div class='sample'>
function rebuildTree($parent, $left) {
<br /> $right = $left+1;
<br /> $result = mysql_query('SELECT ID, NAME FROM TREE WHERE PARENT_ID='.$parent);
<br /> while ($row = mysql_fetch_array($result)) {
<br /> $right = rebuild_tree($row['ID'], $right);
<br /> }
<br /> mysql_query('UPDATE TREE SET LFT='.$left.', RGT='.$right.' WHERE ID='.$parent);
<br /> return $right+1;
<br />}
</div>
<h4>Zhodnocenφ metody</h4>
<p>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.</p>
<h3>Zhodnocenφ probranΘ metodiky</h3>
<p>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.</p>
<p>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Θ.</p>
<div class='page-right-box reading'><h3 title='NejΦten∞jÜφ Φlßnky za poslednφch 14 dn∙'>NejΦten∞jÜφ</h3><div class='page-right-box-in'><ul><li><a href='http://interval.cz/__redirect/redirect.asp?what=interval_offline&url=http://interval.cz/clanek.asp?article=3829'>Interval.cz a jeho Φtenß°i v roce 2005</a></li><li><a href='http://interval.cz/__redirect/redirect.asp?what=interval_offline&url=http://interval.cz/clanek.asp?article=3830'>Pou₧φvßme nßvrhovΘ vzory v .NET - Singleton</a></li><li><a href='http://interval.cz/__redirect/redirect.asp?what=interval_offline&url=http://interval.cz/clanek.asp?article=3827'>SUN Java Studio Creator</a></li><li><a href='http://interval.cz/__redirect/redirect.asp?what=interval_offline&url=http://interval.cz/clanek.asp?article=3824'>Perl-compatible regulßrnφ v²razy v PHP - modifikßtory a lφnΘ kvantifikßtory</a></li><li><a href='http://interval.cz/__redirect/redirect.asp?what=interval_offline&url=http://interval.cz/clanek.asp?article=3831'>GNU Gettext - sprßva p°eklad∙</a></li></ul></div></div><div class='page-right-box cauldron'><h3 title='Nejdiskutovan∞jÜφ Φlßnky za poslednφch 21 dn∙'>Diskuznφ kotel</h3><div class='page-right-box-in'><ul><li><a href='http://interval.cz/__redirect/redirect.asp?what=interval_offline&url=http://interval.cz/clanek.asp?article=3818' title='(36 komentß°∙)'>PHP a MS SQL - vklßdßnφ a naΦφtßnφ soubor∙</a></li><li><a href='http://interval.cz/__redirect/redirect.asp?what=interval_offline&url=http://interval.cz/clanek.asp?article=3811' title='(26 komentß°∙)'>GNU Gettext - prvnφ kroky</a></li><li><a href='http://interval.cz/__redirect/redirect.asp?what=interval_offline&url=http://interval.cz/clanek.asp?article=3829' title='(20 komentß°∙)'>Interval.cz a jeho Φtenß°i v roce 2005</a></li><li><a href='http://interval.cz/__redirect/redirect.asp?what=interval_offline&url=http://interval.cz/clanek.asp?article=3815' title='(11 komentß°∙)'>H°φchy pro ÜφlenΘho korektora - jak se vyhnout zbyteΦn²m chybßm</a></li><li><a href='http://interval.cz/__redirect/redirect.asp?what=interval_offline&url=http://interval.cz/clanek.asp?article=3825' title='(11 komentß°∙)'>Ovlßdacφ prvok CAPTCHA v ASP.NET</a></li></ul></div></div>
