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.

Merkintä \(\mid S \mid\) tarkoittaa joukon \(S\) alkioiden määrää. Äskeisessä esimerkissä \(\mid A \mid=5\) ja \(\mid B \mid =3\).

Merkintä \(x \in S\) tarkoittaa, että alkio \(x\) kuuluu joukkoon \(S\).

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.

Merkintä \(A \subset B\) tarkoittaa, että joukko \(A\) on joukon \(B\) osajoukko.

Osajoukko on aito (proper), jos siinä ei ole kaikkia joukon alkioita.

Kun joukossa on \(n\) alkiota, siitä voidaan muodostaa \(2^n\) osajoukkoa. Esimerkiksi joukossa \(\{1,2,3\}\) on \(3\) alkiota, joten osajoukkoja on \(2^3=8\).

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

Karteesisen tulon alkioiden määrä on \(\mid S_1 \mid \cdot \mid S_2 \mid \dots \mid S_k \mid\). Esimerkiksi kun \(\mid A \mid = 3\), \(\mid B \mid = 1\) ja \(\mid C \mid = 2\), karteesinen tulo \(A \times B \times C\) muodostuu \(3 \cdot 1 \cdot 2 = 6\) alkiosta.

Relaatio

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

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

Karteesisella tulolla \(S_1 \times S_2 \times \dots \times S_k\) on kaikkiaan \(2^{\mid S_1 \mid \cdot \mid S_2 \mid \dots \mid S_k \mid}\) mahdollista relaatiota.

Taulu relaationa

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 eli kunkin attribuutin tyypin.

Esimerkki

Tarkastellaan esimerkkinä taulua Tuotteet, jossa on tietoa tuotteista:

Tämä taulu vastaa relaatiota

jonka jokainen monikko muodostuu kolmesta attribuutista id, nimi ja hinta.

Tässä tapauksessa relaation taustalla on karteesinen tulo \(S_1 \times S_2 \times S_3\). Joukot \(S_1,S_2,S_3\) määrittelevät attribuuttien tyypit eli jokainen joukko sisältää kaikki arvot, joita vastaavassa attribuutissa voi olla.

Esimerkiksi attribuutti id on positiivinen kokonaisluku, joten \(S_1\) voisi olla \(\{1,2,3,\dots\}\) eli ääretön joukko, joka sisältää kaikki positiiviset kokonaisluvut. Toinen mahdollisuus on, että id-numerolla on yläraja, kuten yleensä käytännön tietokannoissa. Esimerkiksi jos id-numero on 64-bittinen kokonaisluku, \(S_1\) voisi olla \(\{1,2,3,\dots,2^{64}-1\}\).

Teoria vs. käytäntö

SQL-tietokannat perustuvat relaatiomalliin, mutta ne eivät kuitenkaan täysin noudata sitä.

Yksi ero on, että relaatiossa jokainen monikko on erilainen (koska relaatio on joukko), mutta SQL-taulussa ei ole tätä rajoitusta. 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-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-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 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. Tämän takia projektiossa \(\Pi_{hinta}(T)\) on vain neljä monikkoa, koska kahdella tuotteella on sama hinta.

Restriktio

Restriktio \(\sigma\) muodostaa relaation, jossa on 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.

Lisäksi 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 on ORDER BY, jolloin tulostaulun rivit ovat halutussa järjestyksessä. Relaatio-operaatioilla ei ole mahdollista toteuttaa tällaista hakua.

Avaimet ja riippuvuudet

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. Tämä tarkoittaa, että jos 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.

Koska attribuutti id yksilöi jokaisen monikon, se on yliavain. Myös yhdistelmät (id, nimi), (id, hinta) ja (id, nimi, hinta) ovat yliavaimia, koska niiden osana on attribuutti id. Kuitenkin näistä yliavaimista vain id on avain, koska muut yliavaimet eivät ole minimaalisia.

Attribuutti hinta ei selkeästi ole yliavain, koska monella tuotteella voi olla sama hinta. Attribuutti nimi on yliavain siinä tapauksessa, että usealla tuotteella ei voi olla samaa nimeä. 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 on luonnollinen avain, kun taas id on sijaisavain.

Tietokantojen teoriassa näkee usein käytettävän luonnollisia avaimia, mutta käytännössä on hyvin tavallista käyttää id-numeroa tai vastaavaa sijaisavainta. Tässä on etuna, että id-numero on kompakti tieto, joka kelpaa varmasti avaimeksi. Jos valittaisiin luonnollinen avain, siihen kuuluisi ehkä monia attribuutteja ja pitäisi pohtia, riittävätkö attribuutit varmasti yksilöimään monikon kaikissa tapauksissa.

Funktionaalinen riippuvuus

Funktionaalinen riippuvuus (functional dependency) \(A \to B\) tarkoittaa, että attribuutit \(A\) määräävät 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. 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ässä tapauksessa koska \(A\) on yliavain, relaatiossa ei voi olla kahta monikkoa, jossa attribuutit \(A\) ovat samat.

Normaalimuodot

Normaalimuodot ovat tietokannan suunnitteluun liittyviä vaatimuksia, joiden tavoitteena on edistää tiedon eheyttä ja helpottaa tietokannan käyttämistä.

Ensimmäinen normaalimuoto vaatii, että tietokannassa on käytössä relaatiomalli. SQL:ssä määritelty taulu toteuttaa automaattisesti ensimmäisen normaalimuodon.

Toinen ja kolmas normaalimuoto liittyvät attribuuttien riippuvuuksiin. Näiden pohjalta on edelleen kehitetty Boyce–Codd-normaalimuoto, johon tutustumme seuraavaksi.

Boyce–Codd-normaalimuoto

Relaatio toteuttaa Boyce–Codd-normaalimuodon, jos jokaisessa siinä olevassa funktionaalisessa riippuvuudessa \(X \to Y\) pätee, että \(Y \subset X\) tai \(X\) on yliavain.

Ideana on varmistaa, että relaatiossa ei ole riippuvuuksia, jotka eivät liittyisi relaation avaimiin. Jos tällaisia riippuvuuksia on olemassa, ne tulisi esittää erillisessä relaatiossa.

Jos \(Y \subset X\), niin attribuutit \(Y\) ovat osa attribuutteja \(X\). Tällainen riippuvuus on voimassa aina, eli se ei kerro mitään erityistä. Esimerkki tästä on riippuvuus (nimi, hinta) \(\to\) hinta.

Jos \(X\) on yliavain, niin riippuvuus \(X \to Y\) kuuluu asiaan, koska yliavain määrää kaikki attribuutit. Esimerkki tästä on riippuvuus id \(\to\) nimi.

Jos relaatio toteuttaa Boyce–Codd-normaalimuodon, niin se toteuttaa myös ensimmäisen, toisen ja kolmannen normaalimuodon.

Esimerkki

Tarkastellaan esimerkkinä seuraavaa taulua Suoritukset, jossa on kurssisuorituksia:

Oletetaan, että jokaisella kurssilla on kiinteä opintopisteiden määrä, jolloin taulussa on riippuvuus kurssi_id \(\to\) op. Tämä on vastoin Boyce–Codd-normaalimuotoa, koska sarake op ei ole osa saraketta kurssi_id eikä sarake kurssi_id ole yliavain.

Asia voidaan korjata tallentamalla kurssien opintopisteet erilliseen tauluun:

Tämän muutoksen jälkeen molemmat taulut noudattavat Boyce–Codd-normaalimuotoa.

Teoria vs. käytäntö

Normaalimuotojen merkityksenä on, että ne antavat matemaattisen näkökulman tietokantojen suunnitteluun. Esimerkiksi jos tietokanta ei toteuta Boyce–Codd-normaalimuotoa, tietokannan rakennetta voi luultavasti parantaa.

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.