Zkouška 24.1.2012

Logické a fyzické schéma souboru, logický a fyzický záznam. Základní databázové operace. Hierarchie pamětí, magnetická páska, magnetický disk, RAID, jukebox. Halda, sekvenční soubor, index-sekvenční soubor, indexovaný soubor. Bitové indexy. Jednoduchá hašovací schemata. Perfektní hašování. Dynamické hašování, skupinové štěpení stránek. Hašovací schemata na částečnou shodu. B-stromy, B+-stromy. B*-stromy, (a,b)-stromy. Srovnání paralelního přístupu pomocí B-stromů a (a,b)-stromů. Struktury pro vícerozměrnou indexaci: VB-stromy, vícerozměrná mřížka. n-cestný algoritmus třídění.
Merlin
Matfyz(ák|ačka) level I
Příspěvky: 13
Registrován: 3. 2. 2008 01:00
Typ studia: Informatika Bc.
Bydliště: Praha
Kontaktovat uživatele:

Zkouška 24.1.2012

Příspěvek od Merlin »

1) Dotaz na částečnou shodu, atributy A, B, C s pravděpodobnostmi 0.75, 0.2, 0.05, d=15. Spočítat kolik bitů pro jaký atribut, cenu dotazu pro B a průměrnou cenu dotazu.
2) Vložení do redundantního B-stromu.
3) Vyjmutí z neredundantního B-stromu. Hloupej případ, kterej závisí na implementaci algoritmu. Napsal jsem, že moje implementace si půjčuje od levého souseda. Jinak by jeden vrchol podtekl.
4) Co je a k čemu je index-sekvenční soubor.
5) Perfektní hashování pomocí adresáře (Cormack) - vložení klíče.
6) Perfektní hashování Larson & Kajla - vložení klíče. Chtělo si to pořádně rozmyslet. Vkládal se klíč 40, který vynutil vyhození klíče 5 ze zaplněné stránky. Problém byl, že signatura 5 i 40 byla stejná, takže 5 se sice vyhodila, ale 40 se nakonec dala jinam. Ve druhém kroku pak záleželo na tom, jestli se první vložila 40 nebo 5. Pokud se to udělalo chytře, tak už tam bylo jen jedno vyhození a dva inserty. Pokud se to udělalo hloupě, tak to spustilo další kaskádu insertů.
7) Rozšiřitelné hashování (Fagin) - vložení klíče. Bylo potřeba rozšířit adresář na 16 položek.
8 ) K čemu je vícerozměrná mřížka a jaké jsou podmínky pro její použití.
Odpovědět

Zpět na „DBI007 Organizace a zpracování dat I“