8. Databasernas teori
Relationsmodellen
SQL-databaser bygger på relationsmodellen, vars teoretiska grund utvecklades på 1970-talet. År 1970 presenterade E. F. Codd i sin artikel A relational model of data for large shared data banks både idén om en databas som använder relationsmodellen och ett allmänt databasspråk för frågor.
Jämfört med tidigare databaser var relationsmodellens styrka dess enkelhet. Med samma tydliga modell kan man på ett naturligt sätt representera olika slags data och genomföra mångsidiga frågor.
Men vad betyder egentligen en relation? Ett enkelt exempel på en relation är den binära relation \(<\) alltså “mindre än”. Denna relation definierar en mängd av par där varje par \((a,b)\) uppfyller villkoret \(a<b\). Om vi begränsar oss till positiva heltal ser mängden ut på följande sätt:
\[[(1,2),(1,3),(2,3),(1,4),(2,4),(3,4),\dots]\]En binär (tvåställig) relation innebär att varje element i relationen är ett par. Mer generellt kan man definiera en \(k\)-ställig relation, där varje element i relationen är en k-tupel av formen \((x_1,x_2,\dots,x_k)\).
I en relationsdatabas representerar en relation en samling information med en viss struktur. Till exempel innehåller följande relation information om produkterna:
\[P = \{(1,rädisa,7), (2,morot,5), (3,rova,4),\\ (4,kålrot,8), (5,selleri,4)\}\]Denna relation är treställig och dess attribut är:
- \(id\): produktens ID-nummer
- \(name\): produktens namn
- \(price\): produktens pris
Till exempel i tupeln \((1,rädisa,7)\) är attributet \(id\) lika med \(1\), attribtet \(name\) lika med \(rädisa\) och attributet \(price\) lika med \(7\).
Relationen ovan motsvarar databastabellen Products som innehåller information om produkterna:
| id | name | price |
|---|---|---|
| 1 | rädisa | 7 |
| 2 | morot | 5 |
| 3 | rova | 4 |
| 4 | kålrot | 8 |
| 5 | selleri | 4 |
En relation är alltså ett matematiskt sätt att beskriva innehållet i en databastabell som en mängd. Varje tupel i relationen motsvarar en rad i tabellen, och antalet attribut i tupeln är detsamma som antalet kolumner i tabellen.
Relationsoperatorer
Med hjälp av relationsoperatorer kan man skapa nya relationer från redan befintliga relationer. Detta motsvarar en SQL-fråga där man skapar en resultattabell från en eller flera tabeller. Tre centrala relationsoperatorer är projektion, selektion och join.
Projektion
Projektion (projection) \(\Pi\) skapar en relation som endast innehåller vissa attribut från den ursprungliga relationen. Exempelvis:
\[\Pi_{name}(P) = \{(rädisa),(morot),(rova),(kålrot),(selleri)\}\] \[\Pi_{price}(P) = \{(7),(5),(4),(8)\}\] \[\Pi_{name,price}(P) = \{(rädisa,7),(morot,5),(rova,4),\\(kålrot,8),(selleri,4)\}\]Observera att eventuella upprepade tupler tas bort i projektionen eftersom en projektion är en relation, det vill säga en mängd. Projektionen \(\Pi_{price}(P)\) innehåller således endast fyra tupler, eftersom två produkter har samma pris.
Projektion motsvarar en SQL-fråga som hämtar vissa kolumner från en tabell. Exempelvis projektionen \(\Pi_{name}(P)\) motsvarar SQL-frågan SELECT name FROM Products.
Selektion
En selektion (restriction) \(\sigma\) skapar en relation som endast innehåller de tupler från den ursprungliga relationen som uppfyller vissa villkor. Exempelvis:
\[\sigma_{name = rova}(P)=\{(3,rova,4)\}\] \[\sigma_{price = 4}(P)=\{(3,rova,4),(5,selleri,4)\}\] \[\sigma_{price \le 5}(P)=\{(2,morot,5),(3,rova,4),(5,selleri,4)\}\]Selektionen motsvarar en SQL-fråga där rader väljs med WHERE-villkoret. Till exempel motsvarar selektionen \(\sigma_{price = 4}(P)\) SQL-frågan SELECT * FROM Products WHERE price = 4.
Genom att kombinera en projektion och en selektion får man en motsvarighet till exempelvis SQL-frågan SELECT name FROM Products WHERE price <= 5:
Join
Join (sammanslagning, på engelska: join) \(\bowtie\) skapar en relation som innehåller kombinationer av tupler från två relationer. I joinen väljs sådana kombinationer där attributvärdena är desamma i de attribut som förekommer i båda de ursprungliga relationerna. De gemensamma attributen visas endast en gång i joinen.
Vi betraktar som exempel relationerna:
\[E = \{(1,Maija,1),(2,Liisa,1),(3,Kaaleppi,3)\}\] \[C = \{(1,Google),(2,Amazon),(3,Facebook)\}\]Relationen \(E\) representerar de anställda och består av följande attribut:
- \(eid\): den anställdes ID-nummer
- \(ename\): den anställdes namn
- \(cid\): företagets ID-nummer
Relationen \(C\) representerar företagen och består av följande attribut:
- \(cid\): företagets ID-nummer
- \(cname\): företagets namn
När man skapar joinen \({E\ \bowtie\ C }\) letar man efter kombinationer av tupler där det gemensamma attributet \(cid\) är lika. Dessa kombinationer är:
- \((1,Maija,1)\) ja \((1,Google)\)
- \((2,Liisa,1)\) ja \((1,Google)\)
- \((3,Kaaleppi,3)\) ja \((3,Facebook)\)
I joinen samlas attributen \(eid\), \(ename\), \(cid\) och \(cname\) på följande sätt:
\[{E\ \bowtie\ C } = \{(1,Maija,1,Google),\\(2,Liisa,1,Google),\\(3,Kaaleppi,3,Facebook)\}\]Vi kan använda projektion efter joinen på följande sätt:
\[\Pi_{ename,cname}({E\ \bowtie\ C}) = \{(Maija,Google),\\(Liisa,Google),\\(Kaaleppi,Facebook)\}\]Joinen motsvarar en viss typ av SQL-fråga mellan två tabeller. Till exempel motsvarar de ovanstående relationerna tabellerna Employees och Companies:
| id | name | company_id |
|---|---|---|
| 1 | Maija | 1 |
| 2 | Liisa | 1 |
| 3 | Kaaleppi | 3 |
| id | name |
|---|---|
| 1 | |
| 2 | Amazon |
| 3 |
Nu motsvarar \(\Pi_{ename,cname}({E\ \bowtie\ C})\) följande SQL-fråga:
SELECT Employees.name, Companies.name
FROM Employees, Companies
WHERE Employees.company_id = Companies.id;
Teori vs. praxis
Tabeller i en SQL-databas motsvarar inte fullt ut relationerna i relationsmodellen, utan det finns skillnader mellan tabeller och relationer.
En skillnad är att varje tupel i en relation är unik, medan en tabell i en SQL-databas kan innehålla flera identiska rader. Till exempel kan vi skapa tabellen Test och lägga till tre likadana rader:
sqlite> CREATE TABLE Test (x INTEGER);
sqlite> INSERT INTO Test VALUES (1);
sqlite> INSERT INTO Test VALUES (1);
sqlite> INSERT INTO Test VALUES (1);
sqlite> SELECT * FROM Test;
1
1
1
Ofta har dock en SQL-tabell en kolumn id som garanterar att det inte finns två identiska rader, eftersom varje rad har ett unikt ID-nummer.
En annan skillnad är att varje attribut i en tupel i en relation måste ha ett värde, medan en kolumn i en SQL-tabell kan innehålla NULL, det vill säga värdet saknas.
Det finns också skillnader mellan SQL-frågor och relationsoperatorer. Som vi såg tidigare innehåller projektionen \(\Pi_{price}(P)\) varje pris bara en gång, medan resultattabellen av frågan SELECT price FROM Products kan innehålla samma pris flera gånger. I SQL finns det faktiskt två olika sätt att hämta information:
SELECT ALL ...: hämtar alla rader, även dubbletterSELECT DISTINCT ...: hämtar varje unik rad endast en gång
Det första sättet är standard, i vilket ordet ALL normalt sett inte används. Dubblettrader kan tas bort med hjälp av ordet DISTINCT. Strängt taget motsvaras alltså projektionen \(\Pi_{price}(P)\) av frågan SELECT DISTINCT price FROM Products.
I SQL kan ordningen på raderna spela roll, medan tupler i en relation inte har någon ordning. I SQL syns radordningen till exempel när en fråga använder ORDER BY i slutet för att sortera resultattabellen på önskat sätt. Med relationsoperatorer är det inte möjligt att genomföra en sådan sortering.
Nycklar och beroenden
Begrepp som är relaterade till nycklar är:
-
Supernyckel (superkey) är en kombination av attribut som garanterat är unik för varje tupel i relationen. En supernyckel identifierar alltså varje tupel i relationen.
-
Kandidatnyckel (candidate key), eller kort sagt nyckel (key), är en minimal supernyckel. Minimalitet innebär att om man tar bort något attribut från supernyckeln, är det inte längre en supernyckel.
-
Primärnyckel (primary key) är en kandidatnyckel som har valts specifikt till primärnyckel.
Exempel
Låt oss som exempel titta på en relation som beskriver produkter med attributen \(id\), \(name\) och \(price\):
I denna relation är supernycklarna åtminstone \(id\), \((id,name)\), \((id,price)\) och \((id,name,price)\). Dessa kombinationer av attribut är supernycklar eftersom de identifierar varje tupel i relationen. Av dessa supernycklar är endast \(id\) en nyckel, eftersom de andra supernycklarna inte är minimala.
Attributet \(price\) kan inte vara en supernyckel eftersom flera produkter kan ha samma pris. Attributet \(name\) kan vara en supernyckel om varje produkt garanterat har ett unikt namn. Kombinationen \((name,price)\) är en supernyckel om det inte kan finnas två produkter med både samma namn och samma pris. Vilka kombinationer av attribut som är supernycklar beror alltså på de antaganden som görs om datan.
Val av nyckel
En nyckel kan vara antingen en naturlig nyckel (natural key) eller en surrogatnyckel (surrogate key). En naturlig nyckel består av ursprunglig information, medan en surrogatnyckel läggs till just för att fungera som nyckel. Till exempel är \((name,price)\) en naturlig nyckel medan \(id\) är en surrogatnyckel.
I databasteorin används ofta naturliga nycklar, men i praktiska databaser är nyckeln vanligtvis ett ID-nummer eller motsvarande surrogatnyckel. Fördelen med ett ID-nummer är att det är kompakt information som garanterat fungerar som nyckel. Om man skulle välja en naturlig nyckel måste man överväga om de valda attributen verkligen räcker för att identifiera varje tupel i alla situationer.
Funktionella beroenden
Ett funktionellt beroende (functional dependency) \(A \to B\) betyder att attributen \(A\) bestämmer attributen \(B\). Med andra ord, om det finns två tupler i relationen med samma värden för attributen \(A\), måste även attributen \(B\) ha samma värden.
Exempelvis om en relation har attributen \(postalcode\) och \(city\), finns det ett funktionellt beroende \(postalcode \to city\) under antagandet att på basis av postnumret kan man bestämma staden. Med andra ord kan det inte finnas två tupler med samma postnummer men olika stad. Om till exempel postnumret är 00560 kan man dra slutsatsen att staden är Helsingfors.
Vad kan man dra för slutsatser av ett postnummer?
Strikt taget kan man i Finland inte härleda staden från ett postnummer, utan endast namnet på postanstalten. Postanstalten är inte nödvändigtvis en stad, och samma postnummer kan täcka områden i flera kommuner. Ett postnummer kan även avse ett företag eller en organisation, som till exempel Helsingfors universitets postnummer 00014. Mer detaljerad information finns på Postens nätsida.
För exemplen i detta kapitel kan man anta att postnumret bestämmer staden fastän det är mer komplicerat i verkligheten. Generellt kan det vara svårt att avgöra om ett funktionellt beroende gäller i alla situationer, även om det verkar så.
Attributen \(A\) utgör en supernyckel precis när \(A \to B\) gäller för alla attribut \(B\). Det betyder att i vilken tupel som helst i relationen identifierar attributen i supernyckeln vilken tupel det handlar om. När en relation exempelvis har attributen \(id\), \(name\) och \(price\), är attributet \(id\) en supernyckel eftersom det gäller att \(id \to id\), \(id \to name\) och \(id \to price\).
Normalformer
Normalform (normal form) är ett krav som gäller en databasrelation (tabell) och syftar till att främja dataintegriteten och underlätta användningen av databasen. Teoretiskt bygger normalformerna på liknande idéer som de som behandlades i kapitel 6 om principerna för god design.
De vanligaste normalformerna är första, andra och tredje normalformen.
Första normalformen
En relation uppfyller första normalformen när varje attribut i relationen har ett enkelt (atomärt) värde.
Till exempel uppfyller inte följande relation den första normalformen:
\[\{(Google, (London, Paris, Stockholm)), \\ (Amazon, Amsterdam) \\ (Facebook, (Marseille, Paris))\}\]Denna relation anger företagskontors placeringar. Problemet ur första normalformens synvinkel är att det andra attributet kan innehålla flera värden. Till exempel innehåller tupeln \((Google, (London, Paris, Stockholm))\) tre värden i det andra attributet.
Problemet kan åtgärdas genom att presentera informationen på ett annat sätt:
\[\{ (Google, London), \\ (Google, Paris), \\ (Google, Stockholm), \\ (Amazon, Amsterdam), \\ (Facebook, Marseille), \\ (Facebook, Paris) \}\]Relationen uppfyller nu första normalformen eftersom varje attribut innehåller exakt ett värde.
Första normalformen är i databasdesign kopplad till principen om att tabellernas kolumner ska innehålla atomär data.
Andra normalformen
En relation uppfyller andra normalformen när den uppfyller första normalformen och dessutom inte innehåller något funktionellt beroende \(A \to B\), där \(A\) är en del av en nyckel och \(B\) ligger utanför nyckeln.
Andra normalformen är endast relevant när nyckeln består av flera attribut. Så är fallet i följande relation:
\[\{ (Google, London, UK), \\ (Google, Paris, France), \\ (Google, Stockholm, Sweden), \\ (Amazon, Amsterdam, Netherlands), \\ (Facebook, Marseille, France), \\ (Facebook, Paris, France) \}\]I denna relation är \((name,city)\) en nyckel, eftersom dessa attribut identifierar varje tupel. I relationen finns ett funktionellt beroende \(city \to country\), eftersom landet kan härledas från kontorets stad.
Relationen uppfyller inte andra normalformen eftersom det finns ett attribut \(country\) utanför nyckeln \((name,city)\) som är beroende av en del av nyckeln, nämligen \(city\).
Vi kan uppnå andra normalformen genom att dela upp relationen i två relationer. Den första relationen innehåller företagets namn och kontorets stad:
\[\{ (Google, London), \\ (Google, Paris), \\ (Google, Stockholm), \\ (Amazon, Amsterdam), \\ (Facebook, Marseille), \\ (Facebook, Paris) \}\]Den andra relationen anger i vilka länder städerna ligger:
\[\{ (Amsterdam, Netherlands), \\ (London, UK), \\ (Marseille, France), \\ (Paris, France), \\ (Stockholm, Sweden) \}\]Betydelsen av andra normalformen är i praktiken liten, eftersom databastabeller vanligtvis använder ID-nummer som nyckel, och nyckeln inte består av flera kolumner. Den andra normalformen uppfylls därför oftast automatiskt.
Tredje normalformen
En relation uppfyller tredje normalformen om den uppfyller första och andra normalformen och dessutom inte innehåller något funktionellt beroende \(A \to B\), där \(A\) och \(B\) är skilda uppsättningar av attribut utanför nyckeln.
Till exempel uppfyller inte följande relation den tredje normalformen:
\[\{ (1, Liisa, Helsingfors, 00100), \\ (2, Maija, Helsingfors, 00560), \\ (3, Kaaleppi, Esbo, 02600), \\ (4, Uolevi, Helsingfors, 00560) \}\]Relationens nyckel är attributet \(id\). Relation uppfyller inte tredje normalformen eftersom \(postalcode\) och \(city\) är attribut utanför nyckeln, men det gäller ett funktionellt beroende \(postalcode \to city\). Här antar vi återigen att vi kan bestämma staden på basis av postnumret.
Även i detta fall kan vi dela upp relationen i två relationer, varefter tredje normalformen uppfylls. Den första relationen innehåller endast postnummer, men inga städer:
\[\{ (1, Liisa, 00100), \\ (2, Maija, 00560), \\ (3, Kaaleppi, 02600), \\ (4, Uolevi, 00560) \}\]Den andra relationen kopplar samman postnummer och städer:
\[\{ (00100, Helsingfors), \\ (00560, Helsingfors), \\ (02600, Esbo) \}\]Tredje normalformen är i databasdesign kopplad till principen om att det inte får finnas redundant information i tabellerna.
Teori vs. praxis
Syftet med normalformerna är att ge ett teoretiskt perspektiv på databasdesign. Om en databas exempelvis inte uppfyller tredje normalformen kan dess struktur behöva förbättras.
I flera normalformer är tanken att minska beroenden i relationerna som kan leda till redundant information. Om en relation inte uppfyller en normalform är lösningen ofta att dela upp relationen i flera relationer, vilket minskar den redundanta informationen.
I praktiken utformas databaser ändå vanligtvis inte med hjälp av normalformer, utan enligt principerna som beskrivs i kapitel 6. Normalformerna illustrerar en del av det tänkesätt som en skicklig databasutformare har.