Deprecated: Function set_magic_quotes_runtime() is deprecated in /DISK2/WWW/lokiware.info/mff/wakka.php on line 35 Matfiz : OrganizaceAZpracováníDat

Matfiz: OrganizaceAZpracováníDat

Organizace a zpracování dat I

Přednášející: Michal Žemlička

Slajdy: lze se jich doklikat na webu přednášky

Nevíte někdo, prosím, kdy a kde Žemlička zkoušky a zápočty zapisuje do indexů? Na webu to nemá, ani neuvádí nějaké obecné konzultační hodiny.Adam

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.

  1. 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á:).)
  2. Kdy se lépe hodí pevné disky a kdy flash paměti?
  3. 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.
  4. 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?
  5. 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.
  6. 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.)
  7. 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...)
  8. 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:

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

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.