Relaatiotietokannan suunnittelu riippuvuuksiin perustuen

Eroon toistuvasta tiedosta

Relaatiotietokantojen suunnittelun pääperiaatteena on tiedon toiston välttäminen. Kukin tieto pitäisi tallentaa vain kertaalleen. Tiedon toistumisesta aiheutuvia ongelmia ovat

• toistuva tieto vie tarpeettomasti tilaa
• ylläpito muodostuu hankalaksi ja
• ylläpito-operaatioilla voi olla odottamattomia sivuvaikutuksia.

Tarkastellaan pientä esimerkkitaulua

Tässä taulussa osastojen 3 ja 4 nimi sekä sijaintipaikka on tallennettu kahteen kertaan. Jos osasto3 muuttaisi Helsingistä Espooseen, pitäisi muutos tehdä kahdelle taulun riville eli ylläpito muodostuu työläämmäksi. Tietenkin näin pienessä taulussa toiston tuomat ongelmat ovat varsin vähäisiä, mutta suuremmissa ne vastaavasti moninkertaistuvat. Hankalampi ongelma on se, että jos työntekijä O.Itä päättäisi lähteä yrityksestä ja hänen rivinsä poistettaisiin, poistuisi samalla tieto siitä, että tuotanto-osastokin on olemassa. Uutta osastoa ei voida myöskään lisätä, ellei sinne heti sijoiteta jotain työntekijää.

Rakenteeltaan parempaan tietokantaan päästään suunnittelemalla taulurakenne paremmin tilanteeseen sopivaksi. Yllä olevan esimerkin tapauksessa toistosta päästään eroon seuraavilla tauluilla

Nyt osastoja voi lisätä ilman, että niihin sijoitetaan työntekijää. Työntekijän poisto ei hävitä osastoa missään tilanteessa ja osaston muuttaessa riittää tehdä muutos yhdelle riville.

Tiedon toiston välttäminen on hyvä asia tietokannan tilantarpeen ja ylläpidon kannalta. Kyselyjen tehokkuutta toisteinen tieto voi kuitenkin parantaa.

Taulurakenteiden suunnittelu

Tällä kurssilla käsitellään vain taulurakenteiden suunnittelua ja sitäkin johdantoluonteisesti siten, että vain pieni mutta keskeinen osa relaatiomalliin liittyvästä suunnitteluteoriasta tulee katetuksi.

Relaatiotietokantojen suunnitteluteoriassa relaatiokaavion hyvyys määritellään tietojen välisiin riippuvuuksiin perustuen. Riippuvuustyyppejä on määritelty useita, mutta tärkeimpiä niistä ovat funktionaaliset riippuvuudet (functional dependency).

Funktionaaliset riippuvuudet

Funktionaalisella riippuvuudella tarkoitetaan sitä, että sarakkeen arvon avulla pystytään selvittämään yksikäsitteinen arvo sarakkeesta funtionaalisesti riippuvalle sarakkeelle. Esimerkiksi henkilötunnuksen perusteella saadaan selville yksikäsitteinen nimi, syntymäaika, osoite, yms. Sama muodollisemmin:

Riippuvuudessa A->B kutsutaan attribuuttia A määrääjäksi. A voi olla yksittäinen attribuutti tai kokoelma attribuutteja. Kun riippuvuuksia määritellään, pyritään määrääjiksi löytämään minimaaliset attribuuttiyhdistelmät. Määrääjä on minimaalinen, jos siinä ei ole turhia attribuutteja. Esimerkiksi riippuvuudessa  Ax->B attribuutti x on turha, mikäli  A->B. Relaatiokaavioon liittyvät riippuvuudet voidaan aina esittää siten, että kussakin riippuvuudessa oikealla puolella, siis riippuvana, on vain yksi attribuutti.

Avaimen määrääminen

Relaation avain määritellään riippuvuuksien avulla seuraavasti

Funtionaalisten riippuvuuksien perusteella voidaan täten selvittää, mitkä sarakkeet muodostavat relaation avaimen. Avaimen saa selville seuraavalla algoritmilla:

Ota avainehdokkaaksi K kaikki attribuutit, jotka eivät esiinny riippuvuuksissa oikealla puolella eivätkä ole siis riippuvia muista. Kunnes K määrää funktionaalisesti kaikki kaavion attribuutit, yhdistä K:hon määrääjä sellaisesta riippuvuudesta, jossa määräytyvä attribuutti ei kuulu K:hon. Kun attribuuttijoukkoa K:ta ei enää tarvitse täydentää, on avain löytynyt.

Yllä olevassa voidaan riippuvuuksia soveltaa eri järjestyksissä ja näin saadaan vaihtoehtoisia avaimia.

Riippuvuuksien päättely

Annetusta joukosta riippuvuuksia voidaan päätellä uusia riippuvuuksia. Päättely perustuu kolmeen päättelysääntöön, ns. Armstrongin aksiomiin

Mille tahansa riippuvuusjoukolle voidaan määritellä minimaalinen joukko riippuvuuksia, josta on pääteltävissä samat riippuvuudet kuin annetusta riippuvuusjoukosta. Kartoitettaessa relaatiokaavioon liittyviä riippuvuuksia on tavoitteena löytää minimaalinen riippuvuusjoukko. Minimaalisessa riippuvuusjoukossa ei ole riippuvuuksia, jotka voidaan päätellä muista riippuvuuksista. On olemassa algoritmeja, jotka laskevat annetulle riippuvuusjoukolle minimaalisen riippuvuusjoukon.

Riippuvuudet heijastavat tietokannan kohdealueella vallitsevia lainalaisuuksia. Niitä ei voi määrätä tarkastelemalla vain tiettyä kaavion ilmentymää vaan niitä määrättäessä pitää ajatella tilannetta missä tahansa kaavion ilmentymässä.

Tarkastellaan esimerkkikaaviota Ostos ja siihen liittyviä mahdollisia riippuvuuksia. Alla olevassa taulukossa punertavalla värillä merkityt vaihtoehdot hylätään. Jäljelle jäävien riippuvuuksien joukko on minimaalinen.

Boyce-Codd normaalimuoto

Tietojen yhteenkuuluvuus voidaan määritellä riippuvuuksien avulla. Relaatiomalliin liittyvässä suunnitteluteoriassa on määritelty useita ns. normaalimuotoja, joihin kuhunkin liittyy erilaiset säännöt. Tällä kurssilla tarkastellaan normaalimuodoista vain Boyce-Codd normaalimuotoa. Normaalimuoto määritellään seuraavasti:

Kun tietokannan relaatiot ovat kaikki Boyce-Codd normaalimuodossa, ei tietokannassa ole lainkaan toisteista tietoa. Boyce-Codd normaalimuoto ei kuitenkaan ole aina saavutettavissa. Hieman lievemmässä kolmannessa normaalimuodossa sallitaan Boyce-Codd normaalimuodossa sallittujen riippuvuuksien lisäksi sellaiset riippuvuudet, joissa riippuva attribuutti kuuluu johonkin avaimeen. Kaavion jako tällaisiin osakaavioihin on aina saavutettavissa. Esimerkiksi kaavio

Osoite(Postinumero,Kaupunki,Katuosoite), jossa riippuvuudet ovat

Postinumero->Kaupunki ja Kaupunki, Katuosoite -> Postinumero

ei ole Boyce-Codd -normaalimuodossa sillä avaimet tässä kaaviossa ovat {Postinumero,Katuosoite} ja {Kaupunki,Katuosoite} eikä Postinumero sisällä näistä kumpaakaan. Sen sijaan riippuvuuden Postinumero->Kaupunki riippuva attribuutti Kaupunki kuuluu avaimeen {Kaupunki,Katuosoite}, joten relaatiokaavio on kolmannessa normaalimuodossa.

Boyce-Codd normaalimuodon tarkistamiseksi on siis ensiksi määriteltävä relaation avaimet ja sen jälkeen tarkistettava rikkooko jokin relaatiokaavioon liittyvä riippuvuus Boyce-Codd normaalimuodon ehdon.

Kaavion Ostos riippuvuuksissa oikealla puolella eivät esiinny tuotenumero , ostajan_nimi eikä ostopäivä . Siispä K on aluksi { tuotenumero,ostajan_nimi ja ostopäivä }. K:sta riippuvien attribuuttien joukko sisältää refleksiivisyyssäännön mukaan attribuutit itsensä sekä transitiivisuuden perusteella kaikki sellaiset attribuutit, jotka riippuvat näistä. K:sta riippuvia ovat siis tuotenumerosta riippuvat tuotenimi ja listahinta sekä ostajan_nimestä riippuva alennusprosentti . Listahinta ja alennusprosentti puolestaan määräävät yhdessä maksuhinnan eli kaikki relaatiokaavion attribuutit kuuluvat K:n perusteella määräytyviin attribuutteihin. K on siis tämän kaavion ainoa avain, koska siihen ei tarvinnut lisätä mitään.

Yksikään kaavioon Ostos liittyvistä riippuvuuksista ei sisällä avainta K, joten kaavio ei ole Boyce-Codd normaalimuodossa. Attribuutit on siis uudelleenjärjesteltävä sellaisiksi relaatioiksi, joissa Boyce-Codd normaalimuodon vaatimukset ovat voimassa. Seuraavat relaatiot täyttävät ehdon

1. Tuote( tuotenumero , tuotenimi, listahinta)    
2. Ostaja( ostajan_nimi , alennusprosentti)
3. Alennus( listahinta, alennusprosentti ,maksuhinta)
4. Ostos( tuotenumero,ostajan_nimi,ostopäivä )

Näistä kolmas (Alennus) on laskettavissa oleva funktio eikä sitä ole tarpeen tallentaa tietokantaan.

Attribuuttien uudelleenryhmitys Boyce-Codd normaalimuodossa oleviksi kaavioiksi

Boyce-Codd normaalimuodossa oleva tietokantakaavio voidaan määrätä minimaalisen riippuvuusjoukon perusteella seuraavasti:

1. Ryhmittele riippuvuudet ryhmiin yhteisen määrääjän perusteella
2. Muodosta kutakin ryhmää kohden relaatiokaavio, johon otat kaikki ryhmän riippuvuuksissa esiintyvät attribuutit
3. Jos relaatiokaavion avain ei sisälly muodostettuihin relaatioihin, muodosta siihen kuuluvista attribuuteista oma relaatio.
4. Karsi mahdolliset saman asian toisteiset esitykset.
5. Anna muodostuneille relaatiokaavioille nimet. Jos niille löytyy nimet ja luonnollinen merkitys jakoa voi pitää onnistuneena.

Kaavion Ostos uudelleenjärjestelyn tuloksena syntyneistä kaavioista a, b ja c määräytyvät kohdan 2 perusteella ja d kohdan 3 perusteella. Niille löytyi myös luonnolliset nimet.

Esimerkki:

Aiemmin oli esillä ongelmallinen taulu Työ

Tähän tauluun liittyen voidaan löytää riippuvuudet

ttNro ->  nimi,

ttNro -> s_aika

ttNro -> oNro

oNro -> oNimi

oNro -> osSijainti

Riippuvuuksien perusteella taulun avain on sarake ttNro . Taulu ei ole Boyce-Codd normaalimuodossa. Siinä esiintyy siis toistoa, kuten aiemmin todettiin. Kun riippuvuudet ryhmitellään yhteisen määrääjän perusteella, saadaan ryhmät:

ttNro ->  nimi,

ttNro -> s_aika

ttNro -> oNro

ja

oNro -> oNimi

oNro -> osSijainti.

Näiden perusteella määräytyvät kaaviot

kaavio_1 (ttNro,  nimi, s_aika, oNro) ja

kaavio_2 (oNro, oNimi, osSijainti).

Kun kaavioille annetaan uudet nimet, päädytään aiemmin esillä olleisiin tauluihin

Työntekijä (ttNro,  nimi, s_aika, oNro) ja

Osasto(oNro, oNimi, osSijainti).

Esimerkki:

Opintosuoritusote sisältää seuraavat tiedot

• Opiskelijan_henkilötunnus
• Opiskelijanumero
• OpiskelijanNimi
• OpiskelijanOsoite
• OpiskelijanKirjoilletuloPvm
• PääOpinto-oikeudenTiedekunta
• PääOpinto-oikeudenKoulutusohjelma
• PääOpinto-oikeudenPääaine
• SuorituksenKoodi 
• Suorituspäivä
• Arvosana
• SuorituksenLaajuus
• KurssinNimi
• SuorituksenLaitos

Oletetaan, että kaikki opiskelijoiden suoritusotteisiin tarvittavat tiedot talletettaisiin yhteen relaatioon (ns. universaalirelaatio-oletus). Määritellään tässä relaatiossa voimassa olevat funktionaaliset riippuvuudet

(1) Myös riippuvuudet joissa henkilötunnus määrää näissä riippuvuuksissa oikealla olevan attribuutin ovat voimassa. Tässä on valittu nämä keskeisimmiksi joten henkilötunnukseen perustuvat riippuvuudet jäävät pääteltäviksi

Kun punaisella merkityt karsitaan, jää jäljelle minimaalinen joukko riippuvuuksia. Näiden perusteella saadaan relaatiolle avaimet {Opiskelijanumero, SuorituksenKoodi} ja {Opiskelijan_henkilötunnus, SuorituksenKoodi}.

Relaatio ei ole Boyce-Codd normaalimuodossa, koska esimerkiksi riippuvuudessa 'SuorituksenKoodi  -> SuorituksenLaitos' määrääjä ei sisällä kumpaakaan avaimista.

Tehdään riippuvuuksien ryhmittely yhteisen määrääjän perustella ja muodostetaan relaatiokaaviot ryhmiin kuuluvista attribuuteista. Tuloksena saadaan kaaviot

Saatuja kaavioita tarkastelemalla havaitaan, että Kaavio 2 on projektio Kaavioista 1, joten se voidaan toisteisena jättää pois. Sarakkeet voidaan myös nimetä uudelleen. Seuraavassa taulukossa taulut on nimetty ja muutama sarake uudelleennimetty. Taulukkoon on merkitty myös kaavioiden pääavaimet. Nämä kaaviot ovat kaikki Boyce-Codd normaalimuodossa.