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.* ## Interní hašování ## *viz dá se to přežít jenom s interním hashováním* ## Externí hašování ## {{:Státnice_-_Hašování_I2/Externí}} ## GRACE algoritmus ## *viz * ## B-stromy (🎓🎓🎓🎓) ## {{:Státnice_-_Stromové_vyhledávací_struktury_I2/B-Stromy}} {{collapse|staré|2= Vícerozměrné B-stromy :: [slajdy Pokorný](http://www.ksi.mff.cuni.cz/%7Epokorny/vyuka/pokorny/cont.htm) *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: :[Fyzická implementace relačních databází](http://siret.ms.mff.cuni.cz/skopal/databaze/slidy/DBI025_11.pdf) (Databázové systémy) :[File Organizations](http://siret.ms.mff.cuni.cz/sites/default/files/doc/david.hoksza/lectures/ndbi007/2014W/lecture2.pdf) (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 (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 :: [Slajdy Pokorný](http://www.ksi.mff.cuni.cz/%7Epokorny/vyuka/pokorny/cont.htm) 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 }}