Názory k článku
Stromy

Děkuji za pro mne zajímavý článek.

V praxi je možno se setkat i se stromy jiného typu, než je zde uvedený příklad. Jak jsem pochopil, v uvedeném příkladu má každé dítě maximálně jednoho rodiče. Tento předpoklad není například splněn u databáze kusovovníku výrobků, kde nějaká sestava často vstupuje do různých nadsestav. Chtěl bych se proto zeptat, zda umí s takovýmto stromem pracovat zde uvedené patche pro PostgreSQL? Pokud jde o "genealogický identifikátor" tak je zřejmé, že ten by si s takovým stromem neporadil.

S tim souvisi jeden z nejhezsich matfyzackych vtipu (autorem je Xofon):

Proc parez nemuze byt strom?
Protoze obsahuje kruznice!

S tym autorstvom by som si nebol tak isty, tazko sa to dokazuje :-)

Důkaz sporem by nemusel být tak těžký. :-)
--------
Nejhezčí matfyzácký ftip je:
Matfyzák - je krásný a inteligentní.
Matfyzačka - je taky krásný a inteligentní.

IMO, typicka matfyzacka reakcia :-)

No dovedu si predstavit, ze pri urcite konstrukci gi by se je dalo pouzit i pro takove grafy.

Jeden o voze, druhý o koze. Strom má o jednu hranu méně, než má uzlů. Přidáním další hrany do stromu vznikne nestrom. Pokud chcete nějakou obecnou hierarchii, musíte si to zřejmě upravit.

Kusovnik soucasti je jedna vec.
Cely strom (rozpad kusovniku) je jina vec.
Pouziti konkeretniho kusovniku v soucasti nebo zakazce
by rozhodne nemelo byt ve stejne tabulce.

Mýlíte.se. Uzel stromu musí mít sice jen jediného předka - mezi ním a potomky je relace 1:N - ale to neznamená, že OBSAH některých uzlů nemůže být shodný. Předpokládám, že i když se stejná podsestava objevuje ve více sestavách, každý kus můžete zamontovat pouze do jediné z nich.
Předpokládejme, že každý záznam obsahuje vlastní jedinečný identifikátor a identifikátor předka. Jde vlastně o identifikátory uzlů, které definují strom - ale o vlastním obsahu uzlů neříkají vůbec nic. (Jedná se pouze o vazební identifikátory). Pokud se tatáž podsestava může opakovat vícekrát v různých kontextech, lze to řešit stejně, jako ve všech obdobných případech tohoto typu. Dalším prvkem záznamu bude identifikátor obsahu (tedy sestav) a pro vlastní sestavy vytvoříme číselník, ve kterém se už každá objeví pouze jedenkrát. Ke každé sestavě z číselníku snadno zjistíme všechny výskyty a ke každěmu z nich všechny předky i potomky. Stačí na to operace join.

Zdravim. Doufam, ze diskuse neni mrtva. Cetl jsem pomerne pozorne vsechno, co bylo napsano, ale nenasel jsem to, co jsem hledal. Naproti tomu jsem nasel to, co je problemovym uzlem ve Vasi debate. Ja to podam z jine strany. Mam pred sebou velke datove soubory, ze kterych bych chtel ziskat prehled o strukture. Nevidim, jestli je to strom, nevim do jake miry jsou data konzistentni a mam to zjistit. Podobne to je, kdyz znam priblizne strukturu, a hledam napriklad chybu. Vzdy musim nejak zacit, a strukturu dohledavat. Neznam rodice, neznam deti. Narazim na uzel a jdu podle nejake uvahy. Kdyz nebude spravna, zkoriguji, rozsirim dotazy a k tomu musim vytvorit doslova sit, ktera je ve vysledku tabulkou s mnoha udaji. Tohle je to, co je jadrem problemu. Je to rychla zmena vazeb, prohledavani na nekolika stupnich s prislusnou strukturou, ktera zahrne vsechny postupne nalezane vztahy. Uplne bezne se tak setkavam s resenim na urovni analyz vztahu M:N. Koketuji uz dost dlouho s ruznymi databazovymi systemy. Uznavam, ze asi nejlepsi je CACHE (byl jsem jednou na Cache Entree a dostal jsem zdarma obed), ale ani tento system si neporadi. A tak uz hezky dlouho hledam mechanizmus, ktery by tohle umel. Vysvetlim proc hledam takova reseni. Nedavno se na mne obratil jeden clovek, jestli bych dovedl vybudovat strukturu mnoziny 366^6. Jednim ze zakladnich predpokladu je porovnani 6^6. V prime souvislosti tedy astronomicke vetveni, ke kteremu je potřeba realnou databazi + tezebni mechanizmus. A ted se ptam ja. Nedoslo k nejake zmene od aktualni diskuse na toto tema? (Ja problem staticke supertabulky vyresil, a lze ji realne budovat - postupne generovat a rozsirovat, jen nemam predstavu jestli nahodou nedelam neco, co nekde funguje a kdyz tak jak? - odezvy ap. ochrany neresim, jen struktury, logiku skladu a tezby z pohledu limitniho zadani.) Dekuji za odpoved.

Clanok hovori o ukladani stromov do databazy. Vy hovorite o vseobecnych grafoch (mozno az orientovanych)... co je ina a vo vseobecnosti trosku komplikovanejsia situacia.

po prostudovani zakladniho dila k teto problematice (JOE CELKO: SQL FOR SMARTIES: TREES AND HIERARCHIES) jsem nabyl dojmu, ze prave takove problemy jsou konecna stanice SQL a ze je prece jen spravne tyto problemy resit na aplikacni urovni (autor upozornil).

Je sice teoreticky mozne resit hierarchicke problemy za pomoci ruznych triku ale je to asi, jako kdyz za totality lide pasovali satelity ze zapadu v zubnich pastach...

Ano a ne. Pokud si namodelujete entity tak, jak byste je modeloval v např. C, pak to pro SQL je dřina.

Je potřeba si uvědomit, že problém s výkonností nastává v okamžiku použití procedurálního rozšíření jazyka SQL, tj. např. PL/SQL u Oracle. Samotné SQL je VELMI rychlé (neboť jednotlivé enginy mají za sebou poměrně slušnou optimalizaci :-))

Takže si stačí namodelovat entity tak, abybylo možno na jedne select vytáhnout celou větev a máte po problému. Ovšem triviální to není a rozhodně to je náročné na datový objem, tj. paměť (i když si můžeme nadefinovat indexy).

Je zaujímavé, že prvé databázové systémy boli hierarchické. Relačné databázy prišli až výrazne neskôr po nich – keď bol HW výkonnejší. Čo naznačuje, že hierarchické DB sú svojou už podstatu výkonnejšie. Samozrejme, všetko má svoje pre a proti. V relačných databázach máme SQL a stačí keď popíšem čo chcem nestarám sa ako to dostanem. V hierarchických musím poznať štruktúru dát v strome a každé prechádzania stromom je závislé na dátach a nedá sa odbaviť jedným SQL príkazom. U relačných je to však vyvážené rýchlosťou a nízkym nárokom na diskový priestor.
Môžem hodnotiť aj z vlastnej skúsenosti. Donedávna sme vo firme, kde pracujem, Používali MSM (implementácia MUMPS od fy Micronetics). V poslednej verzii sa pre WinNT (samozrejme existovala aj verzia pre Unix, ale aj free implementácie M – technológie. Číslo jeden je Cache od Intersystems) sa dodávala na dvoch 3 a ½ palcových disketách!!! Z rozhodnutia vedenia sme prešli na iný systém, ktorý je založený na MSSQL. Žiaľ databáza, ktorá mala v MSM veľkosť 600MB má teraz niekoľko desiatok GB a všetko trvá 10x dlhšie. Nuž čo, pokrok sa nedá zastaviť :-(

> Čo naznačuje, že hierarchické DB sú svojou už podstatu výkonnejšie.

Ne nutne. Bubble sort je taky starsi nez Quick sort a neni vykonnejsi ;-)

Jinak je to IMHO spis o tom, ze cim obeznejsi databaze, tim je pomalejsi. Nebot databaze, ktera muze/umi vyuzivat specifik dat, muze samozrejme byt o dost rychlejsi.

Ehm... "obeznejsi databaze" zni zajimave, ale ma to byt "obecnejsi databaze".

A tady se prave ukazuje sila databaze Cache, ktera krome primeho pristupu nabizi take SQL pristup (pripadne objektovy pristup) k hierarchicky ukladanym datum.

Suhlasim! Cache je super! Ides do Roznova?

pokrok?
Jedno ruské přísloví říká: "Půjč blbovi sekeru a nejspíš si usekne ruku"!

mam stromovou strukturu, ktera je relativne konstantni (prevazuje select nad update), tak bych si molh vytvorit pomocnou tabulku (id-rodice, id-potomka, uroven), nad kterou muzu vytvorit index. Potom by slo vytvaret dotazy na seznam potomku uzlu, rodicu uzlu, omezit uroven prohledavani a podobne, vse pomerne rychle.
Zmeny struktury by slo realizovat jako triggery a pri trose stesti by aktualizace struktury nebyla neumerne vypocetne slozita ...

Narazim s timto pristupen na nejaky zadrhel ?

Zádrhel bude už při zadání dotazu (např) "Vyber všechny následníky uzlu X". Pokud víte, že strom bude mít omezenou a malou výšku (např. max. tři úrovně), pak se to dá řešit pomocí uložení odkazů na všechny předků do jedné relace.

Předpokládám, že číslo úrovně zamýšlíte pro zlepšení výkonnosti omezením prohledávaného prostoru. Nicméně třeba úplný binární strom má v poslední úrovni polovinu všech uzlů, takže ani takto si moc nepomůžete...

Musel byste mit opravdu zvlastni typ dat, aby se to vyplatilo. Stromy jsou jeden z tech pripadu, kdy pouziti ulozenych procedur vede k dost divokemu zvyseni vykonu (oproti aplikacni urovni). Zazil jsem relativne velkou evidencni aplikaci MsSQL + VB, plneni stromu na aplikacni urovni bylo celkem dost brzo nevyhovujici. Prepsani do ulozene procedury zrychlilo operaci sestaveni stromu cca 10. Vami zminovana varianta materializovanych indexu by byla az na poslednim miste. Dovedu si predstavit pripady na ktere relacni databaze neni to prave orechove, a pokud je to vas pripad, pak proste pouzijte jinou databazi.

na doplnenie tiez zaujimavy clanok o stromoch - http://dbazine.com/tropashko4.shtml

to vse vypada tak hezky, ale v praxi je to nepouzitelne.

Praktickym prikladem je jiz zmineny kusovnik a ja nevim, kolik zde pritomnych teoretiku grafu jiz bylo v nejakem podniku s podobnou problemtikou konfrontovano - ale jestli je parez stromem, to se to keca...

V praxi nejde o tupe prochazeni nejakeho stromu nebo zobrazeni v nejakem VB-tree-controlu - na to by znazornene mechanismy (odvisle od nejake konkretni databaze) jakz tak stacily s potem v tvari.

Pri rizeni a planovani vyroby se samozrejme zada vice - pri prochazeni stromu se musi rozhodovat jestli se nejaka podskupina rozlozi nebo ne, podle jakeho mechanismu se ma rozlozit, bude dany mechanismus platit od toho okamziku az do konce rozpadu na dane urovni apod..

Zde se pote setkavame s nasledujicimi problemy:

- nekdo musi uvedenou situaci namodelovat. To je tak komplikovane, ze to dokazi jen velice zkuseni jednotlivci - v kolika projektech se tito lide nachazeji?

- podari-li se to uz namodelovat, musi jini s modelem pracovat. Protoze tito ostatni nemaji takovy abstraktni aparat, dochazi neustale k dotazum na modelovaciho-guru, ktery vysvetluje neustale to same, protoze zbytek kolegu to neni s to pochopit (sam v projektu zazil)

- na zmeny ve strategii pro praci s hierarchii je mozno uz rovnou zapomenout, protoze vesmes chybi ten guru, ktery by sdelil, co si pri navrhu myslel.

Ten kdo docetl az sem by se mohl ptat, co tedy pouzit, kdyz to popsane je nesmysl. Odpovedi jsou v diskuzi - pouzit hierarchickou databazi a je li predepsanna SQL, tak na aplikacni urovni bez toho aby se vymyslelo neco v relacnim modelu, ktery prave v techto ulohach ukazuje, ze neni schopen smysluplne zobrazit prakticky svet...

Praxe je jeden neresitelny pripad, deset obtizne resitelnych a 89 snadno resitelnych ze sta :-). Zminovane techniky jsou pro tech 89%. Ve vasem pripade bych skoro i pochyboval, zda by se daly pouzit ulozene procedury. I kdyz neco by slo, muselo by se to vyzkouset. Ale pochybuji, ze by to zvladal PostgreSQL a Potemkinovym patchem.

Inteligentni jedinci se nachazeji skoro vsude. Jde je jen o to je motivovat, by se chovali inteligentne. Nebo nastavit procesy, byrokracii tak, abych mi stacilo par geniu a banda poskoku, napr. projekt Apollo. Na to abyste dobre navrhl model musite byt budto Pan Buh, ktery vi co bude, nebo mit proste stesti. A stejne musite opakovane zjistovat jestli jste se svym navrhem trefil do vkusu, potreb. Po pravde receno, nikdy jsem nemel problem s inteligenci mych kolegu - budto mam stesti a nebo to nebude se mnou nijak slavny :-). Horsi je to se mnou. Cim mate mene duvtipne spolupracovniky, tim jim to musite lip vysvetlit. Je to sice trochu ztrata casu, urcite jista namaha, na druhou stranu problematiku nejlepe pochopite tak, ze ji bude nekomu vysvetlovat. Taky muzete pripravit dalsi rozhrani, trochu odstinujici uzivatele od komplexnosti systemu. A nekdy to holt udelat jednoduse nejde.

Relacni SQL databaze se pouzivaji celkem bez problemu, a nerozsirily by se pokud by nebyly prinosove v plusu. Zakladem je ale vedet, co chci udelat a jak to udelat. Je urcite velky rozdil v navrhu. Pokud jste delsi dobu pracoval s nerelacnimi databazemi, tak proste myslite jinak (bez urazky). Ja bych mel zase problem pracovat s hiearch. databazemi. Nez jsem se naucil pouzivat SQL tak mi to nekolik let trvalo. Ale treba k Foxce se kterou jsem zacinal uz bych se nevratil. Prolog uz asi nikdy nepochopim, a kdyz se divam na kod v lispu nebo v Smalltalku tak si rikam, ze to je vec, ale jsou to bohove :-), kdyz to zvladaji.

Samozrejme, to co jsem tady predvadel je to nejjednodussi, co se da predvest. Rozhodne to nevypovida o moznostech RDBMS. Zrovna v teto oblasti se jednotlive RDBMS dost lisi. S rekurzivnima dotazama (Common Table Expression) se toho necha delat hodne, a dost mozna by to zvladlo i Vase pozadavky. Ale mate pravdu, ze to je tezsi vymyslet. Ono uz pouzivat vazane SQL poddotazy neni nic jednoducheho.

Tvuj prispevek mi pripada dost zmateny.
My jsme zpracovavali 200000 kusovniku sekvencne
uz v osmdesatych letech. Nemeli jsme to naklicovane,
ale museli jsme strom pekne projit.
Navic, SQL databaze je zabehnuta na evidence vseho druhu a
jen nekde je potreba ulozit stromovou strukturu - zdroje, dealeri, organizacni strukturu apod.

Proc se vyskytla potreba psat o ulozeni stromu?
Viz clanek na intervalu.cz

zdravim,

ja pouzivam contrib kniznicu LTREE v kombinacii so samoreferencnou tabulkou.
LTREE mi zabezpeci naozaj rychlu selekciu dat (odporucam pozriet vysledky testov na http://www.sai.msu.su/~megera/postgres/gist/ltree/)

samoreferencna tabulka mi zase zabezpeci perzistenciu dat...
trigerom si automaticky naplnim atribut typu ltree, nad ktorym potom robim selekciu dat...

je pravda, ze to zrovna nie je najjednoduchsie riesenie, ale ukryva v sebe rychlost a silu prave v pripade, ked sa nad databazou robi viac selektov ako insertov a updatov (weby)

Sice rok a půl starý, ale přesto stále zajímavý článek k tématu jak ukládat hierarchické stromy do relační databáze
http://www.sitepoint.com/article/hierarchical-data-database
Koho by napadlo, že použití ItemID & ParentID není jediná možnost.

Na začiatok sa chcem poďakovať za článok. Zhodou okolností práve píšem bakalársku prácu na rovnakú tému, preto by som sa chcel spýtať, či by mi niekto nevedel poradiť vhodnú literatúru. Vyšlo niečo k stromovým dátam aj v češtine alebo slovenčine?, za odpoveď vopred ďakujem.....