Slovar kot temeljni gradnik podatkovnih baz

Slovar ni le koristna podatkovna struktura pri programiranju, pač pa pride prav tudi pri organizaciji podatkov v podatkovnih bazah. Podatkovna baza je ponavadi sestavljena iz ene ali več relacij, vsaka relacija pa je množica zapisov, pri čemer je vsak od njih opisan z več atributi. V praksi si relacijo ponavadi predstavljamo kot tabelo ali razpredelnico, pri čemer vrstice tabele predstavljajo zapise, stolpci pa atribute. Spodnja tabela na primer kaže, kakšna bi bila lahko relacija s podatki o zaposlenih v cirkusu. Ima štiri atribute in pet zapisov:

Pri vsaki relaciji ponavadi določimo enega ali več atributov, ki naj bi skupaj enolično določali vsak zapis. Za te atribute pravimo, da tvorijo ključ te relacije; to pomeni, da se nobena zapisa te relacije ne smeta ujemati v vseh atributih, ki tvorijo ključ. Relacijo si lahko zdaj predstavljamo kot slovar, saj je vsak zapis pravzaprav par <ključ, pripadajoča vrednost>, pri čemer pripadajočo vrednost tvorijo vsi tisti atributi, ki niso del ključa. V zgornjem primeru bi bilo za ključ smiselno uporabiti atributa Ime in Priimek, pripadajočo vrednost pa bi potem tvorila atributa Leto rojstva in Delovno mesto.

Vaja

Operacije, ki jih ponavadi želimo izvesti na zapisih naše podatkovne baze, so prav tiste, ki smo jih na začetku te učne enote spoznali kot osnovne operacije na slovarjih: dodajanje zapisov, brisanje zapisov, iskanje zapisov po danem ključu ter branje ali spreminjanje pripadajoče vrednosti.

Tudi pri implementaciji podatkovnih baz se uporabljajo podobne podatkovne strukture kot za implementacijo slovarjev (drevesa in razpršene tabele), ki pa so v tem primeru prilagojene temu, da se morajo podatki shranjevati na disk.

*Implementacija slovarja z razpršeno tabelo

Doslej smo videli, kaj slovar je in kako ga lahko uporabljamo. Zanimivo vprašanje pa je tudi: kako je slovar pravzaprav sploh implementiran? Ena možnost je drevo, ki smo ga spoznali v učni enoti o množicah; dopolniti ga moramo le s tem, da v vsakem vozlišču poleg ključa hranimo tudi pripadajočo vrednost. Ima pa implementacija slovarja z drevesom nekaj slabosti: za ključe v drevesu mora biti omogočena primerjava glede na nek vrstni red (to je zahteva, ki je slovar v splošnem drugače nima), poleg tega pa časovna zahtevnost operacij na drevesu ni konstantna, ampak je sorazmerna z globino drevesa. Zato si oglejmo še eno podatkovno strukturo, s katero lahko implementiramo slovar. Pravimo ji razpršena tabela (ang. hash table).

Že na začetku te učne enote smo omenili, da je slovar v marsičem podoben tabeli, le da namesto indeksov (ki so mala cela števila od 0 naprej) uporabljamo ključe (ki sploh niso nujno števila). Tako lahko pridemo na misel, da bi slovar lahko hranili v tabeli, če bi znali ključe nekako predelati v indekse.

Pripravimo si tabelo z m celicami in predvidimo, da imamo funkcijo h, ki zna poljuben ključ k preslikati v indeks h(k), ki je eno od števil 0, 1, 2, ..., m - 1. Ko želi uporabnik našega slovarja shraniti vanj nek določeni ključ k, bomo izračunali h(k) in shranili ta ključ (ter pripadajočo vrednost) v naši tabeli na indeksu h(k).

Simulacija