8. Tietokantojen teoria

Tietokannan sisällön esittäminen relaatiomallin mukaisesti tauluina ja riveinä tuntuu nykyään lähes itsestään selvältä tavalta, mutta tämä oli aikoinaan mullistava idea tietokanta-alalla. Tässä luvussa tutustumme relaatiomallin matemaattiseen taustaan, joka syntyi 1970-luvulla.

Matemaattinen tausta

Joukko

Joukko (set) on kokoelma alkioita. Esimerkiksi \(A=\{1,2,3,4,5\}\) ja \(B=\{apina, banaani, cembalo\}\) ovat joukkoja. Joukko voi olla myös ääretön. Esimerkiksi joukko \(\{1,2,3,\dots\}\) sisältää kaikki positiiviset kokonaisluvut.

Joukon alkioilla ei ole tiettyä järjestystä. Esimerkiksi \(\{1,2,3\}\), \(\{1,3,2\}\) ja \(\{2,3,1\}\) tarkoittavat samaa joukkoa. Tietty alkio voi esiintyä joukossa enintään kerran. Esimerkiksi \(\{1,2,1\}\) ei ole joukko, koska alkio \(1\) esiintyy kahdesti.

Osajoukko

Osajoukko (subset) sisältää osan joukon alkioista. Esimerkiksi joukon \(\{1,2,3\}\) osajoukot ovat \(\emptyset\), \(\{1\}\), \(\{2\}\), \(\{3\}\), \(\{1,2\}\), \(\{1,3\}\), \(\{2,3\}\) ja \(\{1,2,3\}\). Merkintä \(\emptyset\) tarkoittaa tyhjää joukkoa.

Äärettömän joukon \(\{1,2,3,\dots\}\) osajoukkoja ovat esimerkiksi \(\{1\}\), \(\{2,8,25\}\) ja joukko \(\{2,4,6,\dots\}\), joka sisältää parilliset positiiviset kokonaisluvut.

Monikko

Monikko (tuple) on lista alkioita tietyssä järjestyksessä. Esimerkiksi \((1,3,2)\) on monikko, jossa on \(3\) alkiota.

Monikossa alkioiden järjestyksellä on merkitystä. Esimerkiksi \((1,2,3)\), \((1,3,2)\) ja \((2,3,1)\) ovat kolme eri monikkoa. Monikossa sama alkio voi toistua monta kertaa. Esimerkiksi \((1,2,1)\) on monikko, jossa toistuu kahdesti alkio \(1\).

Karteesinen tulo

Karteesinen tulo (Cartesian product) \(S_1 \times S_2 \times \dots \times S_k\) sisältää kaikki monikot, jotka muodostuvat valitsemalla järjestyksessä yksi alkio jokaisesta joukosta \(S_1,S_2,\dots,S_k\).

Kun \(A=\{1,2,3\}\) ja \(B=\{x,y,z\}\), niin

Kun \(A=\{1,2,3\}\), \(B=\{x\}\) ja \(C=\{1,2\}\), niin

Kun \(A=B=\{1,2,3,\dots\}\), niin

eli karteesinen tulo sisältää kaikki parit \((a,b)\), joissa \(a\) ja \(b\) ovat positiivisia kokonaislukuja.

Relaatio

Relaatio (relation) on karteesisen tulon osajoukko. Kun \(A=\{1,2,3\}\) ja \(B=\{x,y,z\}\), niin karteesisen tulon \(A \times B\) relaatioita ovat esimerkiksi:

Relaatio tarkoittaa siis sitä, että valitaan jokin osajoukko kaikista mahdollisista alkioiden muodostamista yhdistelmistä.

Relaatiomalli

Tietokannan taulu voidaan esittää matemaattisesti relaationa, jonka jokainen monikko vastaa yhtä taulun riviä. Kun taulussa on \(k\) saraketta, relaatiossa jokaisessa monikossa on vastaavasti \(k\) alkiota, joista käytetään nimeä attribuutti. Relaation taustalla on karteesinen tulo

jossa joukot \(S_1,S_2,\dots,S_k\) ilmaisevat, mitä arvoja kussakin attribuutissa voi olla. Toisin sanoen joukko \(S_i\) ilmaisee attribuutin \(i\) tyypin.

Esimerkiksi jos \(S_i=\{1,2,3,\dots\}\) eli positiivisten kokonaislukujen joukko, attribuutin \(i\) tyyppi on positiivinen kokonaisluku.

Esimerkki

Tarkastellaan esimerkkinä taulua Tuotteet, jossa on tietoa tuotteista:

Tämä taulu vastaa relaatiota

jossa on viisi monikkoa ja jokainen monikko muodostuu kolmesta attribuutista “id”, “nimi” ja “hinta”.

Tämän relaation taustalla on karteesinen tulo \(S_1 \times S_2 \times S_3\), jossa joukot \(S_1\), \(S_2\) ja \(S_3\) määrittelevät attribuuttien “id”, “nimi” ja “hinta” tyypit.

Esimerkiksi \(S_1\) voisi olla \(\{1,2,3,\dots\}\), mikä tarkoittaa, että attribuutissa “id” on positiivinen kokonaisluku.

Teoria vs. käytäntö

SQL-tietokannan taulut muistuttavat relaatiomallin relaatioita, mutta niissä on kuitenkin joitakin eroja verrattuna relaatiomalliin.

Yksi ero on, että relaatiossa jokainen monikko on erilainen (koska relaatio on joukko), mutta SQL-tietokannan taulussa voi olla monta samanlaista riviä. Esimerkiksi voimme luoda seuraavasti taulun Testi ja lisätä siihen kolme samanlaista riviä:

sqlite> CREATE TABLE Testi (x INTEGER);
sqlite> INSERT INTO Testi VALUES (1);
sqlite> INSERT INTO Testi VALUES (1);
sqlite> INSERT INTO Testi VALUES (1);
sqlite> SELECT * FROM Testi;
1
1
1

Usein tosin SQL-tietokannan taulussa on sarake id, joka takaa, että taulussa ei ole kahta samanlaista riviä, koska jokaisella rivillä on eri id-numero.

Toinen ero on, että relaatiossa jokaisella monikon attribuutilla tulee olla arvo mutta SQL-tietokannan taulussa sarakkeessa voi olla NULL eli arvo puuttuu.

Relaatio-operaatiot

Relaatio-operaatioiden avulla olemassa olevista relaatioista voidaan muodostaa uusi relaatio. Tämä vastaa SQL:ssä kyselyä, jossa taulusta tai tauluista muodostetaan tulostaulu. Tutustumme seuraavaksi esimerkkinä kolmeen keskeiseen relaatio-operaatioon: projektio, restriktio ja liitos.

Projektio

Projektio \(\Pi\) muodostaa relaation, jossa monikoista valitaan tietyt attribuutit. Projektio vastaa SQL-kyselyä, jossa valitaan tietyt sarakkeet taulusta. Esimerkiksi projektio \(\Pi_{nimi,hinta}(T)\) vastaa SQL-kyselyä SELECT nimi, hinta FROM Tuotteet.

Esimerkkejä:

Huomaa, että mahdolliset toistuvat monikot suodattuvat pois projektiosta, koska projektio on relaatio. Tämän takia projektiossa \(\Pi_{hinta}(T)\) on vain neljä monikkoa, koska kahdella tuotteella on sama hinta.

Restriktio

Restriktio \(\sigma\) muodostaa relaation, joka sisältää tietyt ehdot täyttävät monikot. Restriktio vastaa SQL-kyselyä, jossa rivit valitaan WHERE-osassa. Esimerkiksi restriktio \(\sigma_{hinta \le 5}(T)\) vastaa SQL-kyselyä SELECT * FROM Tuotteet WHERE hinta <= 5.

Esimerkkejä:

Yhdistämällä projektio ja restriktio saadaan vastine esimerkiksi SQL-kyselylle SELECT nimi FROM Tuotteet WHERE hinta <= 5:

Liitos

Liitos \(\bowtie\) muodostaa relaation, jonka monikot on koostettu kahden relaation pohjalta. Tämä vastaa SQL:ssä kahden taulun kyselyä.

Tarkastellaan esimerkkinä seuraavia tauluja Henkilot ja Yritykset:

Näitä tauluja vastaavat seuraavat relaatiot:

Nyt kyselyä SELECT * FROM Henkilot H, Yritykset Y WHERE H.yritys_id = Y.id vastaa seuraava relaatio-operaatio:

Yhdistämällä tähän projektion saamme haettua kunkin henkilön nimen ja yrityksen nimen:

Teoria vs. käytäntö

Relaatio-operaatioiden avulla voidaan toteuttaa hakuja samaan tapaan kuin SQL-kyselyillä, mutta tässäkin SQL-kielessä on joitakin eroja.

Kuten näimme aiemmin, projektio \(\Pi_{hinta}(T)\) sisältää jokaisen eri hinnan vain kerran, kun taas kyselyn SELECT hinta FROM Tuotteet tulostaulussa voi olla monta kertaa sama hinta. SQL:ssä on itse asiassa kaksi eri tapaa hakea tietoa:

• SELECT ALL ...: haetaan kaikki rivit, myös toistuvat rivit
• SELECT DISTINCT ...: haetaan jokainen erilainen rivi vain kerran

Ensimmäinen tapa on oletus ja sanaa ALL ei käytetä yleensä, mutta toistuvat rivit voidaan poistaa sanan DISTINCT avulla. Tarkasti ottaen projektiota \(\Pi_{hinta}(T)\) vastaa siis kysely SELECT DISTINCT hinta FROM Tuotteet.

SQL:ssä rivien järjestyksellä voi olla väliä, kun taas relaation monikoilla ei ole järjestystä. Rivien järjestys näkyy SQL:ssä esimerkiksi kyselyssä, jonka lopussa oleva ORDER BY järjestää tulostaulun rivit halutulla tavalla. Relaatio-operaatioilla ei ole mahdollista toteuttaa tällaista hakua.

Avaimet ja riippuvuudet

Avaimiin liittyviä käsitteitä ovat:

• Yliavain (superkey) on attribuuttien yhdistelmä, joka on varmasti erilainen jokaisessa relaation monikossa. Yliavain yksilöi siis jokaisen relaatiossa olevan monikon.

• Kandidaattiavain (candidate key) eli avain (key) on minimaalinen yliavain. Minimaalisuus tarkoittaa, että jos yliavaimesta poistetaan mikä tahansa attribuutti, niin kyseessä ei ole enää yliavain.

• Pääavain (primary key) on yksi avaimista, joka on nostettu erikoisasemaan.

Esimerkki

Tarkastellaan esimerkkinä tuotteita kuvaavaa relaatiota, jonka attribuutit ovat “id”, “nimi” ja “hinta”:

Tässä relaatiossa yliavaimia ovat ainakin “id”, (“id”, “nimi”), (“id”, “hinta”) ja (“id”, “nimi”, “hinta”). Nämä attribuuttien yhdistelmät ovat yliavaimia, koska ne yksilöivät jokaisen relaatiossa olevan monikon. Näistä yliavaimista vain “id” on avain, koska muut yliavaimet eivät ole minimaalisia.

Attribuutti “hinta” ei ole yliavain, koska monella tuotteella voi olla sama hinta. Attribuutti “nimi” on yliavain siinä tapauksessa, että jokaisella tuotteella on eri nimi. Yhdistelmä (“nimi”, “hinta”) on yliavain, jos ei voi olla kahta tuotetta, joilla olisi sekä sama nimi että sama hinta. Riippuu siis tietoon liittyvistä oletuksista, mitkä attribuuttien yhdistelmät ovat yliavaimia.

Avaimen valinta

Avain voi olla joko luonnollinen avain (natural key) tai sijaisavain (surrogate key). Luonnollinen avain muodostuu alkuperäisestä tiedosta, kun taas sijaisavain on lisätty mukaan nimenomaan sen takia, että siitä tulisi avain. Esimerkiksi (“nimi”, “hinta”) on luonnollinen avain, kun taas “id” on sijaisavain.

Tietokantojen teoriassa käytetään usein luonnollisia avaimia, mutta käytännön tietokannoissa avain on yleensä id-numero tai vastaava sijaisavain. Etuna id-numerossa on, että se on kompakti tieto, joka kelpaa varmasti avaimeksi. Jos valittaisiin jokin luonnollinen avain, pitäisi pohtia, riittävätkö valitut attribuutit varmasti yksilöimään monikon kaikissa tapauksissa.

Funktionaalinen riippuvuus

Funktionaalinen riippuvuus (functional dependency) \(A \to B\) tarkoittaa, että attribuuteista \(A\) voidaan päätellä attribuutit \(B\). Toisin sanoen jos relaatiossa on kaksi monikkoa, joissa attribuutit \(A\) ovat samat, niin myös attribuutit \(B\) ovat samat.

Esimerkiksi jos relaatiossa on attribuutit “postinumero” ja “kaupunki”, siinä on funktionaalinen riippuvuus “postinumero” \(\to\) “kaupunki”, koska postinumerosta voidaan päätellä kaupunki. Toisin sanoen ei voi olla kahta monikkoa, joissa olisi sama postinumero mutta eri kaupunki.

Attribuutit \(A\) muodostavat yliavaimen tarkalleen silloin, kun \(A \to B\) pätee mille tahansa attribuuteille \(B\). Tämä vastaa sitä, että missä tahansa relaation monikossa yliavaimen attribuutit yksilöivät, mistä monikosta on kyse.

Tarkastellaan esimerkkiä, jossa relaation attribuutit ovat “id”, “nimi” ja “hinta”. Koska “id” on relaation yliavain, pätee funktionaalinen riippuvuus “id” \(\to\) (“nimi”, “hinta”) eli attribuutista “id” voidaan päätellä attribuutit “nimi” ja “hinta”.

Normaalimuodot

Normaalimuoto (normal form) on tietokannan relaatioon liittyvä vaatimus, jonka tavoitteena on edistää tiedon eheyttä ja helpottaa tietokannan käyttämistä. Normaalimuodoissa on teoreettisessa muodossa samanlaisia ajatuksia kuin luvun 6 tietokannan suunnitteluperiaatteissa.

Tavallisimmat normaalimuodot ovat ensimmäinen, toinen ja kolmas normaalimuoto, joihin tutustumme seuraavaksi.

Ensimmäinen normaalimuoto

Relaatio toteuttaa ensimmäisen normaalimuodon, kun relaation jokaisessa attribuutissa on yksittäinen arvo.

Esimerkiksi seuraava relaatio ei toteuta ensimmäistä normaalimuotoa, koska attribuutissa “toimistot” on lista toimistoista.

Voimme kuitenkin muuttaa relaatiota seuraavasti, jolloin se toteuttaa ensimmäisen normaalimuodon.

Toinen normaalimuoto

Relaatio toteuttaa toisen normaalimuodon, kun se toteuttaa ensimmäisen normaalimuodon ja lisäksi relaatiossa ei ole funktionaalista riippuvuutta \(A \to B\), jossa \(A\) on avaimen osa ja \(B\) on avaimen ulkopuolella.

Toisella normaalimuodolla on merkitystä vain silloin, kun avain muodostuu useammasta attribuutista. Näin on seuraavassa relaatiossa:

Tässä relaatiossa (“nimi”, “toimisto”) on avain, koska nämä attribuutit yksilöivät jokaisen monikon. Kuitenkin relaatiossa on funktionaalinen riippuvuus “toimisto” \(\to\) “maa”, koska toimiston kaupungista voidaan päätellä maa.

Relaatio ei toteuta toista normaalimuotoa, koska siinä on avaimen (“nimi”, “toimisto”) ulkopuolinen attribuutti “maa”, joka riippuu avaimen osasta “toimisto”.

Voimme jakaa relaation seuraavasti kahdeksi relaatioksi, minkä jälkeen toinen normaalimuoto toteutuu.

Kolmas normaalimuoto

Relaatio toteuttaa kolmannen normaalimuodon, jos se toteuttaa ensimmäisen ja toisen normaalimuodon sekä lisäksi relaatiossa ei ole funktionaalista riippuvuutta \(A \to B\), jossa \(A\) ja \(B\) ovat toisistaan erillisiä avaimen ulkopuolisia attribuuttien joukkoja.

Esimerkiksi seuraava relaatio ei toteuta kolmatta normaalimuotoa:

Relaation attribuutti “kaupunki” riippuu attribuutista “postinumero”, koska postinumerosta voidaan päätellä kaupunki. Tämän vuoksi relaatio ei toteuta kolmatta normaalimuotoa.

Voimme jakaa relaation seuraavasti kahdeksi relaatioksi, minkä jälkeen kolmas normaalimuoto toteutuu.

Teoria vs. käytäntö

Normaalimuotojen merkityksenä on, että ne antavat teoreettisen näkökulman tietokantojen suunnitteluun. Esimerkiksi jos tietokanta ei toteuta kolmatta normaalimuotoa, tietokannan rakenteessa voi olla parantamista.

Normaalimuodoissa on usein ideana vähentää relaatioissa olevia riippuvuuksia, joiden takia relaatioissa voi olla toisteista tietoa. Jos relaatio ei toteuta normaalimuotoa, ratkaisuna on usein jakaa relaatio useaksi relaatioksi, mikä vähentää toisteista tietoa.

Käytännössä tietokantoja ei kuitenkaan yleensä suunnitella normaalimuotojen avulla vaan luvun 6 periaatteiden tyylisesti. Normaalimuodot kuvaavat osan siitä, millainen ajattelutapa on pätevällä tietokantojen suunnittelijalla.