Stromy v SQL (diskuse)

[diverman]

Dobrej článek. Přidávám nějaké odkazy do slovníku:
SŘBD
RDBMS
PostgreSQL
MySQL

[3018736794024648]

<ohraný vtip> Proč pařez není strom?

Protože obsahuje kružnice. </ohraný vtip>

[Martin Beránek]

ale divil by ses kolik lidi to nezna

[Věroš]

Moji kolegové ten vtip nejen neznají, ale ani se mu nesmějí A to jsem si na něj ráno taky vzpomněl.

[twain]

A vite, ze strom neni nic jineho nez souvisly les? Miluju teorii grafu :).

[Jiří Hlinka]

Díky za tenhle článek!
Jirka

[100rk]

Pred casem vysel podobny clanek na interval.cz: http://interval.cz/clanek.asp?article=3801

[Pavel 'lingeek' Szalbot]

Interval bohužel nečtu, to bych ten článek možná nedopsal. Ale zaujalo mě pojmenování "Modified Preorder Tree Traversal Algoritmus" .

[Leoš Literák]

Ze podobny clanek vysel jinde pro nas neni zadne kriterium. To bychom nemohli vydavat skoro nic, protoze vzdycky by se ve svete naslo neco podobneho. Dulezite ale je, aby clanek byl originalni. Coz Pavluv clanek je.

[100rk]

Moje reakce byla myslena jen jako dalsi informacni zdroj na toto tema. Nepodsouvejte mi prosim jine umysly.

[Leoš Literák]

Nic jsem vam nepodsouval. Jen jsem sdelil nase kriteria.

[Tom Hlava]

Děkuji za pěkný článek.
Rád bych se zeptal:
Nebude u varianty "DFS" nutné zajistit, aby při CRUD operaci byl průchod stromem prováděn v jednom okamžiku pouze jedním procesem?
Stačí standardní trasakce, nebo nějaká vyšší úroveň izolace? - nebude nakonec potřeba zamknout na dobu průchodu celou tabulku?

[Pavel 'lingeek' Szalbot]

Záleží na tom, co potřebujete. Pokud vyloženě nesmí dojít k práci s nekonzistentními daty, zřejmě potřebujete buď exclusive (table) lock u InnoDB (MyISAM) tabulek MySQL, nebo serializable level u PostgreSQL. U jiných RDBMS analogicky...

[Vladimir Kralik]

Velmi dobry clanok. Dakujem.

[hajma]

oba odkazy na wiky jsou shodné, opravte si to

[Pavel 'lingeek' Szalbot]

Strom -> http://cs.wikipedia.org/wiki/Strom_%28graf%29

[morpho]

Zdravim, clanek je super. Dle meho nazoru by tohle meli vyucovat jiz na strednich technickych skolach. Obcas se v praci setkavam s novymi spolupracoviky kteri se honosi titulem ing, ale znaji jen Sebereferenční tabulky.

V Oracle jsou pro stromy primo embedded funkce, je neco podobneho i v MySQL nebo Postgree?

Morpho

[Pavel 'lingeek' Szalbot]

PostgreSQL má modul ltree v contribu viz třeba výborný článek na Rootu.

[Pavel Janousek]

No pokud vyuka abstraktnich datovych typu/struktur je v podani jisteho, dnes jiz Profesora, tak se ani k tem sebereferencnim tabulkam nedostanete...

[JP]

Pan studoval v Brně, není-liž pravda?

[zde]

Kterou školu? Tady je těch technik, kde se informatika učí, povícero...

[Murdej]

No to já znám jednoho ing co udělal strom který měl maximálně 3 úrovně a měl pro každou větev zvlášť tabulku :)

[Trained.Monkey]

Diky za skvely clanek, jsem jeden z "PHP programatoru",ale snazim se polepsit, hlavne posledni algoritmus mi prijde docela vychytany.

[Honza]

Chtěl bych upozornit, že definujete strom jako speciální případ neorientovaného grafu, ale v databázi i na obrázku jej chápete jako orientovaný. V neorientovaném stromu nemají pojmy jako potomek nebo předek co dělat. Ale jinak zajímavý článek.

[Pavel 'lingeek' Szalbot]

Správně. Jsem rád, že si toho někdo všimnul. Orientaci jsem nakonec vypustil, abych to už nekomplikoval - nechtěl jsem zabřednout v definicích (i když by to vyspravila jedna věta). Hierarchická struktura už ovšem orientaci potřebuje a tu jsem spolu s označením "stromová" používal.

[zde]

Moc jsem nepochopil proč se pro DFS strom uzlům přiřazují DVĚ čísla. IMHO by úplně stačilo jen očíslovat uzly v depth-first pořadí, ušetří se jednak jeden sloupec, navíc doména toho zbylého bude poloviční (ušetří se jeden bit).

Pro vyhledání podstromu pak pro daný kořen X stačí vyhledat uzly x, pro které X <= x < Y, kde Y je nejmenší větší sybling k X. K jeho zjištění je sice potřeba dalšího dotazu, ale obvykle když potřebuji kompletní podstrom uzlu X, zobrazuji někde poblíž i všechny jeho syblings, takže je to zadarmo.

Jo a taky si myslím že i "hloupý" rekurzivní výpis by mohl být docela rychlý, kdyby se prováděl breadth-first. Lidé nemají rádi hluboké hierarchie, určitě ne při nakupování- hloubka stromu zřejmě nepřesáhne 4-5. Mějme dejmetomu strom hloubky 5, hledáme podstrom uzlu v hloubce 3 (uprostřed): stačí nám 2 dotazy! Nač to komplikovat?

[zde]

Jo a vůbec- proč je strom při tom číslování barven? Vždyť je to úplně zbytečné. Jo a taky jednu z těch dvou inkrementací počitadla jde taky zrušit, tj 'right' jednoho node může být klidně rovno 'left' toho node, který v prohledávání do hloubky následuje.

def Renumber (node, counter):
    node.left = counter; counter++
    for i in node.get_child_list ():
        counter = Renumber (i, counter)
    node.right = counter; counter++
    return counter
Renumber (root, 1)

[Fin]

IMHO lepsi reseni lepsi nez DFS strom: Trees in SQL databases

[Andrej]

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.....