V souvislosti s nov²mi verzemi relaΦnφch databßzov²ch server∙ se objevuje op∞t jeden staro-nov² pojem tzv. bitovΘ mapy Φi bitovΘ vektory. Jde o velmi efektivnφ mo₧nost indexace °ßdk∙ tabulek relaΦnφ databßze. Princip je velmi jednoduch². Uva₧ujme atribut relace s dostateΦn∞ malou domΘnou. Mezi takovΘ atributy pat°φ nap°. POHLAV═ (jeho domΘna obsahuje pouze dv∞ hodnoty), nebo ╚═SLO KALEND┴╪N═HO M╠S═CE (obsahuje 12 hodnot). Uva₧ovat by se dala i tabulka platov²ch t°φd spolu s kategoriemi v∞ku v rozpoΦtov²ch organizacφch. Tato tabulka obsahuje po dubnu 1996 144 polφΦek. Nap°. T╪═DA-10 v KATEGORII-6 (praxe do 6 let) udßvß zßkladnφ plat 7100 KΦ.

P°edstavme si dßle soubor Φi relaci R s atributem A, kter² mß takovou domΘnu (oznaΦφme ji dom(A)). Pak lze indexovat tak, ₧e pro ka₧dou hodnotu aktußlnφ domΘny v zkonstruujeme vektor bit∙, kde hodnota 1 na i-tΘ pozici vektoru se interpretuje jako fakt, ₧e pro i-t² prvek R platφ R.A = v. Naopak hodnota 0 na i-tΘ pozici vektoru indikuje, ₧e pro i-t² prvek R danß podmφnka neplatφ. Aktußlnφ domΘnou zde myslφme ty hodnoty z dom(A), kterΘ se skuteΦn∞ vyskytujφ v R.A. Je z°ejmΘ, ₧e Φφm v∞tÜφ bude aktußlnφ domΘna atributu A, tφm vφce bude bitov²ch vektor∙, ovÜem vφce zapln∞n²ch hodnotou 0 a mßlo obsahujφcφch 1. Bitovß mapa je vlastn∞ mapou v²skyt∙. V extrΘmnφm p°φpad∞ lze vytvo°it Boolskou matici, kterß zobrazuje vÜechny atributy relace a vÜechny hodnoty jejich aktußlnφch domΘn.

Ukß₧eme bitovΘ vektory na naÜem Φasto pou₧φvanΘm p°φklad∞ - relaci P╪EDSTAVEN═. Pro lepÜφ p°edstavu jsou u relace vid∞t Φφsla °ßdk∙ (RID).

DomΘnou atributu N┴ZEV_K je mno₧ina { Dukla, Blanφk, Jalta, Metro, Mφr} . Nßsledujφcφ bitovΘ °et∞zce p°edstavujφ realizaci ·plnΘho indexu atributu N┴ZEV_K:

Dukla 0100000000100001

Blanφk 0000101000000010

Jalta 0000010001000100

Metro 1001000100001000

Mφr 0010000010010000

V implementaci vy₧aduje index pomocφ bitov²ch vektor∙ jeÜt∞ tabulku hodnot z domΘny danΘho atributu a propojenφ na jednotlivΘ vektory.

ZajφmavΘ jsou dv∞ otßzky:

• jak se dajφ bitovΘ vektory efektivn∞ vyu₧φt pro vyhodnocovßnφ dotaz∙ a
• jak je celkov² index velk².

Dotazy, pro kterΘ se hodφ bitovΘ vektory, jsou dßny Boolsk²mi v²razy nad jednou relacφ. V naÜem jednoduchΘm p°φpad∞ by mezi takovΘ pat°il nap°. dotazy

D1: ôNajdi filmy, kterΘ dßvajφ v kin∞ Metro nebo Mφrö

D2: ôNajdi filmy, kterΘ dßvajφ v kin∞ Dukla a ne v kinu Mφrö

apod. UvedenΘ dotazy, resp. obecn∞ jak²koli Boolsk² dotaz, se bude °eÜit pomocφ logick²ch operacφ aplikovan²ch na bitovΘ vektory. OznaΦφme-li bitov² vektor pro hodnotu x jako x , pak dotaz D1 se bude °eÜit jako Metro or Mφr, dotaz D2 jako Dukla and not Mφr. Operßtory or, and a not se implementujφ pomocφ obvykl²ch logick²ch operacφ dostupn²ch v b∞₧n²ch programovacφch jazycφch. Je samoz°ejmΘ, ₧e bitovΘ °et∞zce se budou Φφst do vyrovnßvacφch pam∞tφ (buffer∙) a zpracovßvat po Φßstech podle mo₧nostφ, kterΘ logickΘ operace v tom Φi onom jazyku vy₧adujφ.

Vyhodnotφme-li D1 na dan²ch bitov²ch vektorech, obdr₧φme:

Metro 1001000100001000

or 1011000110011000

tj. v²sledek je tvo°en °ßdky s mno₧inou RID { 1, 3, 4, 8, 9, 13, 13} .

P°ipome≥me, ₧e u dotaz∙ D1 i D2 Ülo o podmφnky kladenΘ na jeden atribut. Samoz°ejm∞, bitovΘ vektory mohou existovat pro vφce atribut∙ jednΘ relace a BoolskΘ dotazy se tak mohou mφt obecn∞jÜφ tvar.

Co se t²Φe aktualizace takto pojatΘho indexu, uvedeme pouze chovßnφ vynucenΘ operacφ INSERT vklßdajφcφ nov² °ßdek do relace. Pro dan² atribut to znamenß, ₧e do jistΘho bitovΘho °et∞zce p°ibude jeden bit. Vlo₧enφ hodnoty nevyskytujφcφ se v aktußlnφ domΘn∞ vede k zalo₧enφ novΘho bitovΘho °et∞zce.

Co se t²Φe pam∞¥ov²ch nßrok∙ na bitovΘ vektory, pom∙₧eme si op∞t p°φkladem. Uva₧ujme relaci R obsahujφcφ 524 288 (tj. 2¹⁹) n-tic. Pak jeden bitov² vektor mß velikost 64 Kbyte. Obsahuje-li aktußlnφ domΘna °ßdov∞ desφtky hodnot, dostaneme se s indexem pro jeden atribut na n∞kolik Mbyte (prostor pot°ebn² na reprezentaci hodnot domΘny lze zanedbat). To se m∙₧e zdßt mnoho. Srovnejme vÜak tuto velikost s velikostφ R. Jsou-li velikosti °ßdk∙ relace R do 1 Kbyte, vyjde nßm po₧adovan² prostor pro relaci 1/2 Gbyte, tj. index tvo°φ °ßdov∞ procenta z velikosti primßrnφch dat.

DalÜφ mo₧nosti ·spory mφsta nabφzφ komprese. Tφm, ₧e se p°i vyhodnocovßnφ dotazu pou₧ije pouze n∞kolik bitov²ch vektor∙, lze je ka₧d² zvlßÜ¥ komprimovat a dekomprimovat pouze v okam₧iku pou₧itφ. Navφc, dφky jejich sekvenΦnφmu charakteru zpracovßnφ, je mo₧nΘ je dekomprimovat po Φßstech, tj. v provozu staΦφ buffery velikosti °ßdov∞ n∞kolik Kbyte.

Jak ale takovß metoda komprese pro bitovΘ °et∞zce vypadß. Je mo₧nΘ nap°. ·sp∞Ün∞ pou₧φt vÜeobecn∞ znßmΘ Huffmanovo k≤dovßnφ. ╪et∞zce se rozbijφ na bloky pevnΘ dΘlky o k bitech, spoΦtou se jejich pravd∞podobnosti. To je celkem jednoduchΘ, nebo¥ v∞tÜinou lze vyu₧φt nßsledujφcφ p°edpoklad o zdroji informace (ZI):

Zdroj informace mß parametr p, kter² °φkß, ₧e 0-bit v bitovΘm °et∞zci (interpretovanΘm jako soubor index∙) mß pravd∞podobnost v²skytu p a 1-bit pravd∞podobnost 1-p. Jde tedy o nezßvislost na ostatnφch bitech, tj. vlastn∞ na ostatnφch zßznamech v primßrnφm souboru.

Existuje 2^k r∙zn²ch blok∙, kde nech¥ i jich obsahuje 0. Pravd∞podobnosti v²skytu t∞chto blok∙ jsou pak vzhledem k p°edpokladu ZI rovny pⁱ(1-p)^k-i. Tedy pravd∞podobnosti blok∙ se dajφ odhadnout pouze ze statistick²ch znalostφ o domΘn∞. Huffman∙v strom se ji₧ sestrojφ b∞₧n²m zp∙sobem. Lze tuÜit, ₧e pro velkΘ p, tj. hodn∞ nul v bitovΘm vektoru, bude velmi Φast² blok sklßdajφcφ se ze sam²ch nul, tj. v Huffmanov∞ k≤du mu bude pat°it k≤dovΘ slovo velmi malΘ dΘlky. Dß se ukßzat, ₧e nap°. pro p = 9, a k = 8 bit∙ bude zisk komprese 2,1. Tedy dΘlku bitovΘho vektoru lze srazit zhruba na polovinu. Zde ale poznamenejme, ₧e bitovΘ vektory lze komprimovat mnohem efektivn∞ji. N∞kterΘ prameny dokonce uvßd∞jφ metody, kdy po kompresi lze vektor ulo₧it do 0,05 % p∙vodnφ pam∞ti.

BohatΘ vyu₧itφ majφ bitovΘ vektory v systΘmech zpracovßnφ ·pln²ch text∙, kde se pro danΘ slovo vytvo°φ bitov² vektor jeho v²skyt∙ v n∞jakΘ jednotce textu (nap°. °ßdku, strßnce apod.) Obecn∞ se bitovΘ vektory u₧φvajφ vÜude tam, kde vy₧adujeme informaci typu ANO/NE. Mezi takovΘ pat°φ nap°. informace o obsazenosti strßnky zßznamy, o uzamΦenφ zßznamu, otev°enφ kurzoru apod.

Co °φci zßv∞rem? V souvislosti s modernizacφ relaΦnφch databßzov²ch server∙ se op∞t m∙₧eme utvrdit v tom, ₧e starΘ myÜlenky staΦφ jen vzφt, oprßÜit a realizovat. Pro historicky orientovanΘ Φtenß°e uvßdφm, ₧e bitovΘ °et∞zce pro indexovßnφ pou₧ili Davis a Lim ji₧ v r. 1965 (Φlßnek Secondary key retrieval using an IBM 7090-1301 system, CACM 8, 4, April 1965). Chce to ovÜem hledat a cφtit tlak tvrdΘ konkurence.