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

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:

Skriv ut titel och förlag för de böcker som är utlånade för tillfället (sorterat efter titel).

SELECT    title, publisher_name
FROM      books
          JOIN loans USING (isbn)
          JOIN publishers USING (publisher_id)
WHERE     actual_return_date IS NULL
ORDER BY  title

Ta bort alla böcker som aldrig varit utlånade.

DELETE
FROM      books
WHERE     isbn NOT IN (
      SELECT isbn
      FROM   loans)

Skriv ut namnet på de låntagare som aldrig lånat en skönlitterär bok (skönlitterära böcker har en klassificering som börjar på 8).

Enklast är nog att använda en sub-query:

SELECT    name
FROM      borrowers
WHERE     card_nbr NOT IN (
    SELECT    card_nbr, true
    FROM      loans
              JOIN books USING (isbn)
    WHERE     classification LIKE '8%')

Vi kan även göra det med hjälp av en outer join, men måste då trixa lite för att få ett extra attribut som vi kan testa på efteråt:

WITH
  readers_of_fiction(card_nbr, found) AS (
    SELECT DISTINCT card_nbr, true
    FROM            loans
                    JOIN books USING (isbn)
    WHERE           classification LIKE '8%'
  )
SELECT    name
FROM      borrowers
          LEFT JOIN readers_of_fiction USING (card_nbr)
WHERE     found IS NULL

Skriv ut namnen på de låntagare som vid något tillfälle har lånat någon bok med fransk poesi som är publicerad av förlaget med namnet ”ACME böcker” – texten ”Fransk poesi” finns som en beskrivning (description) i tabellen classifications.

SELECT   name
FROM     borrowers
WHERE    card_nbr IN (
    SELECT    card_nbr
    FROM      loans
              JOIN books USING (isbn)
              JOIN classifications USING (classification)
              JOIN publishers USING (publisher_id)
    WHERE     description = 'Fransk poesi' AND
              publisher_name = 'ACME böcker')

Skriv för de olika förlagen ut hur många av deras skönlitterära böcker biblioteket har i sin databas – vi vill dock bara ha med förlag med minst 10 sådana böcker (skönlitterära böcker har en klassificering som börjar på 8).

SELECT    publisher_name, count(isbn)
FROM      books
          JOIN publishers USING (isbn)
WHERE     classification LIKE '8%'
GROUP BY  publisher_id
HAVING    count(isbn) >= 10

Vi hade:

• actor_id
• actor_name
• movie_id
• movie_role
• category
• year

och får följande funktionella beroenden:

• actor_id -> actor_name
• actor_id movie_id -> movie_role
• movie_id movie_role -> actor_id
• category year -> movie_id movie_role
• movie_id -> year

Man behöver inte komma på alla dessa för full poäng, man får en poäng för varje, och maximalt fyra poäng på uppgiften.

Vi har alltså:

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

och:

• FD1: ADF -> C
• FD2: D -> EH
• FD3: F -> BG

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: ADF -> BCEGH
• FD2: D -> EH
• FD3: F -> BG

Det visar sig alltså direkt att ADF är en nyckel (eftersom vi får alla övriga attribut), samtidigt kan vi konstatera att vi aldrig kan härleda någon av attributen A, D eller F, så de måste alla ingå i en nyckel.

Detta innebär att ADF är den enda möjliga nyckeln.

Vi är inte i BCNF, eftersom FD2 och FD3 har vänsterled som inte är supernycklar (däremot är FD1 OK, ADF är en supernyckel).

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,G,H) och de funktionella beroenden som vi såg ovan – för att göra saker enklare kan vi direkt använda de transitiva höljen vi beräknade ovan.

• FD1: ADF -> BCEGH
• FD2: D -> EH
• FD3: F -> BG

Vår enda nyckel är ADF, och vi kan sammanställa det som:

R(A,B,C,D,E,F,G,H)
--------------
fds: ADF -> BCEGH, D -> EH, F -> BG
keys: ADF

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 D -> EH, 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(D,E,H), och
• en tabell med allt utom högerledet i det valda funktionella beroendet: R2(A,B,C,D,F,G) – 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 beroendet D -> EH, men de andra två beroenden vi hade i R 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(D,E,H)
--------------
fds: D -> EH
keys: D

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å D -> EH försvinner). För ADF -> BCEGH 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 ADF -> BCG (plus F -> BG, som inte påverkas av att vi brutit ut E och H):

R2(A,B,C,D,F,G)
--------------
fds: ADF -> BCG, F -> BG
keys: ADF

Uppdelningarna kan vi göra med med dessa SQL-satser (detta behövde ni inte göra på tentan denna gång):

CREATE TABLE R1 AS
  SELECT DISTINCT D,E,H
  FROM   R;
CREATE INDEX r1key ON R1a(D);

CREATE TABLE R2 AS
  SELECT DISTINCT A,B,C,D,F,G
  FROM   R;
CREATE INDEX r2key ON R2(A,D,F);

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

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

Vi bryter därför ut F -> BG till en ny relation R2a(F,B,G) och kvar från R2 har vi då samma symboler som tidigare, utom högerledet i F -> BG, dvs R2b(A,C,D,F):

R2a(F,B,G)
--------------
fds: F -> BG
keys: F

och

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

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:

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

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

Vi kan nu enkelt bygga tillbaka ursprungsrelationen R – om vi använder uppdelningen ovan:

• R2b(A,C,D,F) kan vi först joina ihop med R2a(F,B,G) med hjälp av vänsterledet i D -> EH, som vi bröt upp R2 med.
• Vi kan sedan joina in R1(D,E,H) med hjälp av vänsterledet i D -> EH, som vi bröt upp R med i det första steget.

Så får vi:

SELECT    *
FROM      R2b
          JOIN R2a USING (D)
          JOIN R1 USING (D)