English version of the materials are work in progress!

Expect bugs, typos, and other issues. The English version is expected to be completed during spring 2026.

Basics of Normalization

In sections 2 and 3, we learned ways to design a relational database according to "good practices". Correct use of the relational model offers protection and some assurances for the data in the database. For example, if we were to design a relation STUDENT(sid, birthdate), where the primary key is {sid}, it is impossible to even accidentally put the table in a state where the same student has two different birthdates:

sid birthdate
s1 1.2.1990
s1 2.3.2000

This situation is impossible from the relational model's perspective, because every row in the table must be distinguishable based on the primary key, and thus one could not add two rows with the same student ID to the table.

In section 4, we also learned that relational database management systems (RDBMS) automatically ensure the correctness of the database whenever data is added, modified, or deleted. For example, RDBMSs check data types, ensure uniqueness of rows according to the primary key, and also check that referential integrity of foreign keys is maintained.

However, the basic building blocks of the relational model are not always enough to guarantee logical consistency of data. Generally, if a table can be put into a state that is "nonsensical" from the domain's perspective, the fault often lies in the database structure. In this section, we get acquainted with normalization, i.e., how database structure design can protect data consistency and reduce redundancy.

Purpose of Normalization

Normalization has two main purposes:

  1. to fix database structures prone to data correctness errors, and
  2. to reduce data redundancy in an otherwise logically correctly designed structure.

In addition to this, normalization facilitates database usage as follows:

  • Normalized tables are simpler to understand and do not contain "useless" columns.
  • Normalized tables are easy to extend to cover new domain needs. AT best, extending does not require changes to the database structure.
  • Normalized tables are better protected against anomalies (i.e., data contradictions) resulting from insert, delete, and update operations.

Structures prone to data correctness errors refer to attribute names that poorly describe the domain; structures with abundant null values; and relation structures where attributes from multiple real-world entities have been unnecessarily combined.

Data redundancy refers to unnecessary repetition of the same values. Data repetition naturally increases storage requirements. Data repetition also leads more easily to anomalies in data correctness.

Esimerkki

Let's examine the following student database, which contains one table. The table keeps track of students, course completions, courses, and grades:

sid sname cid cname grade
s7111 Adam Adapter itka204 Databases 5
s7111 Adam Adapter itkp113 Object-Oriented Design 4
s7111 Adam Adapter tjta114 Information Management GOOD
s6800 Bertha Blade itka204 Databases 5
s6604 Cecilia Chirp tjta114 Information Management GOOD

With the current structure, adding, modifying, or deleting data can easily cause anomalies in the database. An anomaly means that the database information remains contradictory with itself or the domain after an operation targeting the database.

What kind of insert, update, and delete anomalies can occur in this database?

  • Suppose the following row is added to the table:

    sid sname cid cname grade
    s6800 Bertha Blade tjta114 Basics of Information Management 5

    The name of course tjta114 becomes contradictory, as after the insertion the course name can be "Information Management" or "Basics of Information Management".

    This is an insert anomaly.

  • Suppose the following row is deleted from the table:

    sid sname cid cname grade
    s7111 Adam Adapter itkp113 Object-Oriented Design 4

    Now Adam Adapter's completion of the Object-Oriented Design course was removed, but now information about the existence of the Object-Oriented Design course was also removed from the entire database. Now if we wanted to find out what courses are taught using the database, the Object-Oriented Design course would not be found. This would be in conflict with the domain.

    This is a delete anomaly.

  • Suppose the course code of itka204 changes to itka2004 and the name changes to "Basics of Databases". Due to the change, the row

    sid sname cid cname grade
    s7111 Adam Adapter itka204 Databases 5

    is changed to form

    sid sname cid cname grade
    s7111 Adam Adapter itka2004 Basics of Databases 5

    However, it might have been forgotten that the table also has student s6800, whose row should also be updated! A contradiction arises in the database data: one student has a completion with the new course code and course name, but another student has a completion with the old, non-existent course code.

    We ended up with an update anomaly.

The current database is in dire need of normalization!

PS: Generally, if multiple different entities of the domain are modeled into the same table, anomalies are very possible.

Functional Dependency

As noticed, excessive data redundancy causes problems, and minimizing it is at the core of normalization. On the other hand, some redundancy is necessary: in the example above, the student ID and course code belonging to the primary key must be repeated in the table to guarantee row uniqueness ensured by the primary key. In other words, redundancy is error-prone, but not all data repetition can be avoided. How can we then distinguish "allowed" redundancy from redundancy that could be prone to anomalies?

Esimerkki

Let's return for a moment to the table STUDENT(sid, ssn, first_name, last_name, zip_code, city)Example in connection with the primary key in Chapter 3.1.

Let's invent some model data to make examining problems easier:

sid ssn first_name last_name zip_code city
s101 120196-111X Matthew Meikäläinen 33720 Tampere
s102 130280-112X Snow Zinc 40520 Jyväskylä
s103 130280-321Z Snow Zinc 40520 Jyväskylä
s104 121240-111A Donald Duck 60200 Seinäjoki
s105 241252-321X Dave Duck 33720 Tampere

Recall that a candidate key is an irreducible set of columns that uniquely identifies the entire row. In other words, based on the values of the candidate key columns, one can know exactly the values of all other columns of a row.

In the example of Chapter 3.1, we stated that:

  • {sid} is a candidate key, because based on the value of the sid column, the values of columns {ssn, first_name, last_name, zip_code, city} are uniquely known.
    • For example, if we know that a student's sid is s101, we know that the student's ssn is "120196-111X", first_name Matthew, last_name Meikäläinen, zip_code 33720 and city Tampere.
  • {ssn} is also a candidate key with the same reasoning: if we know a student's ssn, we uniquely know the corresponding values {sid, first_name, last_name, zip_code, city}.

Based on the table and the domain, we can make the following interesting observation: even though {zip_code} does not identify all columns of the table, it identifies the city column. If we know that the zip code of a student's address is 33720, we uniquely know that the city is Tampere.

In other words, {zip_code} is not a candidate key of the STUDENT table, but it still behaves similarly regarding the city column: the zip code does not identify all columns of the table, but it still identifies some columns. We also see in the table that there is redundancy in the city column.

Let's try making a table CITY(zip_code, city) and copying data from the STUDENT table:

zip_code city
33720 Tampere
40520 Jyväskylä
60200 Seinäjoki

In this relation {zip_code} is now a candidate key, as it identifies the city column, which is the only column outside the candidate key. It is also the only candidate key, i.e., also the primary key. Specifically, redundancy has been reduced: the same combination of zip code and city is not repeated unnecessarily.

From the example, we can conclude that normalization is closely related to how well the values of columns are identifiable based on the values of other columns. The matter is also partly related to definitions of candidate keys and primary keys, but on a slightly more general level. This brings us to functional dependencies.

Definition of Functional Dependency

The most important concept of normalization is functional dependency. Let's start with a precise definition in the words of the relational model:

Määritelmä

If a set of attributes X of relation R identifies another set of attributes Y of the same relation, it is said that a functional dependency holds in the relation

{X} -> {Y}

In a functional dependency, X is the determinant attribute set. It is said that "Attributes Y are functionally dependent on attributes X" or "Y is functionally dependent on X". More generally, one can say that "X determines Y".

In other words, for every tuple where attributes X have a certain value a, attributes Y have at most one value b.

In practice, functional dependency is very close to the definition of a candidate key. A candidate key is any (irreducible) attribute set of a relation that identifies all other attributes of the tuple. Functional dependency, on the other hand, is any attribute set of a relation that identifies any other set of relation attributes.

Let's take a couple more examples to clarify the concept:

Esimerkki

Let's return again to the table STUDENT(sid, ssn, first_name, last_name, zip_code, city) example in connection with the primary key in Chapter 3.1 and the model data invented in the previous example:

sid ssn first_name last_name zip_code city
s101 120196-111X Matthew Meikäläinen 33720 Tampere
s102 130280-112X Snow Zinc 40520 Jyväskylä
s103 130280-321Z Snow Zinc 40520 Jyväskylä
s104 121240-111A Donald Duck 60200 Seinäjoki
s105 241252-321X Dave Duck 33720 Tampere

In the previous example, we stated that {sid} is a candidate key. A candidate key identifies all other columns of the table: if the student's student ID is known, the values of the student's other columns are known uniquely. In other words, the following functional dependency holds:

{sid} -> {ssn, first_name, last_name, zip_code, city}

This does not tell anything new that is not known about the candidate key; it is just a different way to denote the matter.

Similarly, since {ssn} is a candidate key, the following functional dependency also holds:

{ssn} -> {sid, first_name, last_name, zip_code, city}

In the previous example, it was noticed that the column zip_code identifies the column city. If it is known that a student's zip_code is 33720, it is uniquely known that the student's city is always Tampere. So with functional dependency notation:

{zip_code} -> {city}

Esimerkki

Consider the following table PERSON(pid, name):

pid name
010160-ABCD Adam Adapter
020270-EFGH Bertha Blade
030380-IJKL Adam Adapter
040490-MNOP Cecilia Chirp

Even if we knew nothing about the domain, based on the table data we can deduce that the following functional dependency holds:

{pid} -> {name}

It holds because every value of the pid column corresponds to a unique name. For example, if it is known that the row's pid column value is 010160-ABCD, it is known that it corresponds uniquely to the name Adam Adapter.

The following functional dependency does not hold:

{name} -> {pid}

It does not hold, because for example with name column value Adam Adapter there are two different possible pid column values: 010160-ABCD and 030380-IJKL. Functional dependency means that the correspondence is unique: for every name there should be at most one personal ID, but that is not the case here.

It is worth noting that in the examples above, functional dependencies have been derived from example data. Usually, normalization might be done already at the database design stage when there is no data yet. Then functional dependencies must be deduced by understanding the domain. Although mathematical notation is used to represent functional dependencies, the question is not about a mathematical phenomenon but specifically about understanding the meaning of the relation.

ccode cname year teacher_id credits
itka201 Algorithms 2015 t447 4
itka201 Algorithms 2014 t051 3
itka204 Databases 2014 t300 5
itka204 Databases 2015 t300 5
itka204 Databases 2013 t300 4
tjta118 IT Infra 2014 t411 3
tjta118 IT Infra 2015 t411 3
# monifd

Inference Rules

From the definition and examples above, one can deduce that some functional dependencies can be inferred from other dependencies. For example, if it is known that a student's student ID identifies the student's first name, last name, and SSN together:

{sid} -> {ssn, first_name, last_name}

then clearly the student ID also identifies the SSN, first name, and last name separately:

{sid} -> {ssn}
{sid} -> {first_name}
{sid} -> {last_name}

Meaning: if it is known that with sid one can find a certain student's SSN, first name, and last name, then of course with sid one can find each piece of information also individually.

Armstrong [1] has presented a set of rules with which functional dependencies can be inferred via other dependencies. Functional dependencies that can be inferred using these rules are called trivial.

  1. Reflexivity Rule (axiom of reflectivity): if attribute set Y is a subset of another attribute set X, a trivial functional dependency "X determines Y" holds. That is:

    If Y ⊂ X, then {X} -> {Y}.

    As a consequence of the rule, attribute set X always depends on itself, i.e.:

    {X} -> {X}

    Example: Student's first name depends on student's first name, i.e., {first_name} -> {first_name}. Student's first name also depends on the combination of first name and last name: {first_name, last_name} -> {first_name}.

  2. Transitivity Rule (axiom of transitivity): if functional dependencies "X determines Y" and "Y determines Z" hold, then functional dependency "X determines Z" also holds. That is:

    If {X} -> {Y} and {Y} -> {Z}, then {X} -> {Z}.

    Example: From a student's SSN, their first name and last name are known, i.e., {ssn} -> {first_name, last_name}. On the other hand, if the first name and last name are known, their initials are known, i.e., {first_name, last_name} -> {initials}. Therefore, from a student's SSN, their initials are known, i.e., {ssn} -> {initials}.

  3. Union Rule (axiom of union): if functional dependencies "X determines Y" and "X determines Z" hold, then functional dependency "X determines union of Y and Z" also holds. That is:

    If {X} -> {Y} and {X} -> {Z}, then {X} -> {Y, Z}.

    Example: Student's student ID identifies student's first name, i.e., {sid} -> {first_name}. On the other hand, student's student ID also identifies student's last name, i.e., {sid} -> {last_name}. Therefore, student ID identifies student's first name and last name, i.e., {sid} -> {first_name, last_name}.

  4. Decomposition Rule (axiom of decomposition): if functional dependency "X determines union of Y and Z" holds, then functional dependencies "X determines Y" and "X determines Z" also hold. That is:

    If {X} -> {Y, Z}, then {X} -> {Y} and {X} -> {Z}.

    Example: Student's SSN identifies first name and last name, i.e., {ssn} -> {first_name, last_name}. Therefore, student's SSN identifies first name ({ssn} -> {first_name}) and last name ({ssn} -> {last_name}).

  5. Augmentation Rule (axiom of augmentation): if functional dependency "X determines Y" holds, then functional dependency "combination of X and Z determines Y" also holds, i.e. if "X determines Y", then "X's supersets also determine Y". That is:

    If {X} -> {Y}, then {X, Z} -> {Y}.

    Example: Student's SSN identifies student's last name, i.e., {ssn} -> {last_name}. The dependency holds even if, for instance, first name was added to the determinant set, i.e., {ssn, first_name} -> {last_name}.

Huomautus

One essential consequence of the decomposition rule and union rule is that functional dependency

{X} -> {Y1, Y2, ..., Yn}

is equivalent to the fact that all following dependencies hold simultaneously:

{X} -> {Y1}
{X} -> {Y2}
...
{X} -> {Yn}

and vice versa. In other words, it does not matter if functional dependencies are marked separately or combined into the same dependency.

Huomautus

Note that the rules above are of the form "if (1) then (2)". The rule does not necessarily hold the other way around, meaning "if (2) then (1)" is not always true!

For example, the most common error in reasoning is that the determinant attribute set can always be decomposed while preserving functional dependency!

In the database of study completions at the beginning of this chapter, there is the following dependency according to the primary key:

{sid, cid} -> {sname, cname, grade}

(student ID and course ID together identify student's name, course name, and completion grade).

Here one might want to e.g. leave cid out of the determinant attribute set, because for instance student's name does not depend on the course ID. However, this dependency:

{sid} -> {sname, cname, grade}

does not necessarily hold anymore, because two different students can have the same name, completed course, and even the same grade. For the same reason, student ID cannot be left out of the determinant set.

Instead, in this case, we notice that by taking attributes out of both determinant and dependent sets, we get multiple valid functional dependencies:

{sid} -> {sname}
{cid} -> {cname}
{sid, cid} -> {grade}

So be careful to apply the rules in the "correct direction"!

In the figure below, another way to describe functional dependencies is presented. Here too, the arrow points from the determinant attribute set to the dependent attribute. Functional dependencies are numbered for the multiple choice task.

Figure: attributes of relation R with their functional dependencies.
Figure: attributes of relation R with their functional dependencies.
# moniarmax

Normalisoinnin perusteet

Osissa 2 ja 3 opimme tapoja suunnitella relaatiotietokanta ns. "hyvien oppien" mukaisesti. Relaatiomallin oikeanlainen käyttö tarjoaa suojan ja jotain varmistuksia tietokannassa olevalle datalle. Esimerkiksi jos suunniteltaisiin relaatio OPISKELIJA(optun, syntymäaika), jossa perusavain olisi {optun}, on mahdotonta edes vahingossa saattaa taulu tilanteeseen, jossa samalla opiskelijalla olisi kaksi eri syntymäaikaa:

optun syntymäaika
o1 1.2.1990
o1 2.3.2000

Tämä tilanne on relaatiomallin kannalta mahdoton, sillä taulun jokainen rivi on voitava erottaa toisistaan perusavaimen perusteella, eikä siis tauluun voisi lisätä kahta riviä, joilla on sama opiskelijatunnus.

Osassa 4 opimme myös, että relaatiotietokannanhallintajärjestelmät (RDBMS) automaattisesti varmistavat tietokannan oikeellisuuden aina, kun dataa lisätään, muokataan tai poistetaan. Esimerkiksi RDBMS:t tarkistavat datan tyypin, varmistavat perusavaimen mukaisen rivien yksikäsitteisyyden ja tarkistavat myös, että viiteavainten viite-eheys säilyy.

Aina kuitenkaan relaatiomallin peruspalikat eivät riitä takaamaan datan loogisuutta. Yleisesti, jos taulu voidaan saattaa kohdealueen kannalta "järjettömään" tilaan, vika on usein tietokannan rakenteessa. Tässä osassa tutustumme normalisointiin eli siihen, miten tietokannan rakenteen suunnittelulla voidaan suojata datan loogisuutta ja vähentää toisteisuutta.

Normalisoinnin tarkoitus

Normalisoinnilla on kaksi päätarkoitusta:

  1. korjata datan oikeellisuusvirheille alttiita tietokantarakenteita ja
  2. vähentää datan toisteisuutta (redundancy) muutoin loogisesti oikein suunnitellussa rakenteessa.

Tämän lisäksi normalisointi helpottaa tietokannan käyttöä seuraavasti:

  • Normalisoidut taulut ovat yksinkertaisempia ymmärtää, eikä niissä ole ns. "turhia" sarakkeita.
  • Normalisoituja tauluja on helppo laajentaa kattamaan uusia kohdealueen tarpeita. Parhaimmillaan laajentaminen ei vaadi muutoksia tietokannan rakenteeseen.
  • Normalisoidut taulut ovat paremmin suojattuja lisäys-, poisto- ja muokkausoperaatioista johtuvilta poikkeamilta (eli datan ristiriidoilta).

Datan oikeellisuusvirheille alttiilla rakenteella tarkoitetaan attribuuttien nimiä, jotka kuvaavat huonosti kohdealuetta; rakenteita, joissa esiintyy runsaasti tyhjäarvoja; sekä relaatiorakenteita, joihin on tarpeettomasti yhdistetty attribuutteja useista reaalimaailman kohteista.

Datan toisteisuudella tarkoitetaan puolestaan samojen arvojen tarpeetonta toistamista. Datan toisto luonnollisesti kasvattaa tallennustilatarpeita. Datan toisto johtaa myös helpommin datan oikeellisuuden poikkeamiin.

Esimerkki

Tarkastellaan seuraavaa opiskelijatietokantaa, joka sisältää yhden taulun. Taulu pitää kirjaa opiskelijoista, kurssisuorituksista, kursseista ja suorituksen arvosanoista:

optun opnimi kurssitun kurssinimi arvosana
o7111 Aatami Laippa itka204 Tietokannat 5
o7111 Aatami Laippa itkp113 Oliosuunnittelu 4
o7111 Aatami Laippa tjta114 Tietohallinto HYV
o6800 Bertta Hukari itka204 Tietokannat 5
o6604 Cecilia Rastas tjta114 Tietohallinto HYV

Nykyisellä rakenteella tietojen lisäys, muokkaus tai poisto voi helposti aiheuttaa poikkeamia tietokantaan. Poikkeama tarkoittaa sitä, että tietokannan tiedot jäävät ristiriitaisiksi itsensä tai kohdealueen kanssa tietokantaan kohdistuvan operaation jälkeen.

Millaisia lisäys-, muokkaus- ja poistopoikkeamia tässä tietokannassa voi esiintyä?

  • Oletetaan, että tauluun lisätään seuraava rivi:

    optun opnimi kurssitun kurssinimi arvosana
    o6800 Bertta Hukari tjta114 Tietohallinnon perusteet 5

    Kurssin tjta114 nimestä tulee ristiriitainen, sillä lisäyksen jälkeen kurssin nimi voi olla "Tietohallinto" tai "Tietohallinnon perusteet".

    Kyseessä on siis lisäyspoikkeama.

  • Oletetaan, että taulusta poistetaan seuraava rivi:

    optun opnimi kurssitun kurssinimi arvosana
    o7111 Aatami Laippa itkp113 Oliosuunnittelu 4

    Nyt Aatami Laipalta poistui Oliosuunnittelu-kurssin suoritus, mutta nyt myös koko tietokannasta poistui tieto Oliosuunnittelu-kurssin olemassaolosta. Nyt jos tietokannan avulla haluttaisiin selvittää, mitä kursseja opetetaan, tietokannasta ei löytyisi Oliosuunnittelu-kurssia. Tämä olisi ristiriidassa kohdealueen kanssa.

    Kyseessä on poistopoikkeama.

  • Oletetaan, että kurssin itka204 kurssikoodi muuttuu koodiksi itka2004 ja nimi muuttuu "Tietokantojen perusteet". Muutoksen takia muutetaan rivi

    optun opnimi kurssitun kurssinimi arvosana
    o7111 Aatami Laippa itka204 Tietokannat 5

    muotoon

    optun opnimi kurssitun kurssinimi arvosana
    o7111 Aatami Laippa itka2004 Tietokantojen perusteet 5

    Nyt kuitenkin saatettiin unohtaa, että taulussa on myös opiskelija o6800, jonka rivi pitäisi myös päivittää! Tietokannan dataan syntyy ristiriita: yhdellä opiskelijalla on uuden kurssikoodin ja kurssin nimen suoritus, mutta toisella opiskelijalla on vanhan, olemattoman kurssikoodin mukainen suoritus.

    Päädyimme siis muokkauspoikkeamaan.

Nykyinen tietokanta kaipaa siis kipeasti normalisointia!

PS: Yleisestikin, jos useita kohdealueen eri kohteita mallinnetaan samaan tauluun, poikkeamat ovat erittäin mahdollisia.

Funktionaalinen riippuvuus

Kuten huomattiin, datan liiallinen toisteisuus aiheuttaa ongelmia, ja normalisoinnin ytimessä on sen vähentäminen. Toisaalta jonkinlainen toisteisuus on välttämätöntä: yllä olevassa esimerkissä perusavaimeen kuuluvat opiskelijan tunnus ja kurssikoodi on pakko toistaa taulussa, jotta perusavaimen takaama rivien yksilöllisyys voidaan taata. Toisin sanoin toisteisuus on virhealtista, mutta kaikkea datan toistoa ei voida välttää. Miten voidaan siis erottaa "sallittua" toisteisuutta sellaisesta, joka voisi olla altista poikkeamille?

Esimerkki

Palataan hetkeksi Luvussa 3.1 perusavaimen yhteydessä olevaan esimerkkiin taulusta OPISKELIJA(opnro, hetu, etunimi, sukunimi, postinro, paikkakunta).

Keksitäänpä malliksi jotain dataa, jotta ongelmia on helpompaa tarkastella:

opnro hetu etunimi sukunimi postinro paikkakunta
o101 120196-111X Matti Meikäläinen 33720 Tampere
o102 130280-112X Lumi Sinkki 40520 Jyväskylä
o103 130280-321Z Lumi Sinkki 40520 Jyväskylä
o104 121240-111A Aku Ankka 60200 Seinäjoki
o105 241252-321X Taavi Ankka 33720 Tampere

Muistellaan, että avainehdokas on jakamaton joukko sarakkeita, jotka yksilöivät koko rivin. Toisin sanoin avainehdokkaan sarakkeiden arvojen perusteella voidaan yksilöllisesti tietää tasan tarkkaan jonkin rivin kaikkien muiden sarakkeiden arvot.

Luvun 3.1 esimerkissä totesimme, että:

  • {opnro} on avainehdokas, sillä opnro-sarakkeen arvon perusteella tiedetään yksilöllisesti sarakkeiden {hetu, etunimi, sukunimi, postinro, paikkakunta} arvot.
    • Esimerkiksi jos tiedetään, että jonkun opiskelijan opnro on o101, tiedetään, että sen opiskelijan hetu on "120196-111X", etunimi Matti, sukunimi Meikäläinen, postinro 33720 ja paikkakunta Tampere.
  • {hetu} on myös avainehdokas samalla perustelulla: jos tiedetään jonkun opiskelijan hetu, tiedetään yksilöllisesti sitä vastaavat arvot {opnro, etunimi, sukunimi, postinro, paikkakunta}.

Taulun ja kohdealueen perusteella voidaan tehdä seuraava mielenkiintoinen huomio: vaikka {postinro} ei yksilöi kaikkia taulun sarakkeita, se yksilöi sarakkeen paikkakunta. Jos tiedetään, että jonkun oppilaan osoitteen postinumero on 33720, tiedämme yksikäsitteisesti, että paikkakunta on Tampere.

Toisin sanoin {postinro} ei ole OPISKELIJA-taulun avainehdokas, mutta se silti käyttäytyy samalla tavoin paikkakunta-sarakkeen suhteen: postinumero ei yksilöi kaikkia taulun sarakkeita, mutta se silti yksilöi jotain sarakkeita. Näemme taulussa myös, että paikkakunta-sarakkeessa on toisteisuutta.

Kokeillaan tehdä taulu PAIKKAKUNTA(postinro, paikkakunta) ja kopioidaan tietoa OPISKELIJA-taulusta:

postinro paikkakunta
33720 Tampere
40520 Jyväskylä
60200 Seinäjoki

Tässä relaatiossa nyt {postinro} on avainehdokas, sillä se yksilöi sarakkeen paikkakunta, joka on ainoa avainehdokkaan ulkopuolella oleva sarake. Se on myös ainoa avainehdokas, eli myös perusavain. Erityisesti toisteisuutta on vähennetty: samaa postinumeron ja paikkakunnan yhdistelmää ei toistu turhaan.

Esimerkistä voimme päätellä, että normalisointiin liittyy läheisesti se, miten hyvin sarakkeiden arvot ovat yksilöitävissä toisten sarakkeiden arvojen perusteella. Asia liittyy myös osin avainehdokkaiden ja perusavainten määritelmiin, mutta vähän yleisemmällä tasolla. Tästä päästäänkin funktionaalisiin riippuvuuksiin.

Funktionaalisen riippuvuuden määritelmä

Normalisoinnin tärkein käsite on funktionaalinen riippuvuus (functional dependency). Annetaan alkuun tarkka määritelmä relaatiomallin sanoin:

Määritelmä

Jos joukko relaation R attribuutteja X yksilöi jonkin toisen joukon saman relaation attribuutteja Y, sanotaan, että relaatiossa pätee funktionaalinen riippuvuus

{X} -> {Y}

Funktionaalisessa riippuvuudessa X on määräävä attribuuttijoukko. Sanotaan, että "Attribuutit Y riippuvat funktionaalisesti attribuuteista X" tai "Y on funktionaalisesti riippuvainen X:stä". Yleisemmin voi sanoa, että "X yksilöi Y:n".

Toisin sanoen jokaisella monikolla, jossa attribuuteilla X on tietty arvo a, on attribuuteilla Y korkeintaan yksi arvo b.

Käytännössä funktionaalinen riippuvuus on tosi lähellä avainehdokkaan määritelmää. Avainehdokas on mikä tahansa (jakamaton) relaation attribuuttijoukko, joka yksilöi monikon kaikki muut attribuutit. Funktionaalinen riippuvuus taas on mikä tahansa relaation attribuuttijoukko, joka yksilöi minkä tahansa muun joukon relaation attribuutteja.

Otetaan vielä pari esimerkkiä käsitteen selkeyttämiseksi:

Esimerkki

Palataan taas Luvussa 3.1 perusavaimen yhteydessä olevaan esimerkkiin taulusta OPISKELIJA(opnro, hetu, etunimi, sukunimi, postinro, paikkakunta) sekä aiemmassa esimerkissä keksittyyn mallidataan:

opnro hetu etunimi sukunimi postinro paikkakunta
o101 120196-111X Matti Meikäläinen 33720 Tampere
o102 130280-112X Lumi Sinkki 40520 Jyväskylä
o103 130280-321Z Lumi Sinkki 40520 Jyväskylä
o104 121240-111A Aku Ankka 60200 Seinäjoki
o105 241252-321X Taavi Ankka 33720 Tampere

Aiemmassa esimerkissä totesimme, että {opnro} on avainehdokas. Avainehdokas yksilöi taulun kaikki muut sarakkeet: jos tiedetään opiskelijan opiskelijanumero, tiedetään yksikäsitteisesti opiskelijan muiden sarakkeiden arvot. Toisin sanoin on voimassa seuraava funktionaalinen riippuvuus:

{opnro} -> {hetu, etunimi, sukunimi, postinro, paikkakunta}

Tämä ei kerro mitään uutta mitä ei avainehdokkaasta tiedetä; se on vain eri tapa merkitä asiaa.

Vastaavasti koska {hetu} on avainehdokas, pätee myös seuraava funktionaalinen riippuvuus:

{hetu} -> {opnro, etunimi, sukunimi, postinro, paikkakunta}

Aiemmassa esimerkissä huomattiin, että sarake postinro yksilöi sarakkeen paikkakunta. Jos tiedetään, että jonkun opiskelijan postinro on 33720, tiedetään yksikäsitteisesti, että opiskelijan paikkakunta on aina Tampere. Funktionaalisen riippuvuuden merkinnöillä siis:

{postinro} -> {paikkakunta}

Esimerkki

Tarkastellaan seuraavaa taulua HENKILÖ(htun, nimi):

htun nimi
010160-ABCD Aatami Laippa
020270-EFGH Bertta Hukari
030380-IJKL Aatami Laippa
040490-MNOP Cecilia Rastas

Vaikka emme tietäisi mitään kohdealueesta, voidaan taulun tietojen perusteella päätellä, että seuraava funktionaalinen riippuvuus pätee:

{htun} -> {nimi}

Se pätee, koska jokaista htun-sarakkeen arvoa vastaa yksikäsitteinen nimi. Esimerkiksi, jos tiedetään, että rivin htun-sarakkeen arvo on 010160-ABCD, tiedetään, että sitä vastaa yksikäsitteisesti nimi Aatami Laippa.

Seuraava funktionaalinen riippuvuus ei päde:

{nimi} -> {htun}

Se ei päde, sillä esimerkiksi nimi-sarakkeen arvolla Aatami Laippa löytyy kaksi eri mahdollista htun-sarakkeen arvoa: 010160-ABCD ja 030380-IJKL. Funktionaalinen riippuvuus tarkoittaa, että vastaavuus on yksikäsitteinen: jokaiselle nimelle pitäisi löytyä korkeintaan yksi henkilötunnus, mutta näin ei tässä ole.

On syytä huomata, että yllä olevissa esimerkeissä funktionaaliset riippuvuudet on johdettu esimerkkidatasta. Tavallisesti normalisointi saatetaan tehdä jo tietokannan suunnittelun vaiheessa, kun dataa ei vielä ole. Silloin funktionaaliset riippuvuudet on pääteltävä kohdealuetta ymmärtämällä. Vaikka funktionaalisten riippuvuuksien esittämiseen käytetään matemaattista notaatiota, ei kysymyksessä ole matemaattinen ilmiö vaan nimenomaan relaation merkityksen ymmärtäminen.

kurssikoodi kurssinimi vuosi opettajatun laajuus
itka201 Algoritmit 2015 op447 4
itka201 Algoritmit 2014 op051 3
itka204 Tietokannat 2014 op300 5
itka204 Tietokannat 2015 op300 5
itka204 Tietokannat 2013 op300 4
tjta118 IT-infra 2014 op411 3
tjta118 IT-infra 2015 op411 3
# monifd

Päättelysäännöt

Yllä olevasta määritelmästä ja esimerkeistä voi päätellä, että jotkut funktionaaliset riippuvuudet voidaan päätellä muista riippuvuuksista. Esimerkiksi jos tiedetään, että opiskelijan opiskelijatunnus yksilöi opiskelijan etunimen, sukunimen ja hetun yhdessä:

{optun} -> {hetu, etunimi, sukunimi}

niin selvästi opiskelijan tunnus yksilöi myös erikseen hetun, etunimen ja sukunimen:

{optun} -> {hetu}
{optun} -> {etunimi}
{optun} -> {sukunimi}

Eli: jos tiedetään, että optun:lla voi löytää tietyn opiskelijan hetun, etunimen sekä sukunimen, niin totta kai optun:lla voi löytää jokaisen tiedon myös yksittäin.

Armstrong [1] on esittänyt joukon sääntöjä, joilla funktionaalisia riippuvuuksia voi päätellä muiden riippuvuuksien kautta. Sellaisia funktionaalisia riippuvuuksia, joita voidaan päätellä näiden sääntöjen avulla, kutsutaan triviaaleiksi.

  1. Refleksiivisyyssääntö (axiom of reflectivity): jos attribuuttijoukko Y on toisen attribuuttijoukon X osajoukko, pätee triviaali funktionaalinen riippuvuus "X yksilöi Y:n". Eli:

    Jos Y ⊂ X, niin {X} -> {Y}.

    Säännön seurauksena attribuuttien joukko X riippuu aina itsestään, eli:

    {X} -> {X}

    Esimerkki: Opiskelijan etunimi riippuu opiskelijan etunimestä, eli {etunimi} -> {etunimi}. Opiskelijan etunimi riippuu myös etunimen ja sukunimen yhdistelmästä: {etunimi, sukunimi} -> {etunimi}.

  2. Transitiivisuussääntö (axiom of transitivity): jos pätevät funktionaaliset riippuvuudet "X yksilöi Y:n" ja "Y yksilöi Z:n", pätee myös funktionaalinen riippuvuus "X yksilöi Z:n". Eli:

    Jos {X} -> {Y} ja {Y} -> {Z}, niin {X} -> {Z}.

    Esimerkki: Opiskelijan hetusta tiedetään hänen etunimensä ja sukunimensä, eli {hetu} -> {etunimi, sukunimi}. Toisaalta jos tiedetään etunimi ja sukunimi, tiedetään hänen nimikirjaimensa, eli {etunimi, sukunimi} -> {nimikirjaimet}. Siispä opiskelijan hetusta tiedetään hänen nimikirjaimensa, eli {hetu} -> {nimikirjaimet}.

  3. Yhdistesääntö (axiom of union): jos pätevät funktionaaliset riippuvuudet "X yksilöi Y:n" ja "X yksilöi Z:n", pätee myös funktionaalinen riippuvuus "X yksilöi Y:n ja Z:n yhdisteen". Eli:

    Jos {X} -> {Y} ja {X} -> {Z}, niin {X} -> {Y, Z}.

    Esimerkki: Opiskelijan opiskelijatunnus yksilöi opiskelijan etunimen, eli {optun} -> {etunimi}. Toisaalta myös opiskelijan opiskelijatunnus yksilöi myös opiskelijan sukunimen, eli {optun} -> {sukunimi}. Siispä opiskelijan tunnus yksilöi opiskelijan etunimen sekä sukunimen, eli {optun} -> {etunimi, sukunimi}.

  4. Jakosääntö (axiom of decomposition): jos pätee funktionaalinen riippuvuus "X yksilöi Y:n ja Z:n yhdisteen", pätevät myös funktionaaliset riippuvuudet "X yksilöi Y:n" ja "X yksilöi Z:n". Eli:

    Jos {X} -> {Y, Z}, niin {X} -> {Y} sekä {X} -> {Z}.

    Esimerkki: Opiskelijan hetu yksilöi etunimen ja sukunimen, eli {hetu} -> {etunimi, sukunimi}. Siispä opiskelijan hetu yksilöi etunimen ({hetu} -> {etunimi}) sekä sukunimen ({hetu} -> {sukunimi}).

  5. Täydentämissääntö (axiom of augmentation): jos pätee funktionaalinen riippuvuus "X yksilöi Y:n", pätee myös funktionaalinen riippuvuus "X:n ja Z:n yhdistelmä yksilöi Y:n", ts. jos "X yksilöi Y:n", niin "X:n ylijoukot myös yksilöivät Y:n". Eli:

    Jos {X} -> {Y}, niin {X, Z} -> {Y}.

    Esimerkiksi: Opiskelijan hetu yksilöi opiskelijan sukunimen, eli {hetu} -> {sukunimi}. Riippuvuus pätee, vaikka määräävään joukkoon lisättäisiin vaikkapa etunimi, eli {hetu, etunimi} -> {sukunimi}.

Huomautus

Jakosäännön ja yhdistesäännön yksi olennainen seuraus on, että funktionaalinen riippuvuus

{X} -> {Y1, Y2, ..., Yn}

on yhtäpitävä sen kanssa, että kaikki seuraavat riippuvuudet pätevät samanaikaisesti:

{X} -> {Y1}
{X} -> {Y2}
...
{X} -> {Yn}

ja myös toisinpäin. Toisin sanoin ei ole väliä, merkitäänkö funktionaaliset riippuvuudet erillään vai yhdistettynä samaan riippuvuuteen.

Huomautus

Huomaa, että yllä olevat säännöt ovat muotoa "jos (1) niin (2)". Sääntö ei välttämättä päde toisin päin, eli "jos (2) niin (1)" ei ole aina totta!

Esimerkiksi yleisin virhepäätelmä on, että määräävää attribuuttijoukkoa voi aina jakaa säilyttäen funktionaalinen riippuvuus!

Tämän luvun alussa olevassa opintosuoritusten tietokannassa on seuraava perusavaimen mukainen riippuvuus:

{optun, kurssitun} -> {opnimi, kurssinimi, arvosana}

(opiskelijatunnus ja kurssitunnus yhdessä yksilöivät opiskelijan nimen, kurssin nimen ja suorituksen arvosanan).

Tässä voi tulla esimerkiksi halu jättää kurssitun pois määräävästä attribuuttijoukosta, sillä esimerkiksi opiskelijan nimi ei riipu kurssin tunnuksesta. Kuitenkaan tämä riippuvuus:

{optun} -> {opnimi, kurssinimi, arvosana}

ei enää välttämättä päde, sillä kahdella eri opiskelijalla voi olla sama nimi, suoritettu kurssi ja jopa sama arvosana. Samasta syystä opiskelijan tunnusta ei voi jättää pois määräävästä joukosta.

Sen sijaan tässä tapauksessa huomataan, että ottamalla attribuutteja pois sekä määräävästä että riippuvasta joukosta saadaan useita valideja funktionaalisia riippuvuuksia:

{optun} -> {opnimi}
{kurssitun} -> {kurssinimi}
{optun, kurssitun} -> {arvosana}

Ole siis tarkkana, että sovellat säännöt ns. oikein päin!

Alla olevassa kuviossa on esitetty toinen tapa kuvata funktionaalisia riippuvuuksia. Nuoli osoittaa tässäkin määräävästä attribuuttijoukosta riippuvaan attribuuttiin. Funktionaaliset riippuvuudet on numeroitu monivalintatehtävän vuoksi.

Kuvio: relaation R attribuutit funktionaalisine riippuvuuksineen.
Kuvio: relaation R attribuutit funktionaalisine riippuvuuksineen.
# moniarmax

These are the current permissions for this document; please modify if needed. You can always modify these permissions from the manage page.