od Stevko » 22. 1. 2008 16:48
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í)
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 d[sub]k[/sub] = (d - ∑[sub]i∈{A, B, C}[/sub]lg P[sub]i[/sub])/n + lg P[sub]k[/sub], kde d[sub]k[/sub] je počet bitov pre atribút k, P[sub]k[/sub] 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 2[sup]počet bitov, ktoré nepoznám[/sup]. Pre A je to napríklad 2[sup]15-7[/sup]. Priem!erná cena je presne to, čo poznáme z pravdepodobnosti. E(ceny otázky) = ∑[sub]q∈Q[/sub]P[sub]q[/sub]*cena(q). Q je množina všetkých otázok (dotazov, query). Preto nestačí spočítať iba 0.8*2[sup]8[/sup]+0.1*2[sup]11[/sup]+0.1*2[sup]11[/sup]. 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 2[sup]15-7[/sup]=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 h[sub]i[/sub](K) a s[sub]i[/sub](K). Pozrieme sa na separátor stránky h[sub]i[/sub](K). ak je väčší ako s[sub]i[/sub](K), potom K je buď v tej stránke alebo nie je v súbore vôbec. Ak s[sub]i[/sub](K) je väčšie alebo rovné separátoru stránky h[sub]i[/sub](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í)