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
Zkouška
16. 1. 2009
Bodování ±1: 25–21 výborně, 20-x velmi dobře, (x-1)-15 dobře.
Počty bodů za jednotlivé otázky si nepamatuju, ale nebyly vyšší než 4. Viz též fórum.
- Odebrání 1 prvku z neredundantního B-stromu s m=5. Strom měl tři úrovně (vč. kořene a listů), dvakrát dojde k podtečení, takže ke změnám dojde na všech úrovních. (Aspoň tak jsem to měl já:).)
- Kdy se lépe hodí pevné disky a kdy flash paměti?
- Hashování na částečnou shodu (zadány pravděpodobnosti atributů a celkový počet bitů).
- Určit počet bitů pro jednotlivé atributy.
- Cena dotazu na jeden konkrétní atribut.
- Průměrná cena dotazu na nějaký atribut.
- Máme k dispozici knihovnu implementující perfektní hashování podle Cormacka.
- Kdy je vhodné ji použít?
- Jaké parametry bude třeba nastavit a podle čeho?
- Vložení jednoho prvku do Faginova hashování: h(k) = k mod 128, tříbitová tabulka zadaná diagramem. Přehledná situace dochází k rozštěpení stránky, ne tabulky. Žádné doplňující otázky.
- Kolikacestným tříděním je třeba třídit 220 běhů, abychom to zvládli na dva průchody? (Odpověď je 15, viz !/Zkouškové Příklady.)
- Co je to indexový soubor a na co se používá? (Žemlička osobně mi pak řekl, že klíčové slovo, co se tam mělo objevit, je úložiště, tak si to přeberte...)
- Co je to kombinovaný index, k čemu se používá a jaké má omezení?
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.
http://tuetschek.wz.cz/schule/ozd.pdf – poznámky pana tuetscheka