EDAF75 - lösningsförslag till tentamen i mars 2023

Som vanligt kan man lösa uppgiften på lite olika sätt, men vi ville ha något i stil med:

Ett sätt att rita detta ER-diagram är:

Vi kan även ta bort våra 'invented keys' (eftersom de egentligen är en implementationsdetalj), och rita något i stil med:

Som vanligt kan man rita associationsklasserna som 'vanliga' klasser mellan de två klasser som de nu binder samman, med *-1 på vardera sidan.

Det går även bra att låta Sale associera till både Item och Store, istället för att använda Offer (som ovan) – resultatet skulle i slutändan nästan bli detsamma (det som i detta fall skulle vara två separata främmande nycklar skulle motsvara den sammansatta nyckeln till Offer i figuren ovan).

Skriv ut namn och adress för alla kunder som inte köpt någon vara under 2022. TIPS: man kan få årtalet för ett datum med hjälp av standardfunktionen year.

SELECT  name, address
FROM    customers
WHERE   customer_id NOT IN (
        SELECT  customer_id
        FROM    sales
        WHERE   year(sales_date) = 2022);

Egentligen finns det ingen year-funktion i SQLite (jag bara hittade på den för att göra uppgiften lättare), men vi kan använda den lite krångligare strftime:

SELECT  name, address
FROM    customers
WHERE   customer_id NOT IN (
        SELECT  customer_id
        FROM    sales
        WHERE   strftime('%Y', sales_date) = '2022');

Man kan även bara läsa datumet som en sträng, så sales_date LIKE "2022%" fungerar fint.

Skriv ut antalet affärer som säljer varor med ett item_id som börjar på ’EF’.

Ett problem här är att vi inte vill räkna någon butik mer än en gång, så lösningen:

SELECT  count(shop_id)
FROM    offers
WHERE   item_id LIKE 'EF%';

fungerar inte riktigt (men den ger ändå en del poäng).

Ett elegant sätt att lösa problemet med att butiker kan ha flera olika varor som börjar på EF, och bara räkna varje butik en gång, är:

SELECT  count(DISTINCT shop_id)
FROM    offers
WHERE   item_id LIKE 'EF%';

Man kan även använda en subquery:

SELECT  count()
FROM    shops
WHERE   shop_id IN (
    SELECT DISTINCT shop_id
    FROM   offers
    WHERE  item_id LIKE 'EF%');

(här behöver man egentligen inte använda DISTINCT inne i subqueryn, men det känns naturligt).

Ganska många har använt GROUP BY shop_id, vilket är en fiffig idé, eftersom den gör att vi får en rad per butik. Problemet är att count() i detta fall inte räknar antalet rader i tabellen, utan istället räknar antalet rader i varje grupp – men vi kommer att rätta detta fel väldigt snällt (man får bara ett litet avdrag).

Skriv ut namn och adress för den affär (eller de affärer) som säljer varan med item_id = ’EF123-A’ till lägst pris.

SELECT   name, address
FROM     offers
         JOIN shops USING (shop_id)
WHERE    item_id = 'EF123-A' AND
         price = (SELECT min(price)
                  FROM   offers
                  WHERE  item_id = 'EF123-A');

För alla kunder som handlat för minst 1000 kronor: skriv ut kund-id, namn och totalsumman för alla inköp, sortera efter minskande totalsumma.

SELECT    customer_id, name, address, sum(price) AS total_price
FROM      sales
          JOIN offers USING (shop_id, item_id)
          JOIN customers USING (customer_id)
GROUP BY  customer_id
HAVING    total_price >= 1000
ORDER BY  total_price DESC;

Vi får följande funktionella beroenden:

• stil_id -> name
• stil_id lab_no -> group_no
• lab_no group_no -> status

Vi har alltså:

• R(A,B,C,D,E,F)

och:

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

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

Så, 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.

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 nyckel).

Hela poängen med normaliseringen är att vi får ett antal tabeller som vi kan join-a ihop igen, till precis samma rader som vi hade från början. Och det är det som är poängen med den metod att normalisera som vi diskuterade under föreläsning 7-8 – 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.

Vi kan nu 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)