abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
dnes 01:33 | IT novinky

Red Hat zveřejnil finanční výsledky za čtvrté čtvrtletí a také celý fiskální rok 2019. Ten pro Red Hat skončil již 28. února. Tržby za celý fiskální rok činily 3,4 miliardy dolarů, tj. meziroční nárůst 15 %.

Ladislav Hagara | Komentářů: 0
dnes 00:11 | Komunita

Prezident Nadace pro svobodný software (FSF) Richard M. Stallman vyhlásil na slavnostním ceremoniálu v rámci konference LibrePlanet 2019 vítěze Free Software Awards za rok 2018. Ocenění za společenský přínos získal projekt OpenStreetMap. Za rozvoj svobodného softwaru byla oceněna Deborah Nicholson. Souhrn dění na letošní konferenci LibrePlanet v příspěvcích na blogu FSF: 1. den a 2.den.

Ladislav Hagara | Komentářů: 0
včera 23:33 | Zajímavý projekt

Na Humble Bundle byla spuštěna akce Humble Book Bundle: Coder's Bookshelf by No Starch Press. Za 1 dolar a více lze koupit 4 elektronické knihy, za 8 dolarů a více lze koupit 9 elektronických knih, za 15 dolarů a více lze koupit 13 elektronických knih za 20 dolarů a více lze koupit 14 elektronických knih věnovaných programování od nakladatelství No Starch Press. Nákupem lze podpořit organizaci Freedom to Read Foundation (FTRF).

Ladislav Hagara | Komentářů: 0
včera 05:00 | Nová verze

Byla vydána verze 0.5.0 operačního systému Redox OS (Wikipedie). Jedná se o mikrokernelový unixový operační systém naprogramovaný v programovacím jazyce Rust. Zdrojové kódy jsou k dispozici na GitLabu pod licencí MIT.

Ladislav Hagara | Komentářů: 0
24.3. 22:55 | Zajímavý článek

V bitmapových obrázcích bývají často ukrytá užitečná data, která jsou ovšem běžně nepřístupná. V článku Full-textové prohledávání komiksů a jiných obrázků (dostupné přes Tor) autor prakticky ukazuje, jak si postahovat komiksy a rozpoznat v nich text pomocí OCR nástroje Tesseract. Následně Ghostscriptem vkládá všechny komiksy do jednoho velkého PDF, ve kterém jde vyhledávat text (který byl původně jen shlukem grafických bodů v bitmapách). Uvedený postup lze použít i k užitečnějším věcem, jako např. indexování nestrukturovaných dat na disku.

Monika Kokešová | Komentářů: 20
24.3. 22:44 | Pozvánky

17. až 19. května se uskuteční další ročník putovní konference české a slovenské Drupal komunity - tentokrát v Hustopečích na Moravě. Bude se věnovat nejnovějším trendům v Drupalu, ale i v postupech a nástrojích pro vývoj a správu webových aplikací. Můžete se těšit na odborné přednášky, workshopy, neformální debaty i přehlídku nejzajímavějších projektů. Podrobnosti a vstupenky najdete na drupalcs.camp.

Eva Rázgová | Komentářů: 1
24.3. 22:22 | Nová verze

Byla vydána verze 4.0 textového editoru GNU nano (Wikipedie). Podrobný přehled novinek a oprav v oznámení v diskusním listu info-nano nebo v souboru ChangeLog na Savannah.

Ladislav Hagara | Komentářů: 0
23.3. 17:11 | Komunita

Na konferenci herních vývojářů GDC 2019 (Game Developers Conference) měla svůj stánek i společnost Red Hat. Návštěvníci si mohli zahrát počítačové hry na Fedoře 29 s Cinnamonem a Lutrisem.

Ladislav Hagara | Komentářů: 0
23.3. 15:33 | Komunita

O víkendu probíhá v Cambridgi (MA) konference LibrePlanet 2019 organizovaná Nadací pro svobodný software (FSF). Na programu je řada zajímavých přednášek. Sledovat je lze také online.

Ladislav Hagara | Komentářů: 3
22.3. 21:33 | Humor

Richard M. Stallman v článku Install Fests: What to Do about the Deal with the Devil navrhuje, jak se vypořádat s morálním dilematem, zda na „installfestech“ (akcích, kde zkušení uživatelé pomáhají nováčkům nainstalovat GNU/Linux na přinesený hardware) instalovat také nesvobodný software, typicky ovladače. Vzdělávací přístup je „škola hrou“, kdy instalace právě nesvobodného softwaru provádí postava „Ďábla“.

Fluttershy, yay! | Komentářů: 11
Kolik balíčků (v tisících) máte nainstalovaných na svém systému?
 (4%)
 (14%)
 (33%)
 (30%)
 (20%)
 (3%)
 (2%)
 (1%)
 (2%)
Celkem 242 hlasů
 Komentářů: 23, poslední 24.3. 17:36
Rozcestník

Stromy v SQL

11. 1. 2006 | Pavel Szalbot | Různé | 14260×

Stromy lze s pomocí jazyka SQL sázet, kácet i česat vícero způsoby. Ukážeme si jeden klasický a dva pokročilejší.

Stromy

Definice

Pojmem strom se zpravidla označuje neorientovaný graf, jehož každé dva vrcholy jsou spojeny právě jednou cestou (pokud nerozumíte, zkuste se podívat třeba do wiki - graf, strom).

Strom může reprezentovat vybranou hierarchickou (stromovou) strukturu a ta je předmětem toho článku. Kde že jste mohli strom mimo park zahlédnout? Zajisté jste se s nimi setkali minimálně v diskusních fórech ABCLinuxu.cz, nebo při nakupování v internetovém obchodě, na jehož kategoriích výrobků si budeme práci se stromovou strukturou prezentovat. Důvodem je několik "zajímavých" akcí, jež se v internetovém obchodě provádějí. Uložištěm našeho stromu bude RDBMS komunikující jazykem SQL (konkrétně MySQL a v jednom případě i PostgreSQL).

Jaký strom zasadit?

V perexu jsem naznačil, že si ukážeme celkem tři příklady reprezentace stromu v SQL. Než si z nich vůbec začneme vybírat, měli bychom si ujasnit to, co od stromu budeme očekávat. Aplikace typu internetový obchod může provádět následující akce:

  • základní práce se stromem - CRUD operace s uzly (kategoriemi) (Create, Retrieve, Update, Delete)
  • rozbalení stromu ve vybraném uzlu
  • nalezení všech "podkategorií" dané kategorie (pro různé filtry, ale také zobrazení všech výrobků z kategorie a jejich podkategorií)
  • zobrazení cesty k vybranému uzlu od kořene

Operací s hierarchickou strukturou bude pravděpodobně více a mnohé mohou být efektivněji provedeny na aplikační úrovni (např. načtením celé struktury a jejím zpracováním namísto několika SQL dotazů). Ponechme je ale stranou a zkusme se podívat, co nám nabízí samotné SQL. Vzhůru do lesů!

Sebereferenční tabulky

Prvním způsobem uložení hierarchické struktury v SQL tabulce budou tzv. sebereferenční tabulky, definující strom seznamem následníků. Sebereferenční tabulky využívají vazby rodič-syn/dcera v hierarchické struktuře přítomné. Pro jednoduchost budeme předpokládat, že každý uzel má nanejvýš jednoho rodiče.

Uvažujme následující hierarchii kategorií:

strom

SQL tabulka by mohla být vytvořena příkazem:

 CREATE TABLE categories(
  id INT NOT NULL PRIMARY KEY, 
  name VARCHAR(32), 
  parent INT NOT NULL);

a její obsah by vypadal takto:

+----+---------------------+--------+
| id | name                | parent |
+----+---------------------+--------+
|  1 | Operační systémy    |      0 |
|  2 | Unix                |      1 |
|  3 | Linux               |      1 |
|  4 | Windows             |      1 |
|  5 | Red Hat	    	   |	  3 |
|  6 | Mandriva            |      3 |
+----+---------------------+--------+

Jak vidíte, každý uzel má unikátní identifikátor (číslo ID) a také jsme mu přiřadili rodiče. Všimněte si, že kategorie "Operační systémy" má ve sloupci parent nulu, i když žádná taková kategorie v tabulce není. Její syny budeme označovat jako kořenové kategorie a pro ni samotnou nebudeme požadovat rodiče.

Podívejme se teď na operace, které nás při práci se stromovou strukturou budou otravovat.

CRUD operace jsou vcelku triviální. Vkládání zajistí prostý INSERT. Při odebírání bychom měli dbát na to, abychom dle potřeby rekurzivně smazali i uzly-syny, což je v košatém stromě docela náročné. Přesun uzlu (a celého jeho podstromu!) v rámci stromu, tj. změnu jeho rodiče, realizujeme jednoduchým UPDATE.

Zobrazení podstromu provedeme podobně jako smazání - rekurzivně vybereme všechny potomky právě zpracovávaného uzlu. Podotkněme, že výhoda načtení celého stromu a jeho zpracováním aplikací sice ušetří práci databázi, ale nelze ji dost dobře použít při získávání všech výrobků patřících do kategorií podstromu, kterých může být velmi mnoho.

Rozbalení stromu dle vybrané kategorie je variací na téma zobrazení podstromu s tím, že do hloubky jdeme jen po cestě od kořene k rozbalovanému uzlu. Nalezení této cesty je při této reprezentaci znovu náročné.

Předností sebereferenčních tabulky je jejich jednoduchost - při práci s ní si bohatě vystačíte se znalostí rekurze. Cenou ovšem bude neúměrné zatížení databázového serveru zvláště v případě, že se stromem budete pracovat často, což se u internetového obchodu děje obvykle s každou zobrazenou stránkou, či když strom bude hezky košatý (uzly mají mnoho potomků) a vysoký (mnoho generací potomků). Odlehčit si můžete jistou úrovní cachování stránek, nicméně časem se nejspíš poohlédnete po výkonnějším řešení.

Genealogické stromy

A narazíte možná na genealogické stromy. Genealogický strom také využívá vazbu rodič-syn mezi uzly, ale navíc pro každý uzel definuje i tzv. genealogický identifikátor. Tento identifikátor je unikátní pro každý uzel a dají se z něj vyčíst informace o jeho předcích (rodičích, prarodičích, prapra...) i potomcích. Identifikátor potomka totiž získáme tak, že za identifikátor předka připojíme identifikátor potomka.

Zvolíme-li za identifikátor písmeno abecedy, pak bude naše rozšířená tabulka obsahovat tyto záznamy:

+----+---------------------+--------+------+
| id | name                | parent | path |
+----+---------------------+--------+------+
|  1 | Operační systémy    |      0 |    A |
|  2 | Unix                |      1 |   AA |
|  3 | Linux               |      1 |   AB |
|  4 | Windows             |      1 |   AC |
|  5 | Red Hat      	   |	  3 |  ABA |
|  6 | Mandriva            |      3 |  ABB |
+----+---------------------+--------+------+

CRUD operace tentokrát váže několik nepříjemných podmínek. Jednou z nich je omezení počtu potomků dle volby uložení identifikátoru (v případě písmen abecedy smít uzel mít "jen" 26 přímých potomků). Vložení nového uzlu do stromu provedeme tak, že zjistíme genealogický identifikátor rodiče a za identifikátor uzlu zvolíme nejmenší možné písmeno abecedy, které je na dané úrovni volné (úrovní rozumíme množinu přímých potomků rodiče). Zaveďme proto požadavek, aby na sebe identifikátory sourozenců lexikálně navazovaly.

Odstraňení uzlu je velmi snadné. Stačí smazat všechny uzly, jejichž genealogický identifikátor začíná identifikátorem odstraňovaného uzlu. Pokud bychom v naší hierarchii chtěli z nabídky odstranit podstrom s kořenovou kategorií "Linux", provedli bychom SQL příkaz:

DELETE FROM categories WHERE genealogical LIKE 'AB%';

Tím nám ovšem může vzniknout mezera na úrovni mazaného uzlu (Linux), což si nepřejeme a musíme proto po smazaní uzlu aktualizovat identifikátory postižených uzlů.

Přesun uzlu provedeme příslušnou změnou umístění (změna rodiče) a následnou aktualizací identifikátorů.

Poznamenejme, že návaznost identifikátorů se nakonec zdá být spíše na škodu, jelikož nám práci docela komplikuje, nicméně se bez procedury na odstranění hluchých míst ve stromu nejspíš neobejdeme.

Zobrazení kompletního podstromu je poněkud svízelné. Sice nám postačí SELECT s klauzulí ORDER BY genealogical, aplikace ovšem často požaduje, aby byl výstup abecedně setříděn. Tuto komplikaci lze vyřešit už během CRUD operací, totiž vkládáním nových uzlů na správné místo. Cenou je bohužel režie spojená s tříděním a následnou aktualizací identifikátorů.

Chcete-li si ušetřit nepříjemnosti s nedostatkem písmen a přepočítáváním po mazání, můžete použít jiný identifikátor. V praxi se často používá např. speciální oddělovač následovaný číselnou sekvencí. Identifikátor uzlu Red Hat by byl "/1/3/5&qout;.

Konečně nalezení cesty k uzlu zařídí:

SELECT * FROM categories WHERE 'ABB' LIKE genealogical||'%'
nebo
SELECT * FROM categories WHERE 'ABB' LIKE concat(genealogical, '%')

Nested set aneb DFS strom

Posledním a dle mého názoru nejvýkonnějším řešením je tzv. nested set reprezentace stromu. (Pozn.: Tento název používá Joe Celko a z různých článku se zdá, že není sám. Ačkoli podstatu uložení informace o uzlech charakterizuje čitelně i pro základních grafových algoritmů neznalé, lepší název by mohl být DFS strom.) Podívejme se nejprve na tabulku:

+----+---------------------+--------+------+-------+
| id | name                | parent | left | right |
+----+---------------------+--------+------+-------+
|  1 | Operační systémy    |      0 |    1 |    12 |
|  2 | Unix                |      1 |    2 |     3 |
|  3 | Linux               |      1 |    4 |     9 |
|  4 | Windows             |      1 |   10 |    11 |
|  5 | Red Hat	    	   |	  3 |    5 |     6 |
|  6 | Mandriva            |      3 |    7 |     8 |
+----+---------------------+--------+------+-------+

Vychází ze sebereferenční tabulky, kterou rozšiřuje atributy left a right. Jejich hodnoty jsou získány průchodem stromu DFS (depth first search) algoritmem. Pseudokód algoritmu:

 DFS(graf)
  foreach uzly_grafu as uzel do
    uzel->barva = bila
  done
  cas = 0
  foreach uzly_grafu as uzel do
    if uzel->barva = bila
      DFS-PROJDI(uzel)
  done
  end

DFS-PROJDI(uzel)
  uzel->barva = seda
  cas = cas + 1
  uzel->nalezen = cas
  foreach sousede[uzel] as soused do
    if soused->barva = bila
      DFS-PROJDI(soused)
  done
  uzel->barva = cerna
  uzel->opusten = cas

Algoritmus začíná voláním funkce DFS, které je předán zkoumaný graf. Ta nastaví barvu všech uzlů na bílou (uzel dosud nebyl navštíven), seřídí čas a následně prochází uzly grafu s tím, že pokud je uzel bílý, zavolá funkci DFS-PROJDI. DFS-PROJDI přebarví uzel na šedou (byl navštíven, ale dosud se zpracovává), zvedne čas o jedničku a použije jej jako čas navštívení uzlu a poté rekurzivně prochází dosud nenavštívené sousedy uzlu předaného jako parametr. Jakmile jsou všichni sousedé zpracování, přebarví uzel na černou (zpracování dokončeno), nastaví čas opuštění uzlu a vrací se.

Čas navštívení a opuštění uzlu se použijí jako hodnoty atributů left resp. right v SQL tabulce. Lepší představu o výsledku můžete získat z obrázku.

DFS strom

Všimněte si, že interval <left;right> libovolného uzlu je podintervalem intervalu vlastního rodiče (odtud nested set = vnořené množiny). Tato vlastnost plyne z toho, jak DFS prochází strom a ukladá časy a právě ona nám ulehčí práci s hierarchickou strukturou v SQL.

Podívejme se na operace, které chceme nad strukturou provádět. Všechny podkategorie zvolené kategorie získame jednoduchým SELECTem:

SELECT * FROM categories WHERE left >=x AND right <=y

Oproti rekurzi sebereferenčních tabulek podmíněnou mnoha dotazy či spíše přenosem většího množství dat jsme ve výhodě, ovšem genealogický identifikátor umožňuje totéž, ač s nutností použití pomalejšího operátoru LIKE. Získat výstup setříděný podle názvu uzlů je tentokrát o něco jednodušší. Po každé CRUD operaci totiž musíme aplikovat DFS algoritmus na celý strom znovu. Aby DFS generoval časy s ohledem na abecední pořadí uzlů, stačí naštěstí jen vhodně připravit pořadí uzlů, ve kterém jsou algoritmem zpracovávány (nezapomeňte abecedně setřídit i pole sousede[uzel]).

Cestu k uzlu nalezneme také velmi jednoduše. Stačí si uvědomit, že každý předek uzlu byl navštíven dříve a opuštěn později než uvažovaný uzel.

SELECT * FROM categories WHERE left <= x AND right >=y

DFS strom se zdá být velmi vhodný pro statické, či málo upravované struktury. Uplatnění si však zajisté najde i v případě potřeby vyhledávání ve velmi rozsáhlých hierarchických strukturách.

Závěr

Předvedli jsme si tři možné reprezentace hierarchické struktury v SQL databázích. Jejich přednosti a nevýhody je třeba zvážit vždy s ohledem na konkrétní využití, přičemž společnou výhodou se jeví zvláště přenositelnost mezi různými databázovými servery. Dle předložených indicií a zdrojů na internetu si zajisté zvolité správnou reprezentaci pro požadované použití.

       

Hodnocení: 97 %

        špatnédobré        

Nástroje: Tisk bez diskuse

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

Komentáře

Vložit další komentář

11.1.2006 00:50 diverman | skóre: 32 | blog: život s tučňáčkem
Rozbalit Rozbalit vše Re: Stromy v SQL
Dobrej článek. Přidávám nějaké odkazy do slovníku:
SŘBD
RDBMS
PostgreSQL
MySQL
deb http://ftp.cz.debian.org/debian jessie main contrib non-free
11.1.2006 00:59 plathel | blog: plathel | Praha, Prostejov
Rozbalit Rozbalit vše Re: Stromy v SQL
<ohraný vtip> Proč pařez není strom?

Protože obsahuje kružnice. </ohraný vtip>
11.1.2006 07:46 Martin Beránek | skóre: 33 | blog: mousehouse | Brno
Rozbalit Rozbalit vše Re: Stromy v SQL
ale divil by ses kolik lidi to nezna :-)
never use rm after eight
Věroš avatar 11.1.2006 09:25 Věroš | skóre: 24 | blog: Co není v hlavě | 49.29 s.š., 16.54. v.d.
Rozbalit Rozbalit vše Re: Stromy v SQL
Moji kolegové ten vtip nejen neznají, ale ani se mu nesmějí :-( A to jsem si na něj ráno taky vzpomněl.
Školím Ansible
15.1.2006 21:14 twain
Rozbalit Rozbalit vše Re: Stromy v SQL
A vite, ze strom neni nic jineho nez souvisly les? Miluju teorii grafu :).
11.1.2006 01:14 Jiří Hlinka | skóre: 29 | blog: zapisky | Teplice
Rozbalit Rozbalit vše Re: Stromy v SQL
Díky za tenhle článek!
Jirka
11.1.2006 08:49 100rk | Ceskoslovensko
Rozbalit Rozbalit vše Re: Stromy v SQL
Pred casem vysel podobny clanek na interval.cz: http://interval.cz/clanek.asp?article=3801
11.1.2006 08:54 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
Rozbalit Rozbalit vše Re: Stromy v SQL
Interval bohužel nečtu, to bych ten článek možná nedopsal. Ale zaujalo mě pojmenování "Modified Preorder Tree Traversal Algoritmus" :-).
Math, as Barbie says, is hard.
11.1.2006 09:00 Leoš Literák | skóre: 74 | blog: LL | Praha
Rozbalit Rozbalit vše Re: Stromy v SQL
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.
Zakladatel tohoto portálu. Twitter, LinkedIn, blog, StackOverflow
11.1.2006 09:07 100rk | Ceskoslovensko
Rozbalit Rozbalit vše Re: Stromy v SQL
Moje reakce byla myslena jen jako dalsi informacni zdroj na toto tema. Nepodsouvejte mi prosim jine umysly.
11.1.2006 10:38 Leoš Literák | skóre: 74 | blog: LL | Praha
Rozbalit Rozbalit vše Re: Stromy v SQL
Nic jsem vam nepodsouval. Jen jsem sdelil nase kriteria.
Zakladatel tohoto portálu. Twitter, LinkedIn, blog, StackOverflow
11.1.2006 09:04 Tom Hlava | skóre: 4
Rozbalit Rozbalit vše Re: Stromy v SQL
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?
11.1.2006 09:19 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
Rozbalit Rozbalit vše Re: Stromy v SQL
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...
Math, as Barbie says, is hard.
11.1.2006 09:08 Vladimir Kralik
Rozbalit Rozbalit vše Re: Stromy v SQL
Velmi dobry clanok. Dakujem.
hajma avatar 11.1.2006 10:07 hajma | skóre: 27 | blog: hajma | Říčany
Rozbalit Rozbalit vše Re: Stromy v SQL
oba odkazy na wiky jsou shodné, opravte si to
21 promarněných znaků
11.1.2006 10:10 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
Rozbalit Rozbalit vše Re: Stromy v SQL
Math, as Barbie says, is hard.
11.1.2006 11:43 morpho | skóre: 4 | blog: morpho
Rozbalit Rozbalit vše Re: Stromy v SQL
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
To že daný produkt neumíme používat ještě neznamená že musi být bezpodmínečně špatný
11.1.2006 12:01 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
Rozbalit Rozbalit vše Re: Stromy v SQL
PostgreSQL má modul ltree v contribu viz třeba výborný článek na Rootu.
Math, as Barbie says, is hard.
11.1.2006 23:26 Pavel Janousek
Rozbalit Rozbalit vše Re: Stromy v SQL
No pokud vyuka abstraktnich datovych typu/struktur je v podani jisteho, dnes jiz Profesora, tak se ani k tem sebereferencnim tabulkam nedostanete...
15.1.2006 09:29 JP
Rozbalit Rozbalit vše Re: Stromy v SQL
Pan studoval v Brně, není-liž pravda? ;-)
16.1.2006 14:58 zde | skóre: 9 | blog: Linuch | Brno
Rozbalit Rozbalit vše Re: Stromy v SQL
Kterou školu? Tady je těch technik, kde se informatika učí, povícero...
Táto, ty de byl? V práci, já debil.
20.2.2006 10:37 Murdej
Rozbalit Rozbalit vše Re: Stromy v SQL
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 :)
11.1.2006 14:18 Trained.Monkey | skóre: 12 | blog: monkey
Rozbalit Rozbalit vše Re: Stromy v SQL
Diky za skvely clanek, jsem jeden z "PHP programatoru",ale snazim se polepsit, hlavne posledni algoritmus mi prijde docela vychytany.
12.1.2006 11:39 Honza
Rozbalit Rozbalit vše neorientovaný graf
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.
12.1.2006 12:24 Pavel 'lingeek' Szalbot | skóre: 54 | Třinec
Rozbalit Rozbalit vše Re: neorientovaný graf
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.
Math, as Barbie says, is hard.
16.1.2006 14:56 zde | skóre: 9 | blog: Linuch | Brno
Rozbalit Rozbalit vše DFS strom
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?
Táto, ty de byl? V práci, já debil.
16.1.2006 15:09 zde | skóre: 9 | blog: Linuch | Brno
Rozbalit Rozbalit vše Re: Stromy v SQL
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)
Táto, ty de byl? V práci, já debil.
27.1.2006 18:45 Fin
Rozbalit Rozbalit vše Re: Stromy v SQL
IMHO lepsi reseni lepsi nez DFS strom: Trees in SQL databases
2.1.2009 18:26 Andrej
Rozbalit Rozbalit vše Re: Stromy v SQL

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

Založit nové vláknoNahoru

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.