DBI007 probraná látka

Přehled látky probrané na přednášce Organizace a zpracování dat I.

Schémata organizace souborů

• hromada – nehomogenní soubor (nemá pevný typ záznamu s primitivními typy)
  • pravěk
• sekvenční soubor – homogenní soubor uspořádaný dle nějakého klíče
  • + sekvenčí přístup; - (minus) přístup k záznamům
• index-sekvenční soubor – sekvenční soubor + (víceúrovňový) index na blocích, příp. oblast přetečení
  • + přístup k záznamům i sekvenční přístup
• indexovaný soubor (také invertovaný soubor) – primární soubor + více indexů na záznamech (klasický index, bitmapy, ..)
  • + přístup k záznamům, k množině záznamů; - sekvenční přístup
• soubor s přímým přístupem – typicky hašování
  • + přístup k záznamům; - přístup k množině i sekvenční přístup
  • perfektní (prosté) hašování
    • Cormack – 2-stupňové hašování přes pomocný adresář
    • Larson & Kalja – 2-stupňové hašování + signatury a separátory stránek
  • dynamické hašování
    • s pomocným adresářem (Fagin)
    • bez adresáře – skupinové štěpení
  • výcerozměrná mřížka (pro OLAP?)

Popis jednotlivých algoritmov

Perfektní hešovaní (Cormack)

Cormakovo hašování je založeno na existenci primární hašovací funkce $ h(k) $, a celé třídy sekundárních hašovacích funkcí $ h_{i}(k,r) $. funkce $ h(k) $ musí mít obor hodnot roven velikosti adresáře. Položky jsou ukládány do primárního souboru (pevné velikosti), způsobem, který bude popsán za pomoci adresáře (pevné velikosti). Protože je i primární soubor i adresář pevné velikosti, řadí se Cormacovo hašování do tzv statických metod hašování.

Primární soubor si jde představit jako pole pevné velikosti. Adresář vypadá následujícím způsobem:

Adresár

pozice	p	i	r
1
2
...
j
...

Význam položek
p je odkaz do primárního souboru
i značí kolikátá hašovací funkce byla použita a
r označje počet položek v primárním souboru, na které se odkazuje p
pozice je index položky v adresáři.

Příklad 1.

Adresár pozice p i r 0 1 1 2 3 2 ... j ...

Primární soubor pozice hodnota 0 1 4 2 5 3 6 4 5 6

Tato situace nám popisuje, že v primárním souboru jsou uloženy 3 položky, všechny v jednom bloku (vede na ně jen jeden pointer p), které jdou od sebe rozlišit hašovací funkcí číslo 2 (i == 2) a první z těchto položek je v primárním souboru na pozici 1 (p == 1).

Jak funguje vkládání

Pokud přidáváme položku s klíčem k, nejprve spočteme $ h(k) $. Pokud je Adresář[$ h(k) $].r == 0, provedeme následující akce

• Adresář[$ h(k) $].r = 1
• Adresář[$ h(k) $].i = $ \heartsuit $ (Pozor, ne 0)!
• V primárním souboru na první volnou pozici s adresou p_new umístíme ukládanou položku
• Adresář[$ h(k) $].p = p_new

Pokud je Adresář[$ h(k) $].r != 0, provedeme následující akce

• Adresář[$ h(k) $].r = Adresář[$ h(k) $].r +1
• Najdeme nejmenší i takové, že $ h_{i}(k,r) $ je růzdné pro nově vkládanou položku a pro všechny položky v datovém bloku příslušném pointeru Adresář[$ h(k) $].p
• Adresář[$ h(k) $].i = i

• V primárním souboru na první volnou a dostatečně velkou pozici s adresou p_new umístíme ukládanou položku a všechny položky z bloku Adresář[$ h(k) $].p v pořadí, které určí klíč sekundární hašovací funce

$ h_{i}(k, r) $

• Adresář[$ h(k) $].p = p_new

Příklad 2.

Zvolne velikost adresáře M=7. Potom $ h(k) $ navrhneme ve tvaru
$ h(k) $ $ h(k)= k \quad mod \quad M $;
$ h_{i}(k, r) = (k \quad << \quad i) \quad mod \quad r $, pro r případ r jemocninou 2;
$ h_{i}(k, r) = (k \quad xor \quad i) \quad mod \quad r $, jinak.
($ << i $ značí bitový posun vlevo o i bitů)

Postupně budeme přidávat do prázného souboru položky 6, 3, 13. $ h(6) = 6, h(3) = 3 $, přidání je tedy triviální a struktury mají po přidání prvních dvou tento tvar.

Adresár pozice p i r 0 1 2 3 1 $ \heartsuit $ 1 4 5 6 0 $ \heartsuit $ 1

Primární soubor pozice hodnota 0 6 1 3 2 3 4 5

Potom se pokusíme přidat 13. $ h(13) = 6 $, což už je obsazeno. Updatneme Adresář[6].r na 2, a najdeme čím je to obsazeno (položkou s klíčem 6), a hledáme první sekundární funkci, která tyto klíče rozliší. To je $ h_{0} $, protože $ h_{0}(6,2) = 0 $, a $ h_{0}(13,2) = 1 $. Takže po vložení 13 budou struktuy vypadat následujícím způsobem

Adresár pozice p i r 0 1 2 3 1 $ \heartsuit $ 1 4 5 6 2 0 2

Primární soubor pozice hodnota 0 1 3 2 6 3 13 4 5

Jak funguje vyhledávání

• spočteme $ h(k) $.
• podle Adresář[$ h(k) $].r se buď podíváme na přímo příslušné místo do primárního souboru, nebo spočteme příslušnou (Adresář[$ h(k) $].i) sekundární hašovací funkci, najdeme příslušný blok a v něm příslušnou položku.

Další často používanou sekundární funkcí je funkce $ h_{i}(k,r)=(k \quad mod \quad (2i + 100r +1))\quad mod \quad r $ Predpokladá se, že $ k << 2i + 100r +1 $.

Pseudokód

Zadefinujeme si ješte nějaké datové položky:

typedef head_1 {int p; int i; int r;}
typedef body_1 {int k; int v;}

head_1 *head=new head_1[s];
body_1 *body=new body_1[];

Vyhledávání

int h(int k, int s) {}
int hi(int i, int k, int r) {}

bool find(int k, int *v) {
    j=h(k, s);
    if (head[j].r==0) return false;
    else {
        body *p=body[head[j].p+hi(head[j].i, k, head[j].r)];
        if (p->k!=k) return false;
        else {*v=p->v; return true;}
    }
}

Vkládání

...je trošku zložitejšie, c-like algoritmus není kompletní, ale je názorný...

int free(int size) {/*nájde voľné miesto v primárnom súbore s veľkosťou size*/}

bool insert(body_1 d) {
    j=h(d.k, s);
    if (head[j].r==0) { //pre daný kľúč ešte nemáme alokovaný blok
        int p=free(1);
        body[p].k=d;
        head[j].p=&body[p]; head[j].i=0; head[j].r=1;
    } else {
        Ak už je hodnota d.k v množine head[j].p - head[j].p+head[j].r, vráť false
        Nájdi voľné miesto pre (head[j].r+1) prvkov
        Nájdi i také, aby hashovacia funkcia hi vrátila pre každý z prvkov (pôvodný blok+d) rôznu adresu
        Premiestni prvky zo starého umiestnenia na nové, zapíš nový prvok
        Oprav adresár
    }
}

Perfektné hashovanie - Larson & Kalja (beta)

• otvorené adresovanie s dvojitým hašhovaním a jedným prístupom
• používa tabuľku pomocných informácií, nazvime ju sep (povolenie), ktorá je podstatne menšia ako u Cormacka. Vyžaduje M*d bitov, kde M je počet stránok adresového priestoru, a d je veľkost pomocnej dátovej štruktúry (reťazec 0 a 1) - separátor/povolenie. Ďalej sa používa M hashovacích funkcií h_i, ktoré pre každý kľúč vracajú postupne postupnosť adries tých stránok, kde je možné hľadať (vložiť) daný záznam; dalších M hashovacích funkcií s_i generuje signatúry kľúča k .

Predstava:

Stránka:

+------+      
| sep  |      
+------+-----+
|  data  sig |   (PS: sig-signatúry záznamov si ukladať nemusíme, pomocou si si ich dopočítame...)
|   ...      |
+------------+

Na začiatku sú všetky stránky prázdne...

   1               2              3                   M
+------+       +------+       +------+            +------+      
| 1111 |       | 1111 |       | 1111 |            | 1111 |      
+------+-----+ +------+-----+ +------+-----+      +------+-----+
|            | |            | |            | ...  |            |
|            | |            | |            |      |            |
+------------+ +------------+ +------------+      +------------+

Vkladanie

1. i=1
2. Keď chceme pridať záznam (k), pomocou h_i(k) zistíme umiestnenie stránky. Potom záznam zahashujeme pomocou s_i, čím získame jeho signatúru.
3. Porovnáme povolenie/separátor stránky so signatúrou záznamu - ak je sep<=sig, pak nastavíme i=i+1 a opakujeme od predchadzajuceho bodu.
4. Inak sme našli správnu stránku - pokúsime sa pridať do nej náš záznam. Záznamy v stránke usporiadame podľa signatúry (od nejmenšího po největší).
5. V prípade, že je záznamov v stránke priveľa (viac ako je veľkosť stránky): vyberieme (vymažeme zo stránky) záznamy s najvačšou signatúrou (teda všetky s rovnakou signatúrou z "vrchu" stránky), túto signatúru nastavíme ako separátor stránky, a vybrané záznamy znovu zahashujeme...

Pridanie jedného prvku (33, h₁=4, s₁=(001)b)...

   4
+------+      
| 111  |      
+------+-----+
|  data  sig |
|   33   001 |
|            |
+------------+

Pridanie ďalších dvoch (11, h₁=4, s₁=(101)b; 15, h₁=4, s₁=(001)b)...

   4
+------+      
| 111  |      
+------+-----+
|  data  sig |
|   11   101 | <= stránka je plná, toto budeme musieť "vyhodiť"
|   33   001 |
|   15   001 |
+------------+
       |
       V
   4
+------+      
| 101  |      
+------+-----+
|  data  sig |
|   33   001 |
|   15   001 |
+------------+

Hodnotu 11 budeme musieť zahashovat znovu, ale tentokrát už nie "pomocou" h₁/s₁, ale niektorých ďalších funkcií...

Vyhľadávanie

Viď bod 0-2 z pridávania :-)

Stromy

• B-stromy