COMPUTERWORLD
pod kapotou
Bitové mapy a vektory

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).

PŘEDSTAVENÍ

RID

JMÉNO_F

NÁZEV_K

 

1

Apokryfy

Metro

 

2

Apokryfy

Dukla

 

3

Apokryfy

Mír

 

4

Babička

Metro

 

5

Babička

Blaník

 

6

Babička

Jalta

 

7

Dobrý člověk

Blaník

 

8

Dobrý člověk

Metro

 

9

Dobrý člověk

Mír

 

10

Dobrý člověk

Jalta

 

11

Dobrý člověk

Dukla

 

12

Návrat

Mír

 

13

Návrat

Metro

 

14

Návrat

Jalta

 

15

Návrat

Blaník

 

16

Návrat

Dukla

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

Mír 0010000010010000

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. 219) 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 2k 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 pi(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.



<seznam dílů seriálu>   <COMPUTERWORLD>