Tietokannan suunnittelussa käytetään erilaisia teorioita ja algoritmeja. Yksinkertaisen tietokantarakenteen voi suunnitella intuitiivisestikin, mutta tehokkaan rakenteen aikaansaaminen vaatii enemmän kuin hyvää pelisilmää. Monimutkaiset tietosisältöjen riippuvuudet toisistaan asettavat tietokannan suunnittelun aivan uuteen valoon, sillä rakenteen ja siihen liittyvien avainten määräytyminen ei ole välttämättä triviaalia. Tietokannoista puhuttaessa ei voi olla törmäämättä relaation käsitteeseen. Relaatioiden lisäksi käsitteistöön sisältyvät attribuutit, jotka ovat olennainen osa relaatiokaavioita. Esimerkiksi relaatiokaavio
enrolled(student, course, year, period, group, teacher)voisi kuvata jotakin enrolled-nimistä tietokantataulua, jonka kuusi attribuuttia vastaisivat taulun sarakkeita. Tietokannan suunnittelu alkaa joskus edellä kuvatuilla kaavioilla ja etenee kohti jotain normaalimuotoa, jolla tietokantasuunnitelma pyritään saamaan tehokkaaksi ja toimivaksi. Relaatiokaavioissa on tyypillisesti funktionaalisia riippuvuuksia eli tiettyjen attribuuttien tai niiden yhdistelmien eli attribuuttijoukkojen arvot määräävät muita attribuutteja tai niiden joukkoja. Funktionaalista riippuvuutta R : X → Y merkitään
r ⊨ X → Ymissä attribuutit X määräävät attribuutit Y relaatiossa r. Toisin sanoen attribuutit Y riippuvat funktionaalisesti attribuuteista X relaatiossa r. Tällaisia funktionaalisia riippuvuuksia voi olla voimassa useita samanaikaisesti, jolloin ne muodostavat riippuvuusjoukon. Esimerkin relaatiokaaviossa voi olla seuraavanlainen riippuvuusjoukko:
F = {course year → period teacher, teacher year period → course, student course year → group}missä esimerkiksi attribuutit course year määräävät attribuutit period ja teacher. Riippuvuusjoukkoa ja siitä eri algoritmein johdettuja osajoukkoja tarvitaan tietokannan suunnitteluprosessissa esimerkiksi avaimia määrätessä. Attribuuttijoukon X ⊆ R sulkeuma X+ relaatiokaavion R riippuvuusjoukon F suhteen on attribuuttijoukko
X+ = {A ∈ R | F ⊨ X → A}.Attribuuttijoukon sulkeuma on helppo laskea yksinkertaisella algoritmilla, joka tässä on esitetty pseudokoodilla:
Y ← X
G ← F
while Z ⊆ Y any Z → V ∈ G do begin
Y ← Y ∪ V
G ← G ∖ {Z → V}
end.Algoritmin päättyessä Y = X+. Olen sovittanut algoritmin PHP-ohjelmointikielelle, jolla kyseinen algoritmi voidaan toteuttaa monellakin tavalla. Oheinen closure()-funktio laskee attribuuttijoukon X sulkeuman riippuvuusjoukon F suhteen:
function closure(array $X, array $F) {
$Y = $X;
$G = $F;
$Z = array();
while (!empty($G) && empty($Z)) {
foreach ($G as $i => $V) {
$Z = array_diff($V[0], $Y);
if (empty($Z)) {
$Y = array_merge($Y, $V[1]);
unset($G[$i]);
}
}
}
return array_unique($Y);
}Funktio saa parametrikseen attribuuttijoukon taulukkona samoin kuin riippuvuusjoukonkin. Riippuvuudet ovat muotoa X → Y eli attribuutit X määräävät attribuutit Y. Tällainen joukko annetaan funktiolle taulukkona, jossa kukin riippuvuus muodostaa yhden taulukon elementin. Riippuvuuden X- ja Y-attribuutit välitetään niin ikään taulukkona, jolloin lopullinen riippuvuusjoukko on useiden sisäkkäisten taulukoiden muodostama arvojoukko. Oheinen esimerkki valaisee funktion argumenttien välityksen:
$X = array('year', 'course');
$F = array(
array(
array('course', 'year'), array('period', 'teacher')
),
array(
array('teacher', 'year', 'period'), array('course')
),
array(
array('student', 'course', 'year'), array('group')
)
);Esimerkissä on edellä mainitun riippuvuusjoukon F riippuvuudet sekä attribuuttijoukko X, jonka sulkeuma halutaan laskea. Funktio laskee sulkeuman riippuvuusjoukon F suhteen kutsumalla sitä alustetuilla taulukkomuuttujilla:
print_r(closure($X, $F));Funktio tulostaa sulkeuman taulukkona. Kukin taulukon elementti on sulkeumaan sisältyvä attribuutti.
Array
(
[0] => year
[1] => course
[2] => period
[3] => teacher
)Esimerkkisulkeuma (year course)+ on siis attribuuttijoukko {year course period teacher}. Sulkeuman laskeva algoritmi on kätevä apuväline, kun halutaan esimerkiksi testata relaatiokaavioiden normaalimuotoja, sillä testaaminen perustuu avainten määräämiseen kaavion riippuvuusjoukon F suhteen. Avainten määräämiseen puolestaan tarvitaan attribuuttijoukon sulkeumaa, jota voidaan käyttää lisäksi riippuvuusjoukon kanonisen peitteen laskemisessa.