{{collapse|okruhy 09/10 (pro srovnání)|''Metody indexace relací, datové struktury na externí pameti: hašování, B-stromy. Vícerozmerné dotazy pomocí hašovacích metod, vícerozmerných mrížek, vícerozmerných stromu. Prístupové metody k prostorovým objektum: R-stromy a jejich varianty. Vyhledávání v textech: indexy, signatury, metody implementace signatur (vrstvené kódování), usporádání odpovedí.''}}
okruhy 14/15: ''Indexace relacních dat: B-stromy, hašování, GRACE algoritmus. Prístupové metody k prostorovým objektum: R-stromy a jejich varianty. Vyhledávání v textech: boolské a vektorové indexy a indexace, usporádání odpovedí, signatury a jejich implementace.''
=== Indexace relacních dat: B-stromy, hašování, GRACE algoritmus (🎓🎓🎓) ===
{{Zkazky|
* '''Indexace relacnich dat (Hoksza)''' - B-stromy a hasovani - -B B+ B* (proc se pouzivaji - velikost vnitrniho uzlu), hashování 7 druhu, viz Hoksza slajdy
* '''DS - B-stromy a ich varianty (Kopecky)''' - Napisal som si zakladne definicie B, B+, B* a VB stromov. Pobavili sme sa o redundantych/neredundantych stromoch. Potom o dotazoch na viacero atributov z coho sme sa dostali k hasovaniu a dotazom na ciastocnu zhodu a koncilo to iba otazkou na priestorove data. Tam stacilo povedat, ze je na to dobry R-strom. (Tiez niekde v debate padla otazka na paralelny pristup do B-stromu.) Prijemne aj ked pomerne podrobne sa snazil preverit znalosti.
* '''DS - B-stromy a jejich varianty (?)''' - Popsal jsem definice, co splňují, operace, vyváženosti a jaké jsou varianty ((ne)redundantní, B+, B*). Pak chtěl pan Kopecký vědět, k čemu jsou dobré (zmínil jsem indexování) a dlouho se ptal na různé detaily (např. jak zabránit zamykání celého B-stromu při insertu pokud se ke stromu přistupuje paralelně - lze provádět dopředný split již naplněného uzlu, jaká varianta stromu je nejlepší pro indexování, které atributy v DB jsou vhodné pro indexování - záleží např. na doméně, atd.)
}}
{{TODO| mega zjednodusit - sloucit z datovkama a pridat jenom vychytavky z DB (proc se pouzivaji atd)}}
==== B-stromy ====
''viz [[Státnice_-_Stromové_vyhledávací_struktury#B-Stromy|společná část "B-Stromy a jejich varianty"]]''
{{TODO|}}
* redundantni, neredundantni B-strom
* redundantni, neredundantni B*-strom
* redundantni B+-stromy
==== Hashování ====
''viz [[Státnice_-_Hašování|společná část "Hašování"]]''
{{TODO|}}
* perfektni hasovani Cormacka
* perfektni hasovani Larsona a Kalji
* Deskriptory stranek, Grayovy kody (viz Vícerozměrné dotazy implementované pomocí hashovacích metod)
* hasovani Fagina
* dynamicke hashovani Litwina
* skupinove stepeni stranek
==== GRACE algoritmus (grace hash join) ====
{{TODO|}}
This algorithm avoids rescanning the entire S relation by first partitioning both R and S via a hash function, and writing these partitions out to disk. The algorithm then loads pairs of partitions into memory, builds a hash table for the smaller partitioned relation, and probes the other relation for matches with the current hash table. Because the partitions were formed by hashing on the join key, it must be the case that any join output tuples must belong to the same partition.
It is possible that one or more of the partitions still does not fit into the available memory, in which case the algorithm is recursively applied: an additional orthogonal hash function is chosen to hash the large partition into sub-partitions, which are then processed as before. Since this is expensive, the algorithm tries to reduce the chance that it will occur by forming as many partitions as possible during the initial partitioning phase.
*„školní“ verze
Datové struktury: n-tice R a S, kapsy ukazatelů HRi, HSi,
i ∈ {0,1,…,m-1}
hašovací funkce h: dom(A) → <0,m-1>
Algoritmus:
<pre>for k:=1 to nR do begin i :=h(R[k].A); HRi := HRi ∪ {k} end
for k:=1 to nS do begin i :=h(S[k].A); HSi := HSi ∪ {k} end
for i:=0 to m-1 do
begin POMR := ∅; POMS := ∅;
foreach j ∈ HRi do begin r:=R[j]; POMR:=POMR∪{r} end;
foreach j ∈ HSi do begin s:=S[j]; POMS:=POMS∪{s} end;
foreach s ∈ POMS do /* ve vnitřní paměti */
begin foreach r ∈ POMR do
begin if s.A = r.A then begin u:= r * s; WRITE(u)
end
end
end
end</pre>
⇒ pR + pS + nR + nS čtení
vhodnost: když pR /m + pS/m < M
=====GRACE s ukládáním rozdělených relací=====
•M ≥ √(pR*F)
# Zvol h tak, že R lze rozdělit do m = √(pR*F) částí;
# Čti R a hašuj do (výstupních) bufferi, (0 ≤ i ≤ m-1);
#:if bufferi je plný then WRITE(bufferi);
# Proveď (2) pro S;
# for i :=0 to m-1 do begin
## Čti Ri a hašuj do paměti velikosti √(pR*F);
## Čti s ∈ Si a hašuj s.A.
:Existuje-li r ∈ Ri a s.A = r.A, generuj výsledek.
end
Zdůvodnění 4.1: předpoklad - Ri ≈ stejné velké
pR/m = pR/ √(pR*F) = √(pR/F)
Ri vyžaduje prostor F√(pR/F) = √(pR*F)
⇒ 3(pR + pS) I/O operací
:vhodnost: když pR /m + pS/m < M
:poznámky:
*Si mohou být libovolně velké. Vyžadují 1 stránku paměti;
*problém, když V(A,R) je malý;
*vhodné v situacích, když R(K,…), S(K1,K,…);
*nevejde-li se Ri resp. Si do M-2 stránek ⇒ rekurze
tj. Ri se rozdělí na Ri0, Ri1,...,Ri(k-1) stránek;
{{collapse|staré|2=
;Vícerozměrné B-stromy
[http://www.ksi.mff.cuni.cz/~pokorny/vyuka/pokorny/cont.htm slajdy Pokorný]
*lze pomocí nich indexovat soubor podle několika atributů současně.
*celý strom má tolik hladin, kolik je atributů (hlavní strom není B-Strom!)
*pro každý atribut jsou vytvořeny stromy - pro první jeden, pro druhý tolik, kolik má první atribut různých hodnot atd. U každé hodnoty atributu (uzlu stromu) existuje index na strom s dalším atributem.
*jednotlivé vrstvy celého stromu jsou indexovány polem Level (vrstva = jeden atribut) - slouží pro přeskočení prvních i atributů, které nebyly v dotazu zadány
*stromy v jedné vrstvě jsou propojeny do spojáku pomocí NEXT v kořeni, poddoména jednoho stromu je určena pomocí LEFT a RIGHT (uloženy v kořeni), které ukazují do další hladiny na první a poslední strom, který se týká daného stromu. Tedy každý prvek z vrstvy i-1 má ve vrstvě i určeny všechny prvky ve vrstvě i+1, LEFT a RIGHT dává vše.
*podobná struktura by pravděpodobně šla definovat i pro obecný, nebo jakýkoliv jiný vyhledávací strom.
;Metody indexace relací
* relacie mozu byt chapane ako subory, zaznamy suboru ako n-tice relacie, samozrejme su tam rozdiely, napr.:
** schemy vsetkych relacii sa natiahnu naraz s celou DB, subory musime otvarat/zatvarat jednotlivo
*indexsekvenční soubor (indexováno jen podle primárního klíče)
*invertovaný soubor - lze indexovat podle čehokoliv - indexují se přímo záznamy
*bitová mapa
**pro atributy malých domén (pohlaví, typ karoserie vozu...) se pro každou doménu vytvoří bitový vektor a jednička tam kde hodnota pro daný řádek platí, tedy vždy jen jedna jednička na řádku => hodně nul, lze dobře komprimovat
**vyhledávání je rychlé používají se operace AND, OR atd.
**insertem se všechny vektroy prodlouží, přidáním další možnosti (rozšíření domény) se přidá další bitový vektor
**lze využívat i pro GROUP BY, COUNT atd.
;Datové struktury na externí paměti
*hromada - nehomogenni záznamy (ruzne delky) jsou ukládány za sebou (bez dalších podmínek) - vyhledání čehokoliv = projití celé hromady (v nejhorším případě)
*sekvenční soubor - podobný jako hromada, jen záznamy jsou pevné délky (homogenni)
** uspořádaný sekvenční soubor - záznamy uspořádány podle klíče, nově přidávané se ukládají do "souboru aktualizací" a občas je provedena reorganizace, kdy je "soubor aktualizací" vyprázdněn a data z něj zatříděna do uspořádaného sekvenčního souboru. Nalézt záznam lze pak půlením intervalů v case O(log_2(n)).
** indexsekvenční soubor - obdobně jako předchozí jsou záznamy setříděny podle klíče, navíc existují indexy do jednotlivých bloků (stránek). Indexy jsou tvořeny klíči některých záznamů. Celý index je pak jakýsi B-strom. Při přidávání není index reorganizován, ale je použita oblast přetečení, kam je nový záznam vložen. K záznamu, za který měl být nový záznam vložen se pak uloží číslo bloku i číslo záznamu, kde nový záznam leží. V oblasti přetečení jsou tak vytvářeny lineární seznamy.
**invertovaný (indexovaný) soubor - indexují se přímo záznamy, ne bloky (jak tomu je v indexsekvenčním souboru), data nejsou v souboru nijak uspořádána, jednotlivé bloky nemusí být na disku za sebou. Indexů může být více různých. Při přidávání není použita další struktura, přímo se upravují indexy. Používá se v DIS (invertovany soubor).
*ukládání pomocí hashování
*b-stromy
Jiny (urcite lepsi :) popis:
:[http://siret.ms.mff.cuni.cz/skopal/databaze/slidy/DBI025_11.pdf Fyzická implementace relačních databází] (Databázové systémy)
:[http://siret.ms.mff.cuni.cz/sites/default/files/doc/david.hoksza/lectures/ndbi007/2014W/lecture2.pdf File Organizations] (OZD 1)
Definice: '''Klíč''' schématu relace R je nejmensi mnozina atributů ze schématu R, na níz celá R funkčně závisí. Jakmile tedy máme hodnoty pro klíčové atributy, máme jednoznačné určen libovolný řádek tabulky.
;Organizace databázových souborů (podle OZD 1)
:'''Halda''' (hromada / heap file)
::zaznamy maji ruznou delku
::zaznamy jsou vkladany na konec souboru
:'''Sekvenční soubor''' (sequential file)
::''nesetrideny'' - halda s pevnou delkou zaznamu
::''setrideny'' - zaznamy setridene podle klice (narocny INSERT a DELETE)
:'''Index-sekvenční soubor''' (indexed sequential file)
::index nad jednim klicem je vytvoren
::je to vlastne primarni soubor se setridenymi daty podle klice + indexovy soubor, ktery muze mit vice urovni indexu
:'''Indexový soubor''' (index file)
::indexy nad vice klici jsou vytvoreny
::muze obsahovat primarni index (coz je index nad klicem, podle ktereho je setrideny primarni soubor - asi klastrovany index) a obsahuje sekundarni indexy (asi neklastrovane indexy)
:'''Hashovaný / hešovaný soubor''' (hashed file)
::pro jeden atribut (asi i klic) existuje hesovaci funkce
;Vícerozměrné dotazy implementované pomocí hashovacích metod
* viacrozmerne dotazy - obsahuju viac atributov (n>1)
** na uplnu zhodu - hodnoty vsetkych n atributov su pevne dane (n=2: MENO='Jiri' AND MESTO='Praha')
** na ciastocnu zhodu - hodnoty niektorych atributov (<n) su pevne dane
** na uplnu intervalovu zhodu - pre vsetkych n atributov su dane intervaly hodnot (napr. VEK>22)
** na ciastocnu intervalovu zhodu - intervaly hodnot su dane len pre niektore atributy
* implementacia
**'''signatury''' - d bitove binarne retazce
*** signatura zaznamu (dlzky d) je zretazenim signatur jednotlivych atributov, pre kazdy atribut A_i je samostatna hasovacia funkcia h_i, ktora vytvori signaturu dlzky d_i. Plati, ze d_0+d_1+...+d_n=d; n-pocet atributov. Signatura dotazu sa tvori podobne, nezadane atributy su reprezentovane retazcom nul.
*** signatura dotazu Q sa porovnava so signaturami zaznamov S - na pozicii, kde je v Q jednicka, musi byt jednicka aj v S, inak zaznam do odpovede nepatri
**'''deskriptory stranok'''
*** vrstvia sa deskriptory zaznamov v danej stranke pomocou logickeho OR. Deskriptor zaznamu je opat zretazenie deskriptorov atributov A_i, pre kazdy atribut je dana hasovacia funkcia h_i, ktora priradi kazdej hodnote atributu binarny retazec obsahujuci prave 1 jednicku.
*** subor deskriptorov stranok je pripojeny k primarnemu suboru, ak je velky, moze byt dvojurovnovy (prim. subor sa rozdeli do segmentov, kazdy ma svoj subor deskriptorov, tie tvoria 1. uroven; 2. uroven ma deskriptory ukazujuce do 1.)
*** rychlejsie ako signatury, lebo sa musi porovnat menej deskriptorov (ale na ukor pamate); lepsie ako indexovany subor, lebo nerastie cas vyhodnocovania s rastucim poctom atributov v dotaze, pamatove naroky su podobne
**'''grayove kody''' - binarne retazce, hodnoty nasledujuce za sebou sa lisia vzdy len v jednom bite
*** adresa stranky dana signaturou je interpretovana ako grayov kod
*** zaznamy vyhovujuce signature dotazu tvoria zhluky, kde zaznamy su fyzicky za sebou v jednej stranke (alebo viacerych po sebe iducich strankach), nikdy nie je viac pristupov na disku ako u binarneho kodovania
*** dobre pre dotazy na ciastocnu zhodu pri malom pocte zadanych atributov a pre dotazy na intervalovu zhodu
;Vícerozměrná mřížka
[http://www.ksi.mff.cuni.cz/~pokorny/vyuka/pokorny/cont.htm Slajdy Pokorný]
;Vícerozměrné stromy
}}
=== Přístupové metody k prostorovým objektům: R-stromy a jejich varianty (🎓🎓🎓) ===
{{:Implementace_databázových_systémů/RTree}}
=== [[Databázové_modely_a_jazyky#Datab.C3.A1ze_text.C5.AF:_modely_.28boolsk.C3.BD.2C_vektorov.C3.BD.29_.28.F0.9F.8E.93.F0.9F.8E.93.F0.9F.8E.93.F0.9F.8E.93.F0.9F.8E.93.F0.9F.8E.93.F0.9F.8E.93.29 |Vyhledávání v textech: boolské a vektorové indexy a indexace, usporádání odpovedí, signatury a jejich implementace (🎓)]] ===
{{Zkazky|
* '''IDS - Vektorovy a boolovsky model (Kopecky)''' - princip, tvar dotazu a odpovede, implementacia
}}
