8. Tietokantojen teoria

Relaatiomalli

SQL-tietokannat perustuvat relaatiomalliin, jonka teoreettinen pohja syntyi 1970-luvulla. Vuonna 1970 E. F. Codd esitteli artikkelissaan A relational model of data for large shared data banks sekä idean relaatiomallia käyttävästä tietokannasta että yleiskäyttöisestä tietokantakyselykielestä.

Verrattuna aiempiin tietokantoihin relaatiomallin vahvuutena oli sen yksinkertaisuus: saman selkeän mallin avulla pystyy esittämään luontevasti monenlaista tietoa sekä toteuttamaan monipuolisia kyselyitä.

Mutta mitä relaatio tarkoittaa tarkalleen? Yksi yksinkertainen esimerkki relaatiosta on binäärirelaatio \(<\) eli “pienempi kuin”. Tämä relaatio määrittelee pareista muodostuvan joukon, jonka jokaisessa parissa \((a,b)\) pätee ehto \(a<b\). Kun tarkastelu rajataan positiivisiin kokonaislukuihin, tämä joukko näyttää seuraavalta:

Binäärirelaatio on kaksipaikkainen, eli jokainen relaation alkio on pari. Yleisemmin voidaan määritellä \(k\)-paikkainen relaatio, jossa jokainen relaation alkio on monikko muotoa \((x_1,x_2,\dots,x_k)\).

Relaatiotietokannassa relaatio esittää kokoelman tietoa, jolla on tietty rakenne. Esimerkiksi seuraava relaatio sisältää tietoa tuotteista:

Tämä relaatio on kolmipaikkainen ja sen attribuutit ovat:

• \(id\): tuotteen id-numero
• \(name\): tuotteen nimi
• \(price\): tuotteen hinta

Esimerkiksi monikossa \((1,retiisi,7)\) attribuutti \(id\) on \(1\), attribuutti \(name\) on \(retiisi\) ja attribuutti \(price\) on \(7\).

Yllä oleva relaatio vastaa tietokantataulua Products, jossa on tietoa tuotteista:

Relaatio on siis matemaattinen tapa kuvata tietokantataulun sisältö joukkona. Relaation jokainen monikko vastaa yhtä taulun riviä, ja monikon attribuuttien määrä on sama kuin taulun sarakkeiden määrä.

Relaatio-operaatiot

Relaatio-operaatioiden avulla olemassa olevista relaatioista voidaan muodostaa uusia relaatioita. Tämä vastaa SQL-kyselyä, jossa taulusta tai tauluista muodostetaan tulostaulu. Kolme keskeistä relaatio-operaatiota ovat projektio, restriktio ja liitos.

Projektio

Projektio (projection) \(\Pi\) muodostaa relaation, joka sisältää alkuperäisen relaation tietyt attribuutit. Esimerkkejä:

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

Projektio vastaa SQL-kyselyä, joka hakee tiettyjä sarakkeita taulusta. Esimerkiksi projektio \(\Pi_{name}(P)\) vastaa SQL-kyselyä SELECT name FROM Products.

Restriktio

Restriktio (restriction) \(\sigma\) muodostaa relaation, joka sisältää alkuperäisen relaation tietyt ehdot täyttävät monikot. Esimerkkejä:

Restriktio vastaa SQL-kyselyä, jossa rivit valitaan WHERE-osassa. Esimerkiksi restriktio \(\sigma_{price = 4}(P)\) vastaa SQL-kyselyä SELECT * FROM Products WHERE price = 4.

Yhdistämällä projektio ja restriktio saadaan vastine esimerkiksi SQL-kyselylle SELECT name FROM Products WHERE price <= 5:

Liitos

Liitos (join) \(\bowtie\) muodostaa relaation, jossa on yhdistelmiä kahden relaation monikoista. Liitokseen valitaan mukaan sellaiset yhdistelmät, joissa attribuuttien arvot ovat samat niissä attribuuteissa, jotka esiintyvät molemmissa alkuperäisissä relaatioissa. Yhteiset attribuutit esitetään vain kerran liitoksessa.

Tarkastellaan esimerkkinä seuraavia relaatioita:

Relaatio \(E\) esittää työntekijät ja muodostuu seuraavista attribuuteista:

• \(eid\): työntekijän id-numero
• \(ename\): työntekijän nimi
• \(cid\): yrityksen id-numero

Relaatio \(C\) esittää yritykset ja muodostuu seuraavista attribuuteista:

• \(cid\): yrityksen id-numero
• \(cname\): yrityksen nimi

Kun muodostetaan liitos \({E\ \bowtie\ C }\), etsitään monikoiden yhdistelmät, joissa yhteinen attribuutti \(cid\) on sama. Nämä yhdistelmät ovat:

• \((1,Maija,1)\) ja \((1,Google)\)
• \((2,Liisa,1)\) ja \((1,Google)\)
• \((3,Kaaleppi,3)\) ja \((3,Facebook)\)

Liitokseen kootaan attribuutit \(eid\), \(ename\), \(cid\) ja \(cname\) seuraavasti:

Voisimme vielä käyttää liitoksen jälkeen projektiota seuraavasti:

Liitos vastaa tietynlaista kahden taulun SQL-kyselyä. Esimerkiksi yllä olevat relaatiot vastaavat seuraavia tauluja Employees ja Companies:

Nyt operaatiota \(\Pi_{ename,cname}({E\ \bowtie\ C})\) vastaa seuraava kysely:

SELECT Employees.name, Companies.name
FROM Employees, Companies
WHERE Employees.company_id = Companies.id;

Teoria vs. käytäntö

SQL-tietokannan taulut eivät vastaa täydellisesti relaatiomallin relaatioita, vaan tauluissa ja relaatioissa on eroja.

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

sqlite> CREATE TABLE Test (x INTEGER);
sqlite> INSERT INTO Test VALUES (1);
sqlite> INSERT INTO Test VALUES (1);
sqlite> INSERT INTO Test VALUES (1);
sqlite> SELECT * FROM Test;
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 monikon jokaisella attribuutilla tulee olla arvo mutta SQL-tietokannan taulussa sarakkeessa voi olla NULL eli arvo puuttuu.

Myös SQL-kyselyissä ja relaatio-operaatioissa on eroja. Kuten näimme aiemmin, projektio \(\Pi_{price}(P)\) sisältää jokaisen eri hinnan vain kerran, kun taas kyselyn SELECT price FROM Products 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_{price}(P)\) vastaa siis kysely SELECT DISTINCT price FROM Products.

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 lyhemmin 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\), \(name\) ja \(price\):

Tässä relaatiossa yliavaimia ovat ainakin \(id\), \((id,name)\), \((id,price)\) ja \((id,name,price)\). 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 \(price\) ei voi olla yliavain, koska monella tuotteella voi olla sama hinta. Attribuutti \(name\) voi olla yliavain siinä tapauksessa, että jokaisella tuotteella on varmasti eri nimi. Yhdistelmä \((name,price)\) 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 \((name,price)\) 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 \(postalcode\) ja \(city\), siinä on funktionaalinen riippuvuus \(postalcode \to city\) olettaen, että postinumerosta voidaan päätellä kaupunki. Toisin sanoen ei voi olla kahta monikkoa, joissa olisi sama postinumero mutta eri kaupunki. Esimerkiksi jos postinumero on 00560, voidaan päätellä kaupungin olevan Helsinki.

Mitä postinumerosta voi päätellä?

Attribuutit \(A\) muodostavat yliavaimen tarkalleen silloin, kun \(A \to B\) pätee mille tahansa attribuuteille \(B\). Tämä tarkoittaa, että missä tahansa relaation monikossa yliavaimen attribuutit yksilöivät, mistä monikosta on kyse. Esimerkiksi kun relaation attribuutit ovat \(id\), \(name\) ja \(price\), attribuutti \(id\) on yliavain, koska pätee \(id \to id\), \(id \to name\) ja \(id \to price\).

Normaalimuodot

Normaalimuoto (normal form) on tietokannan relaatioon (tauluun) liittyvä vaatimus, jonka tavoitteena on edistää tiedon eheyttä ja helpottaa tietokannan käyttämistä. Normaalimuodoissa on teoreettisessa muodossa samantapaisia 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:

Tämä relaatio ilmaisee yritysten toimistojen sijainnit. Ongelmana ensimmäisen normaalimuodon kannalta on, että relaation toinen attribuutti voi sisältää useita arvoja. Esimerkiksi monikossa \((Google, (London, Paris, Stockholm))\) toinen attribuutti sisältää kolme arvoa.

Ongelma voidaan korjata esittämällä tiedot toisella tavalla:

Nyt relaatio toteuttaa ensimmäisen normaalimuodon, koska jokainen attribuutti sisältää tarkalleen yhden arvon.

Ensimmäinen normaalimuoto liittyy tietokannan suunnittelussa siihen periaatteeseen, että taulujen sarakkeissa tulee olla atomista tietoa.

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 \((name,city)\) on avain, koska nämä attribuutit yksilöivät jokaisen monikon. Kuitenkin relaatiossa on funktionaalinen riippuvuus \(city \to country\), koska toimiston kaupungista voidaan päätellä maa.

Relaatio ei toteuta toista normaalimuotoa, koska siinä on avaimen \((name,city)\) ulkopuolinen attribuutti \(country\), joka riippuu avaimen osasta \(city\).

Voimme toteuttaa toisen normaalimuodon jakamalla relaation kahdeksi relaatioksi. Ensimmäinen relaatio sisältää yrityksen nimen ja toimiston kaupungin:

Toinen relaatio puolestaan kertoo, missä maissa kaupungit sijaitsevat:

Toisen normaalimuodon merkitys on käytännössä pieni, koska tietokantatauluissa käytetään yleensä avaimina id-numeroita eikä avain muodostu useasta sarakkeesta. Tämän takia toinen normaalimuoto yleensä toteutuu automaattisesti.

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 avaimena on attribuutti \(id\). Relaatio ei toteuta kolmatta normaalimuotoa, koska \(postalcode\) ja \(city\) ovat avaimen ulkopuolisia attribuutteja, mutta pätee funktionaalinen riippuvuus \(postalcode \to city\). Tässä oletuksena on taas, että postinumerosta voidaan päätellä kaupunki.

Tässäkin tapauksessa voimme jakaa relaation kahdeksi relaatioksi, minkä jälkeen kolmas normaalimuoto toteutuu. Ensimmäinen relaatio sisältää vain postinumerot muttei kaupunkeja:

Toinen relaatio puolestaan yhdistää postinumerot ja kaupungit:

Kolmas normaalimuoto liittyy tietokannan suunnittelussa siihen periaatteeseen, että tauluissa ei saa olla toisteista tietoa.

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.

Useissa normaalimuodoissa on 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.