Toto je stará verze stránky OrganizaceAZpracováníDat z 2009-01-15 17:09:30..

Organizace a zpracování dat I

Přednášející: Michal Žemlička
Slajdy: lze se jich doklikat na webu přednášky

Informace a příklady

http://www.ms.mff.cuni.cz/~rouba4am/web/3/zpracuj67z.php?predmety67z=DBI007&p=uk%C3%A1zat – zapisky ze cvik (2006) od Andulky
http://forum.matfyz.info/viewtopic.php?f=386&t=2397 reseny priklady ze cvik na hashovani a trochu na Bstromy...docela doporucuju
http://wiki.matfyz.cz/wiki/DBI007_p%C5%99edn%C3%A1%C5%A1ka dalsi priklady na hashovani

applety na B-stromy (RNDr. Tomáš Holan, Ph.D.):
http://tuetschek.wz.cz/schule/ozd.pdf – poznámky pana tuetscheka
http://hippies.matfyz.info/files/Stromy.pdf – šablona – prázdné stromy pro trasování
http://mff.modry.cz/ozd/ozd_1_pisemky/zkouskove_pisemky.txt – zadání starých písemek

Vybraná témata

Statické (vs. dynamické) metody organizace souborů

Ze slajdů to není zcela jasné, ale statické metody jsou (podle skript):

(a) hromada, sekvenční soubor, indexsekvenční soubor, indexovaný soubor, soubor s přímým přístupem
(b) (podle kontextu) bitové mapy
(c) (podle kontextu) základní hashování (Cormack, Larson-Kajla)

Asi tušíte, že se tu tak trochu míchají jablka s banány:

Třeba indexový soubor vystupuje zprvu spíše jako konkértní druh/metody statického indexování (ve skriptech je zařazen do kapitoly Statické metody organizace souborů), později (slajd 57, 3. přednášky) jako soubor, jehož index může být statický nebo to může být třeba bitová mapa, B-strom, atd.
Bitová mapa je ve skriptech zařazena pod Indexový soubor, do kapitoly Statické metody organizace souborů. Evidentně je IMHO ze své povahy statická, ale většinou se o ní mluví, jako by byla něco “extra”. Například na už jmenovaném slajdu (#57, 3. přednáška) je jmenována odděleně od statických metod. Na slajdu #3 z 5. přednášky jsou bitová mapa a seznam adres jmenovány odděleně od dynamických i statických indexů (ale na stejném řádku jako statické indexy a seznamy adres).
Hashovací metody Cormacka a Larsona-Kajly jsou kompromisně dány do kapitoly Vývoj statických hašovacích metod. Berou se tedy zřejmě jako jakési historické perličky, která jsou statické (jinde než v této kapitolce se o nich snad nemluví) a jsou zajímavé hlavně jako předchůdci dynamických hashovacích metod.

Nepořádek podle mě částečně pramen z toho:

že se směšují základní typy schémat organizace souborů (hromada, sekvenční, indexsekvenční, invertovaný soubor …), konkrétní datové struktury (jednoduché [příp. víceúrovňové] statické indexy, seznamy adres, bitmapy, hashovací tabulky, B-Stromy), případně požadavky ze strany aplikací na dynamičnost (bitové mapy je možné použít i u dynamických dat),
že se zdánlivě vymezuje nějaká dichotomie statických a dynamických metod a velmi záhy se na ni rezignuje.

Toť můj osobní názor a pokus o shrnutí poznatků ze slajdů a skript. — Adam

Seznamy adres

V přednášce je jim věnován jeden slajd, je na něm napsáno pouze «Odstranění duplicit» a následují tři nicneříkající obrázky. Odpovídá tomu kapitolka «Indexované soubory v DIS» ve skriptech. Vězte, že ty tři obdélníky reprezentují logickou strukturu invertovaného souboru: soubor indexů, soubor souřadnic a primární soubor. V souboru indexů by u slov měly být počty «hitů» (zásahů) a ukazatele (na slajdech je jen jedno pole, zřejmě ukazatele, počty hitů lze totiž dopočítat), v souboru souřadnic jsou pak ony “seznamy adres”, resp. ukazatelů do jednotlivých dokumentů. Každé slovo je tedy v souboru indexů právě jednou (s nějakým počtem hitů), to je ono «odstranění duplicit”. Skripta dále říkají, že v základní variantě jde o statický, jednoúrovňový index, ve kterém se hledá půlením intervalů a při přidání/odebrání/aktualizaci dokumentů se musí přestavět.

Zkouška

na foru uz je nejaky info o letosnich zkouskach: http://forum.matfyz.info/viewforum.php?f=160
!/Zkouškové Příklady — pokus o soupis a kategorizaci a nějaké dřívější zdroje ke stažení