Názory k článku Stromy
-
Marek Chlup (neregistrovaný)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. -
Miloš Kafka (neregistrovaný)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. -
neutr (neregistrovaný)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.
-
honza (neregistrovaný)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... -
Pepa (neregistrovaný)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). -
Peter Harbut (neregistrovaný)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ť :-( -
Michal Kára (neregistrovaný)> Č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. -
Petr Ledvina (neregistrovaný)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. -
bzuk a strup (neregistrovaný)picoviny ... co je tak vykacet vsechny a misto nich vsude vybudovat dalnice a pokud nebude dost penez aspon betenovy hriste aby decka mely kde cutat do micudy misto fetovani a sukani nafukovacich pan ... jo svet speje do totalni pice a tak to je a stromy nebo ne moc se nezmeni ;DD
-
bzuk a strup (neregistrovaný)musim se pridat k tobe malokdo chape co takova sazenicka obnasi prae ... nejdriv se o ni musis poradne starat doma, pak ju presadis do vetsiho kvetinaca lae porad resis jestli nezmrzne a pak mozna nekdy pozdeji ju teprve muzes dat ven ... jenze ouha nakej pankac ju posere a poblije a je to v prdeli ... tp nevyresi ani kernel 2.7 ;DD
-
anonymníTuhlencto jsem zatim nepotreboval a ani v nasledujicich 10 letech potrebovat nebudu. Nikdy jsem nemel v databazi tolik zaznamu. Leda si je umele vygeneruju a budu machrovat jak jsem dobrej. A kdyz budu chtit stromy tak na to pouziju extra databazi a nebudu to honit pres nejaky pochybny upravy.
Radeji povidani o ReiserFS4 a dancing trees. -
ubu (neregistrovaný)na doplnenie tiez zaujimavy clanok o stromoch - http://dbazine.com/tropashko4.shtml
-
honza (neregistrovaný)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. -
ja (neregistrovaný)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. -
hlavki (neregistrovaný)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) -
poohDA (neregistrovaný)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. -
Andrej (neregistrovaný)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.....
ČLÁNKY DO MAILU