Databasenormalisering
- Se også Normalisering (personnavn)
Databasenormalisering er en teknikk for å designe tabeller i relasjonsdatabaser slik at man minimerer duplisering av informasjon. Hvis samme informasjon lagres på flere ulike steder i en tabell, risikerer man at en endring fører til at databasen blir inkonsistent når noe endres. Hvis for eksempel en persons adresse er lagret på flere ulike steder i tabellen og adressen endres på ett av stedene kan man ikke lenger vite hvilken adresse som er riktig, tabellen har mistet dataintegritet.
Høyere normaliseringsgrad fører vanligvis til flere tabeller i databasen, noe som kan gi redusert ytelse(hastighet) fordi man må gjøre flere joiner av ulike tabeller for å finne sammensatt informasjon. I systemer der man ofte trenger komplisert, sammensatt informasjon kan det derfor enkelte ganger være en fordel med en lavere normaliseringsgrad.
For å oppnå en viss normalform, er det et krav at alle lavere normalformer er oppnådd.
Begreper
[rediger | rediger kilde]- Funksjonell avhengighet er et sentral begrep i normaliseringsteori. Når B har en funksjonell avhengighet av A, A → B, betyr det at for hver verdi av A finnes det eksakt en verdi av B, og hvis A gjentas får vi også samme verdi av B. For eksempel kan man si at 'adresse' er funksjonelt avhengig av 'personnavn'. Da skal samme adresse alltid være knyttet til denne personen. Det motsatte er ikke nødvendigvis tilfelle, det er ikke sagt at det nødvendigvis er bare ett personnavn knyttet til hver adresse. Hvis dette var tilfelle ville man ha en funksjonell avhengighet som gikk andre veien (B → A). Et attributt kan være funksjonelt avhengig av ett enkelt attributt, eller en kombinasjon av attributter. Det er ikke mulig å avgjøre hvilken normalform en relasjon har uten å kjenne til de funksjonelle avhengighetene, noe som forutsetter kunnskap om området relasjonen omhandler.
- Transitiv avhengighet er en indirekte funksjonell avhengighet, der X→Z fordi X→Y og Y→Z.
- Flerverdi-avhengighet oppstår når man har et mange til mange-forhold i samme relasjon der alle koblinger skal forekomme, og de to forholdene ikke har avhengigheter seg i mellom. Formelt blir dette: Hvis man har tre kolonner eller grupper av kolonner – X, Y, Z i en tabell, så er X→→Y i tabellen hvis det alltid er slik at hvis to rader(rad 1, rad 2) er like på X, så må den også ha to rader(rad 3, rad 4) der:
- Rad 3 er lik 1 på X og Y og lik 2 på Z, og
- Rad 4 er lik 2 på X og Y og lik 1 på Z
Første normalform (1NF)
[rediger | rediger kilde]Utdypende artikkel: Første normalform
Man kan ta som utgangspunkt at en tabell oppfyller første normalform hvis alle poster i relasjonen er atomære.[1] Det er en viss faglig diskusjon rundt dette, men kjernen er at tabellen skal oppfylle grunnleggende regler for en relasjon.
Eksempel
[rediger | rediger kilde]| navn | telefonnummer |
|---|---|
| Ivar Bø, Hilde Svanhjell | 750 55 647 |
| Ole Iversen | 750 13 113, 750 54 524 |
Tabellen over bryter første normalform fordi verdiene ikke er atomære. Nedenfor er samme data normalisert.
| fornavn | etternavn | telefonnummer |
|---|---|---|
| Ivar | Bø | 750 55 647 |
| Hilde | Svanhjell | 750 55 647 |
| Ole | Iversen | 750 13 113 |
| Ole | Iversen | 750 54 524 |
Andre normalform (2NF)
[rediger | rediger kilde]Utdypende artikkel: Andre normalform
For at en relasjon skal være på andre normalform må den oppfylle kravene til første normalform. I tillegg skal det ikke finnes noen ikke-nøkkelattributter som er avhengige av en del av en kandidatnøkkel. Eller sagt på en annen måte, alle kolonner i tabellen skal være fakta om en hel nøkkel, og ikke bare en del av nøkkelen.
Formell definisjon av andre normalform: En relasjon R er på andre normalform hvis alle ikketrivielle funksjonelle avhengigheter i R på formen X→A, der X er en mengde attributter og A et attributt i R, tilfredsstiller minst ett av følgende:
- X er en primærnøkkel i R
- A er et nøkkelattributt i R
- X⊄K for noen kandidatnøkkel K i R[2]
Eksempel
[rediger | rediger kilde]| emnekode | studentnummer | karakter | faglærer |
|---|---|---|---|
| MAT100 | 1001 | A | Ivar Bø |
| MAT100 | 1002 | C | Ivar Bø |
| ING100 | 1001 | B | Hilde Svanhjell |
Tabellen over bryter med andre normalform fordi kolonnen faglærer kun er avhengig av en del av den sammensatte primærnøkkelen emnekode og studentnummer. Faglærer kolonnen er kun avhengig av emnekode i motsetning til kolonnen karakter som er avhengig av hele primærnøkkelen. Ved å flytte faglærer til en ny tabell hvor vi oppretter emnekode som primærnøkkel og lar emnekoden i den opprinnelige tabellen referere til denne vil tabellene oppfylle kravene til andre normalform samtidig som vi minimerer overflødig data ved at faglærerens navn kun oppføres en gang for hver unike emnekode:
| emnekode | studentnummer | karakter |
|---|---|---|
| MAT100 | 1001 | A |
| MAT100 | 1002 | C |
| ING100 | 1001 | B |
| emnekode | faglærer |
|---|---|
| MAT100 | Ivar Bø |
| ING100 | Hilde Svanhjell |
Tredje normalform (3NF)
[rediger | rediger kilde]Utdypende artikkel: Tredje normalform
For at en relasjon skal være på tredje normalform må den oppfylle kravene til andre normalform. I tillegg skal ingen ikke-nøkkelattributter være transitivt avhengig av primærnøkkelen. Det vil si at ingen attributter skal være avhengige av noe annet enn primærnøkkelen, hvis de ikke er nøkkelattributter.
Formell definisjon av tredje normalform: En relasjon R er på tredje normalform hvis alle ikketrivielle funksjonelle avhengigheter i R på formen X→A tilfredsstiller minst ett av følgende:
- X er en primærnøkkel i R
- A er et nøkkelattributt i R[2]
Eksempel
[rediger | rediger kilde]| id | fornavn | etternavn | postnummer | poststed |
|---|---|---|---|---|
| 1 | Ivar | Bø | 3225 | Sandefjord |
| 2 | Hilde | Svanhjell | 3227 | Sandefjord |
| 3 | Ole | Iversen | 3227 | Sandefjord |
Tabellen over bryter tredje normalform fordi det finnes en transitiv avhengighet mellom poststed og id. Ved å opprette en egen tabell for postnummer og poststed vil tabellene oppfylle kravet for tredje normalform og vi kan minimere overflødig data ved at poststed ikke gjentas flere ganger for det samme postnummeret:
| id | fornavn | etternavn | postnummer |
|---|---|---|---|
| 1 | Ivar | Bø | 3225 |
| 2 | Hilde | Svanhjell | 3227 |
| 3 | Ole | Iversen | 3227 |
| postnummer | poststed |
|---|---|
| 3225 | Sandefjord |
| 3227 | Sandefjord |
Elementærnøkkel normalform (EKNF)
[rediger | rediger kilde]Utdypende artikkel: Elementærnøkkel normalform
Elementærnøkkel normalform (EKNF) er en subtil forbedring av tredje normalform (3NF), og derfor tilfredsstiller EKNF-tabeller 3NF per definisjon. Dette skjer når det er mer enn én unik sammensatt nøkkel og disse overlapper hverandre. Slike tilfeller kan forårsake overflødig informasjon i de overlappende kolonnene.
Boyce-Codd normalform (BCNF)
[rediger | rediger kilde]Utdypende artikkel: Boyce–Codd normalform
En relasjon er på Boyce–Codd normalform hvis alle attributter kun er avhengige av supernøkler. Vanligvis vil relasjoner som er på tredje normalform også oppfylle BCNF.
Formell definisjon av Boyce-Codd normalform: En relasjon R er på Boyce-Codd normalform hvis alle ikketrivielle funksjonelle avhengigheter i R på formen X→A tilfredsstiller følgende:
- X er en primærnøkkel i R[3]
Wessels theorem: Dersom du har en tabell T, med et sett av funksjonelle avhengigheter F, vil du, ved å dekomponere T i tabellene T1,...,Tn for hver funksjonelle avhengighet (1,...,n), stå igjen med tabeller som oppfyller kravene til BCNF.
Fjerde normalform (4NF)
[rediger | rediger kilde]Utdypende artikkel: Fjerde normalform
En relasjon R er på fjerde normalform hvis X er en primærnøkkel i R i alle ikketrivielle flerverdiavhengigheter X →→ Y[4]
Femte normalform (5NF)
[rediger | rediger kilde]Utdypende artikkel: Femte normalform
Femte normalform (5NF) er designet for å fjerne redundans i relasjonsdatabaser som registrerer fakta med flere verdier ved å isolere flere semantisk relaterte relasjoner.
Domene–nøkkel normalform (DKNF)
[rediger | rediger kilde]Utdypende artikkel: Domene–nøkkel normalform
Domene–nøkkel normalform (DKNF) er en normalform som krever at databasen ikke inneholder andre begrensninger enn domenebegrensninger og nøkkelbegrensninger.
Sjette normalform (6NF)
[rediger | rediger kilde]Sjette normalform (6NF) utvider relasjonsalgebraen og generaliserer relasjonsoperatorer (som skjøt) for å støtte intervalldata, hvilket kan være nyttig i temporale databaser. Enhver relasjon på 6NF er også på 5NF.
Referanser
[rediger | rediger kilde]- ^ Kobro Runde, Ragnhild: Relasjonsdatabasedesign (Slides). Universitetet i Oslo, INF3100 januar 2009.
- ^ a b Codd, E.F. "Further Normalization of the Data Base Relational Model." (Presented at Courant Computer Science Symposia Series 6, "Data Base Systems," New York City, May 24th-25th, 1971.) IBM Research Report RJ909 (August 31st, 1971). Republished in Randall J. Rustin (ed.), Data Base Systems: Courant Computer Science Symposia Series 6. Prentice-Hall, 1972.
- ^ Codd, E. F. "Recent Investigations into Relational Data Base Systems." IBM Research Report RJ1385 (April 23rd, 1974). Republished in Proc. 1974 Congress (Stockholm, Sweden, 1974). New York, N.Y.: North-Holland (1974).
- ^ Fagin, R. "Multivalued Dependencies and a new Normal Form for Relational Databases. Arkivert 29. november 2007 hos Wayback Machine." Association for Computing Machinery 1977.