[Zk] 2008-01-21

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í.
Uživatelský avatar
Stevko
Matfyz(ák|ačka) level I
Příspěvky: 17
Registrován: 31. 1. 2007 21:52
Typ studia: Informatika Mgr.
Bydliště: kolej

[Zk] 2008-01-21

Příspěvek od Stevko »

Bohužiaľ mi nebolo dovolené vziať si zadanie a nezapísal som si ho presne, lebo ma to napadlo až po odovzdaní, tak aspoň takto.
Úloha 1:
Navrhnite schému hashovania pri otázkach (query, dotazoch) na čiastočnú zhodu. Budú tri atribúty, pravdepodobnosti otázok, ak počítame iba otázky na zhodu jedného atribútu, na jednotlive atribúty sú: 0.8, 0.1, 0.1. Adresa má 15 bitov.
  1. Ako budete adresovať jednotlivé atribúty?
  2. Aká je priemerná cena otázky?
  3. Aká je cena na otázku na atribút A?
Úloha 2:
Prečo sa používajú Grayove kódy (načo sú dobré)? Uveďte zlepšenie v najhoršom a najlepšom prípade.
Úloha 3:
Máte indexovaný súbor, v ktorom je 1125 záznamov, blokovací faktor b je 6. Nad týmto súborom je index primárneho kľúča v B+ strome (m = 60). Tiež máme pri tomto súbore bitovú mapu pre jeden (trojhodnotový) atribút. Bitové mapy sú uložené oddelene. Nič si nedržíme v pamäti.
  1. Aký je minimálny počet prístupov na disk pri vyhľadávaní? (asi 3b)
  2. Aký je počet prístupov na disk pri vkladaní prvku v najlepšom prípade? (asi 3b)
  3. Máme to na disku, kde s = 8,4, r = 4,3 a btt = 0,2. Ako dlho bude trvať vloženie prvku v najhoršom prípade? (určite 5b)
Úloha 4:
Zahashujte 161 do nasledujúcej schémy Faginovho hashovania. Hashovacia funkcia je h(x) = x mod 128.
Adresár mal hĺbku 3, vložené hodnoty boli 25, 28, 35, 42, 70, 100, 125 (a niekoľko ďalších, ktoré boli niekde medzi 42 a 70). (asi 2b)
Úloha 5:
Popíšte vyhľadávanie v perfektonom hashovaní podľa Larsona a Kalju. (asi 3b)
26 bodov spolu, známkovanie: 26-23, 22-20, 20-16, 16-0
michael111
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 14. 1. 2008 18:41
Typ studia: Informatika Bc.

Re: [Zk] 2008-01-21

Příspěvek od michael111 »

no toto bol moj treti pokus ...som teda zvedavy....ale je to vo hviezdach :cry:
michael111
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 14. 1. 2008 18:41
Typ studia: Informatika Bc.

Re: [Zk] 2008-01-21

Příspěvek od michael111 »

aj ked vlastne mi to uz moze byt po 3 pokuse patnast.......ako sa mala robit priemerna cena toho dotazu ?

ja som to robil ako 0.8 * 2^7 + 0.1 * 2^4 + 0.1 *2^4 ale velmi pravdepodobne to je zle..:-(
Uživatelský avatar
cathack
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 31. 1. 2006 14:18
Typ studia: Informatika Bc.

Re: [Zk] 2008-01-21

Příspěvek od cathack »

michael111 píše:aj ked vlastne mi to uz moze byt po 3 pokuse patnast.......ako sa mala robit priemerna cena toho dotazu ?

ja som to robil ako 0.8 * 2^7 + 0.1 * 2^4 + 0.1 *2^4 ale velmi pravdepodobne to je zle..:-(
já myslím, že by to mělo být 0.8 * 2(15-7) + 0.1 * 2(15-4) + 0.1 * 2(15-4) = 2.4 * 28 = 614.4

ale jistý si nejsem.
quick Jesus, IDDQD!
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

Re: [Zk] 2008-01-21

Příspěvek od Myshaak »

cathack píše: já myslím, že by to mělo být 0.8 * 2(15-7) + 0.1 * 2(15-4) + 0.1 * 2(15-4) = 2.4 * 28 = 614.4
ale jistý si nejsem.
tak tak

Me by hodne zajimalo, jak jste resili priklad 3 c) ?
Stevko píše: Ako dlho bude trvať vloženie prvku v najhoršom prípade?
(resp. jak byste ho resili, pro ty z vas, co nebyli na pisemce) Vypada to, ze co clovek, to jiny vysledek a postup... :)
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Uživatelský avatar
Stevko
Matfyz(ák|ačka) level I
Příspěvky: 17
Registrován: 31. 1. 2007 21:52
Typ studia: Informatika Mgr.
Bydliště: kolej

Re: [Zk] 2008-01-21

Příspěvek od Stevko »

Tak náznaky riešenia teda.

Úloha 1:
a) Adresujeme tak, že každému atribútu priradíme nejaký počet bitov (to, aký počet to bude, spočítame zo vzorčeka dk = (d - ∑i∈{A, B, C}lg Pi)/n + lg Pk, kde dk je počet bitov pre atribút k, Pk je pravdepodobnosť otázky na atribút k, n je počet atribútov, d je celkový počet bitov a lg je dvojkový logaritmus. Pozn.: Ten je vždy záporný, lebo pravdepodobnosť je menšia ako 1.) Pre atribút A je to 7, pre B a C sú to po 4 bity.
Tieto bity spojím (concat, poradie je asi rozumné dať tak, aby A bolo na začiatku, ale teória nám k tomu nič nehovorí) a tak získam adresu pre záznam. Keď hľadám nejaký záznam, tak vyrobím tie bity, ktoré viem a prejdem príslušné adresy.
b) Pre každú otázku je jej cena 2počet bitov, ktoré nepoznám. Pre A je to napríklad 215-7. Priem!erná cena je presne to, čo poznáme z pravdepodobnosti. E(ceny otázky) = ∑q∈QPq*cena(q). Q je množina všetkých otázok (dotazov, query). Preto nestačí spočítať iba 0.8*28+0.1*211+0.1*211. To sú totiž iba otázky na jednotlivé atribúty. Ale nie sú tam započítané otázky, keď poznáme napríklad dva atribúty. Z toho, čo bolo v zadaní sa to podľa mňa nedalo spočítať presne.
c) Pre atribút A je cena 215-7=256

Úloha 2:
a) Grayove kódy slúžia presne pri hashovaní z prvého príkladu a to na zníženie počtu nesúvislých úsekov, ktoré treba prejsť. V najhoršom prípade sa nič nezlepší (ale ani nič nezhorší), v najlepšom je to tuším polovica (počet nesúvislých úsekov, ktoré treba prejsť, je polovičný), ale nevidím dôvod, prečo by to nemohlo byť aj viac. Pre presné čísla konzultujte literatúru (slady, skriptá, web. odborné časopisy).

Úloha 3:
Indexovaný súbor je netriedený sekvenčný, ktorý má pri sebe index. V tomto B+ strome v listoch (prípadne aj v uzloch, ak si zvolíme neredundantný, ale podľa ma je redundantný teraz výhodnejší) sú odkazy na konkrétne záznamy v primárnom súbore. Týchto listov môže byť najviac 1125/30 a najmenej 1125/60 (tá 30 aj 60 je ±1, ale na ďalšom to nič nemení). počet listov je stále taký, že nad nimi je už len jeden koreň. Pre atribút, ktorý nadobúda tri hodnoty potrebujeme bitmapy dve (potrebujeme dva bity pre hodnoty a jedna bitmapa je pre spodný a druha pre horný bit) (možno nie, ale predpokládajme to pre ďalšie výpočty). Ďalší rozumný predpoklad je, že uzly tohto B+ stromu sa vždy vojdú do bloku. B+ stromy sa takto zvyknú navrhovať. To, že v prmárnom súbore je 6 záznamov v bloku nič neznamená, lebo "záznam" v strome je primárny kľúč a pointer, pričom v primárnom súbore sú ďalšie atribúty, ktoré ten záznam môžu veľmi zväčšovať. O veľkosti primárneho kľúča nič nevieme. To, že je blokovací faktor 6 nám hovorí, že jeden záznam nepresahuje hranice blokov (aspoň dúfam), takže na načítanie záznamu nemusíme nikdy čítať viac blokov.
Takže za týchto predpokladov:
a) Načítame koreň (prvý prístup), zistíme si, do ktorého listu máme ísť. načítame list (druhý prístup) a zistíme, kde je správny záznam v primárnom súbore. Skočíme na správne miesto v primárnom súbore a prečítame si záznam (tretí prístup). Ten záznam je práve jeden (práve preto sa to, podľa čoho hľadáme volá primárny kľúč). Spolu tri prístupy.
b) Pridávame. Do súboru pridáme na koniec nový záznam (vždy pridávame na koniec súboru) (prvý prístup - na koniec súboru vieme skočiť priamo zo známej veľkosti súboru), pridáme na koniec (v bitmape sú položky v tom istom poradí ako v prim. súbore) oboch bitmáp položku (keďže ich držíme osobitne tak dva súbory, teda dva prístupy). Vložíme pointer do B+ stromu: prístup ku koreňu (jeden prístup), načítanie správneho listu (jeden prístup), zapísanie správneho listu (opäť jeden prístup). List sa nám nerozdelí, lebo máme ideálny prípad. Končíme. Spolu prístupov: 6
c) Náhodný prístup znamená s + r + btt (nastav hlavičky, počkaj, kým sa dotočí, prenes). Pokiaľ z nejakého miesta čítame druhý krát (alebo tam zapisujeme), už nemusíme posúvať hlavičky - odpadá seek. Pridávame. Je to veľmi podobné, ako predchádzajúci prípad (náhodný prístup do súboru, dvakrát bitmapa, nájdenie správneho listu -> zatiaľ 5 náh. prístupov). Máme načítaný list. Ten sa však (v najhoršom prípade) preplnil. Takže ho rozdelíme. Jeden (ten s mešími hodnotami) zapíšeme na pôvodné miesto (prístup bez seeku, teda iba r+bbb), druhý na "náhodné" voľné (jeden náhodný prístup). Pointre medzi listami v B+ strome v iných listoch upravovať nemusíme (teda, za podmienky, že idú len jedným smerom), keďže pointer, ktorý mieril na tento list mieri opäť na časť tohto listu (a to na správnu) a ostatné pointre, ktoré potrebujeme zapísať sú v nami zapisovaných listoch. Ešte potrebujeme update-ovať koreň. Načítame koreň (náhodný prístup) a zapíšeme koreň (prístup bez s). Spolu 7 náhodných prístupov a 2 prístupy bez posunu hlavičiek. Teda 7*(s+r+btt) + 2*(r+btt). Pri týchto hodnotách asi 99.3.
Úloha 4:
Jednoduché Faginovo hashovanie. Každy si určite naštuduje sám (nechce sa mi kresliť). Adresár bude treba zdvojnásobiť.
Úloha 5:
Hľadáme K. V i-tom kroku spočítame hi(K) a si(K). Pozrieme sa na separátor stránky hi(K). ak je väčší ako si(K), potom K je buď v tej stránke alebo nie je v súbore vôbec. Ak si(K) je väčšie alebo rovné separátoru stránky hi(K), musíme hľadať ďalej. Zvýšime i a skúsime znova. Končíme, keď stránku nájdeme, alebo keď už nie sú stránky, na ktorých sme ešte neboli (čo znamená, že tam K nie je, a keby sme ho aj chceli pridať, tak sa to nepodarí - buď plný disk (to nevyriešime) alebo príliš nízke deskriptory (čo sa dá vyriešiť zmenou hashovacích funkcií a kompletnou reorganizáciou). toto však už k vyhľadávaniu asi ani nepatrí)
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 161
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

2Stevko

Příspěvek od Myshaak »

K tej trojce...

jsi si jisty, ze na zapsani zaznamu do souboru Ti skutecne staci jeden jediny pristup? O tom totiz nejsem tak ouplne presvedcen. Kdyz vychazim z toho, ze "Bloky jsou minimální entitou přenášenou mezi primární a sekundární pamětí", tak nemuzu -v momente, kdy v pameti nemam nic nactene(jak to stoji v zadani)- prece do souboru pridat jeden zaznam. :) Jak bych to udelal, kdyz nevim, co jineho v danem bloku/strance je? Neni to tak, ze se musi dany blok nejprve nacist do pameti, tam si do nej v klidu pridam insertovany zaznam ... a pak cely blok zas zapisu zpatky? Tedy 2 pristupy?
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Uživatelský avatar
Stevko
Matfyz(ák|ačka) level I
Příspěvky: 17
Registrován: 31. 1. 2007 21:52
Typ studia: Informatika Mgr.
Bydliště: kolej

Pridanie do súboru

Příspěvek od Stevko »

Asi to tak bude. Tak si každý určite opraví príslušný počet prístupov (v ideálnom prípade píšeme do nového prázdneho bloku a teda nepristupujeme k starému - a to ani v bitových mapách, aj keď je to veľmi nepravdepodobné, ale je to ideálny prípad; v zlom prípade pridáme pri zápise do súboru a pri zápise do bitových máp dva prístupy - teda urobíme načítanie bloku (s+r+btt) a zápis na to isté miesto (r+btt)). A ja budem dúfať, že to v mojej písomke nebude príliš vadiť.
I keď disk by mal byť snáď schopný začať zapisovať kamkoľvek a kód:

Kód: Vybrat vše

fseek(subor, 0, SEEK_END);
fwrite(&zaznam, sizeof(zaznam), 1, subor);
by snáď nemal potrebovať dva prístupy. Lenže asi potrebuje.
Control

Re: [Zk] 2008-01-21

Příspěvek od Control »

ladies and gentlemen, na http://www.ksi.mff.cuni.cz/~zemlicka/vyuka/DBI007/ jsou k videni dalsi vysledky...

Zaroven timto vyhlasuju konkurz na spolubojovnika, ktery semnou pujde na letni termin :]
Zivotopisy posilejte na ICQ 256 551 296
Uživatelský avatar
Stevko
Matfyz(ák|ačka) level I
Příspěvky: 17
Registrován: 31. 1. 2007 21:52
Typ studia: Informatika Mgr.
Bydliště: kolej

Re: [Zk] 2008-01-21

Příspěvek od Stevko »

Tak, už mám výsledky a teda viem aké chyby boli v predchádajúcich riešeniach.
Úlohy 1 a 2 a 4 -> riešenia ostávajú.
Úloha 5 -> v písomke som nemal ukončenie hľadania (a viac ľudí malo túto chybu), za čo strhával bod s poznámkou, že či cyklíme donekonečna.
No, a úloha 3.
a) ostáva.
Rozdiely sú nasledovné:
Bitové mapy sú v troch súboroch. Pre jeden atribút, ktorý môže mať tri hodnoty treba tri bitové mapy.
Pred zapísaním bloku ho treba načítať, a to aj v ideálnom prípade. Keď máme 1125 záznamov a v bloku je ich 6, znamená to, že posledný blok nie je plný a preto ho treba pred zápisom načítať. Ináč sa kazia dáta. Načítať pred zmenou treba aj bitmapy (všetky tri).
Načítanie, zmena a zapísanie bloku trvá (r+s+btt)+2*r. Prvé je načítanie, potom sú hlavičky na konci bloku, tak sa chvíľu točí disk, kým sa nedostane na začiatok bloku a potom zapisuje, kým sa nedostane na koniec bloku. A to je presne jedna otáčka (z konca bloku na koniec bloku).
No, a to by boli asi komentáre k písomke.
Malá errata k zadaniam tu na webe: Úloha 3c) časy boli s=8,5, r=4,2, btt=0,2 (snáď už ich mám dobre), úloha 4: zahashované čísla boli 25, 28, 35, 42, 55, 62, 70, 99, 100, 115, 125.ô
Bodovanie:
1a) 3
1b) 2
1c) 2
2) 3
3a) 3
3b) 3
3c) 5
4) 2
5) 3
Odpovědět

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