Normalisering (typisk normaliserings-uppgift, från mars 2023)

Den första deluppgiften handlar om att hitta funktionella beroenden i någon problemdomän – denna sida fokuserar på själva normaliseringen (att vi har a-uppgiften beror på att man måste kunna hitta funktionella beroenden för att ha någon nytta av att normalisera).

Uppgift: Vi har relationen R(A,B,C,D,E,F) och:

• fd1: A -> CF
• fd2: C -> A
• fd3: CE -> B
• fd4: F -> D

Beräkna dess nycklar.

Lösning: Vi kan börja med att ta det transitiva höljet av vart och ett av dessa beroenden (det underlättar när vi skall beräkna nycklarna):

• fd1: A -> CDF
• fd2: C -> ADF
• fd3: CE -> ABDF
• fd4: F -> D

Det visar sig alltså direkt att CE är en nyckel (eftersom vi får alla övriga attribut).

För att hitta alla nycklar kan vi konstatera att E måste ingå i varje nyckel, eftersom den inte ingår i något högerled. Och E själv ger ingenting om vi tar dess transitiva hölje:

• {E}+ = E

Så vi får börja med alla möjliga två-attributsnycklar som innehåller E (och vet redan att CE kommer att vara en nyckel):

• {AE}+ = ABCDEF
• {BE}+ = BE
• {CE}+ = ABCDEF
• {DE}+ = DE
• {EF}+ = DEF

Det visar sig att både AE och CE är nycklar, men vi måste även undersöka eventuella tre-attributnycklar – dessa måste innehålla E, men får inte innehålla vare sig A eller C:

• {BDE}+ = BDE
• {BEF}+ = BEFD
• {DEF}+ = DEF

Alltså inga nya nycklar, men vi måste även testa den enda möjliga fyr-attributskombinationen som innehåller E men varken A eller C:

• {BDEF}+ = BDEF

Så, det visar sig att AE och CE är våra enda nycklar.

Uppgift: Visa att relationen ovan inte är i BCNF.

Lösning: Vi är inte i BCNF, eftersom fd1, fd2 och fd4 har vänsterled som inte är supernycklar – däremot är fd3 OK, CE är en supernyckel (den är till och med en nyckel, men en supernyckel räcker).

Uppgift: Normalisera relationen ovan till BCNF, på ett sätt som gör att vi kan rekonstruera ursprungstabellen, utan tillägg eller förluster. Lösningar som inte bygger på 'receptet' från föreläsning 7-8 ger inga poäng.

Lösning: Poängerna med den normalisering till BCNF som vi behandlar under föreläsning 7-8 är:

• att vi får ett antal tabeller utan redundans beroende på funktionella beroenden, och
• att vi kan join-a ihop tabellerna igen, till precis samma rader som vi hade från början.

Att bara skriva upp ett antal relationer som var och en är i BCNF visar inte att vi kan återskapa ursprungstabellen utan förvrängning, så man får inga poäng om man inte följer 'receptet'.

Vi utgår alltså från R(A,B,C,D,E,F) och de funktionella beroenden som vi såg ovan. När vi skall normalisera är det lämpligt att börja med att utveckla det transitiva höljet av respektive beroende, annars måste vi göra det upprepade gånger i efterföljande steg, och då är det lätt att missa något. Observera att vi i detta fall, utöver beroendena fd1 … fd4, faktiskt har hittat ett beroende till: eftersom AE är en nyckel gäller det funktionella beroendet AE -> BCDF (om vi inte skriver ut det här kommer vi ändå att kunna härleda det via A -> CDF och CE -> ABDF, men det är enklare att ha det med från början):

• fd1: A -> CDF
• fd2: C -> ADF
• fd3: CE -> ABDF
• fd4: F -> D
• fd5: AE -> BCDF

Våra nycklar är dem vi fann ovan, och vi kan sammanställa det som:

R(A,B,C,D,E,F)
--------------
fds: A -> CDF, C -> ADF, CE -> ABDF, F -> D, AE -> BCDF
keys: AE, CE

Vi skall bryta upp på ett funktionellt beroende som bryter mot BCNF – vi gör det för att dess vänsterled kan förekomma flera gånger i tabellen, och att dess högerled kommer att upprepas varje gång (att bryta upp på ett beroende som är i BCNF, dvs har ett vänsterled som är en supernyckel, visar att man inte har förstått idén bakom normaliseringen – vi vill undvika redundans, men för ett beroende med en supernyckel i vänsterledet kan varje vänsterled bara förekomma en gång, och då får vi ingen redundans).

Vi kan exempelvis välja beroendet A -> CDF, som ju har ett vänsterled som inte är en supernyckel, och får då:

• en tabell med alla attributen i det valda funktionella beroendet: R1(A,C,D,F), och
• en tabell med allt utom högerledet i det valda funktionella beroendet: R2(A,B,E) – observera att vänsterledet i vårt funktionella beroende måste finnas kvar, eftersom vi behöver det för att 'joina' in attributen i dess högerled från tabellen R1.

I tabellen R1 har vi kvar beroendena A -> CDF, C -> ADF och F -> D, men de andra två beroenden vi hade försvinner, eftersom vi inte längre har hela deras vänsterled (observera att vi måste ha samtliga attribut i vänsterledet för att ett beroende skall gälla):

R1(A,C,D,F)
--------------
fds: A -> CDF, C -> ADF, F -> D
keys: A, C

I tabellen R2 har vi kvar vänsterledet i några av de beroenden vi hade ovan, men om inget av attributen i högerledet finns kvar så 'försvinner' beroendet (så A -> CDF och C -> ADF försvinner). För AE -> BCDF har vi kvar hela vänsterledet, men bara en del av högerledet – eftersom vi har hela vänsterledet kommer de delar av högerledet som återstår att gälla, alltså har vi beroendet AE -> B:

R2(A,B,E)
--------------
fds: AE -> B
keys: AE

Uppdelningarna kan vi göra med med dessa SQL-satser (detta behövde ni inte göra på tentan denna gång, men vi kommer troligen att ha det på framtida tentor):

CREATE TABLE R1 AS
  SELECT DISTINCT A,C,D,F
  FROM   R;
CREATE INDEX r1key ON R1a(A);

CREATE TABLE R2 AS
  SELECT DISTINCT A,B,E
  FROM   R;
CREATE INDEX r2key ON R2(A,E);

Vi gör SELECT DISTINCT eftersom vi i våra redundanta tabeller kan ha fått upprepningar (beroende på att vi inte var i BCNF).

Här är R2 redan i BCNF, eftersom det enda funktionella beroendet har ett vänsterled som är en supernyckel, men vi måste jobba vidare med R1, som ju har beroendet F -> D, vars vänsterled inte är en supernyckel.

Vi bryter därför ut F -> D till en ny relation R1a(F,D) och kvar från R1 har vi då R1b(A,C,F):

R1a(F,D)
--------------
fds: F -> D
keys: F

och

R1b(A,C,F)
--------------
fds: A -> CF, C -> AF
keys: A, C

Båda dessa tabeller är i BCNF, eftersom deras funktionella beroenden har supernycklar i vänsterleden.

Uppdelningen kan göras med SQL-satserna:

CREATE TABLE R1a AS
  SELECT DISTINCT F,D
  FROM   R1;
CREATE INDEX r1aKey ON R1a(F);

CREATE TABLE R1b AS
  SELECT DISTINCT A,C,F
  FROM   R1;
CREATE INDEX r1bKey ON R1b(A);

Så, vi kan alltså bryta upp i de tre relationerna:

• R2(A,B,E)
• R1b(A,C,F)
• R1a(F,D)

och sättet vi brutit upp på garanterar att vi kan slå ihop dem till ursprungstabellen ovan, utan att tappa rader, eller få nya rader (se nästa deluppgift).

Det finns alternativa lösningar, eftersom vi kan välja att börja bryta upp på något annat av våra BCNF-brytande beroenden – en ganska vanlig lösning på tentan var att börja med att bryta ut F -> D.

Vi utgår då återigen från:

R(A,B,C,D,E,F)
--------------
fds: A -> CDF, C -> ADF, CE -> ABDF, F -> D, AE -> BCDF
keys: AE, CE

och får nu:

R1(F,D)
--------------
fds: F -> D
keys: F

och

R2(A,B,C,E,F)
--------------
fds: A -> CF, C -> AF, CE -> ABF, AE -> BCF
keys: AE, CE

Här är R1 i BCNF, eftersom vänsterledet i F -> D är en supernyckel, men för R2 bryter både A -> CF och C -> AF mot BCNF – om vi väljer att bryta upp på A -> CF så får vi:

R2a(A,C,F)
--------------
fds: A -> CF, C -> AF
keys: A, C

och

R2b(A,B,E)
--------------
fds: AE -> B
keys: AE

Båda dessa är i BCNF, eftersom det inte finns något beroende vars vänsterled inte är en supernyckel.

Våra tre relationer här blir:

• R1(F,D)
• R2a(A,C,F)
• R2b(A,B,E)

vilket faktiskt är samma relationer som vi fick ovan (bortsett från namnen på relationerna) – olika val av beroenden att bryta upp på i de olika stegen kan ge olika slut-relationer, men med den metod vi använt kan vi alltid vara säkra på att vi kan återskapa ursprungsrelationen utan att tappa något, eller få något extra.

Uppgift: Skriv SQL-satser för att rekonstruera den ursprungliga tabellen ovan ur de BCNF-tabeller du kom fram till.

Lösning: Vi kan enkelt bygga tillbaka ursprungsrelationen R – om vi använder den första uppdelningen ovan:

• R2(A,B,E) (detta är resultatet efter att vi tog bort A -> CDF från R) – vi kan joina ihop den med återstoden med hjälp av join-predikatet A
• R1b(A,C,F) (detta är återstoden efter att vi först skapade R1(A,C,D,F) och sedan tog bort F -> D), vi kan joina in D med hjälp av join-predikatet F
• R1a(F,D)

så får vi:

SELECT    *
FROM      R2
          JOIN R1b USING (A)
          JOIN R1a USING (F)