Databasteknik: Lösningar till tentamen 2022-06-01

Uppgift 1 (5 p)

Några kommentarer om lösningen ovan:

Stjärntypen kan göras som en entitetstyp. Ordningsnumret på planeterna kan vara ett attribut på Har-sambandstypen. Man kan också göra planeter som en svag entitetstyp. Det unika numret på utryckningar är inte nödvändigt i ER-diagrammet, men kommer att behövas när man skapar en tabell med utryckningar.

Uppgift 2 (6 p)

Kandidatnycklarna är understrukna. I tabeller med en enda kandidatnyckel är det förstås den som är primärnyckel, och annars är det Nummer som är primärnyckel.

Främmande nycklar:

Planet.Stjärna till Stjärnor.Nummer
Utryckningar.Planet refererar till Planeter.Nummer
Deltar.Utryckning refererar till Utryckningar.Nummer
Deltar.Rymdskepp refererar till Rymdskepp.Nummer

Nedan visas create table-kommandon och exempeldata. Det krävs inte som svar, men är med för att underlätta provkörningar.

CREATE TABLE Stjärnor
(Nummer INTEGER NOT NULL PRIMARY KEY,
Namn NVARCHAR(10) NOT NULL UNIQUE,
Typ NVARCHAR(10) NOT NULL);

INSERT INTO Stjärnor VALUES (1, 'Solen', 'Gul sol');
INSERT INTO Stjärnor VALUES (2, 'Betelgeuse', 'Röd jätte');
INSERT INTO Stjärnor VALUES (3, 'Sirius', 'Stjärna');
INSERT INTO Stjärnor VALUES (4, 'Canopus', 'XL-stjärna');

CREATE TABLE Planeter
(Nummer INTEGER NOT NULL PRIMARY KEY,
Namn NVARCHAR(10) NOT NULL UNIQUE,
Stjärna INTEGER NOT NULL REFERENCES Stjärnor (Nummer),
Ordningsnummer INTEGER NOT NULL,
UNIQUE (Stjärna, Ordningsnummer));

INSERT INTO Planeter VALUES (1, 'Merkurius', 1, 1);
INSERT INTO Planeter VALUES (2, 'Venus', 1, 2);
INSERT INTO Planeter VALUES (3, 'Jorden', 1, 3);
INSERT INTO Planeter VALUES (4, 'Mars', 1, 4);
INSERT INTO Planeter VALUES (5, 'B-5', 2, 17);

CREATE TABLE Rymdskepp
(Nummer INTEGER NOT NULL PRIMARY KEY,
Namn NVARCHAR(10) NOT NULL UNIQUE,
Vikt INTEGER NOT NULL);

INSERT INTO Rymdskepp VALUES (1, 'Doom', 1000);
INSERT INTO Rymdskepp VALUES (2, 'Doom-doom', 1000);
INSERT INTO Rymdskepp VALUES (3, 'Doomer', 2000);
INSERT INTO Rymdskepp VALUES (4, 'Super-doom', 3000);
INSERT INTO Rymdskepp VALUES (5, 'Ultra-doom', 1000);

CREATE TABLE Utryckningar
(Nummer INTEGER NOT NULL PRIMARY KEY,
Datum DATE NOT NULL,
Tid TIME NOT NULL,
Planet INTEGER NOT NULL REFERENCES Planeter (Nummer),
Beskrivning NVARCHAR(10) NOT NULL);

INSERT INTO Utryckningar VALUES (1, DATE '2023-06-01', TIME '12:00:00', 4, 'Upplopp');
INSERT INTO Utryckningar VALUES (2, DATE '2023-06-01', TIME '13:00:00', 4, 'Upplopp');
INSERT INTO Utryckningar VALUES (3, DATE '2023-06-01', TIME '14:00:00', 2, 'Bråk');
INSERT INTO Utryckningar VALUES (4, DATE '2023-06-02', TIME '12:00:00', 2, 'Upplopp');
INSERT INTO Utryckningar VALUES (5, DATE '2023-06-03', TIME '13:00:00', 4, 'Klotter');

CREATE TABLE Deltar
(Utryckning INTEGER NOT NULL REFERENCES Utryckningar (Nummer),
Rymdskepp INTEGER NOT NULL REFERENCES Rymdskepp (Nummer),
PRIMARY KEY (Utryckning, Rymdskepp));

INSERT INTO Deltar VALUES (1, 1);
INSERT INTO Deltar VALUES (1, 2);
INSERT INTO Deltar VALUES (2, 1);
INSERT INTO Deltar VALUES (3, 2);
INSERT INTO Deltar VALUES (4, 1);
INSERT INTO Deltar VALUES (4, 2);
INSERT INTO Deltar VALUES (4, 3);
INSERT INTO Deltar VALUES (4, 4);
INSERT INTO Deltar VALUES (5, 4);

SELECT * FROM Stjärnor;
SELECT * FROM Planeter;
SELECT * FROM Rymdskepp;
SELECT * FROM Utryckningar;
SELECT * FROM Deltar;

Primärnyckeln i tabellen Deltar är sammansatt av båda kolumnerna, och i tabellen Planeter är kombinationen av Stjärna och Ordningsnummer en kandidatnyckel, men det gick inte att göra ett streck under båda kolumnamnen i HTML.

Uppgift 3 (10 p)

SELECT Stjärnor.Namn
FROM Planeter, Stjärnor
WHERE Planeter.Stjärna = Stjärnor.Nummer
AND Planeter.Namn = 'B-5';

SELECT Stjärnor.Namn
FROM Planeter JOIN Stjärnor ON Planeter.Stjärna = Stjärnor.Nummer
WHERE Planeter.Namn = 'B-5';

SELECT Namn
FROM Stjärnor
WHERE Nummer IN (SELECT Stjärna
                 FROM Planeter
                 WHERE Namn = 'B-5');

b) (2p) Vad heter det tyngsta rymdskeppet?

SELECT Namn
FROM Rymdskepp
WHERE Vikt IN (SELECT MAX(Vikt) FROM Rymdskepp);

SELECT Namn
FROM Rymdskepp
ORDER BY Vikt DESC
FETCH FIRST 1;

SELECT Namn
FROM Rymdskepp
ORDER BY Vikt DESC
LIMIT 1;

SELECT TOP 1 Namn
FROM Rymdskepp
ORDER BY Vikt DESC;

c) (2p) Vad heter de planeter som rymdskeppet Doomhammer of Doom ryckt ut till?

SELECT DISTINCT Planeter.Namn
FROM Planeter, Utryckningar, Deltar, Rymdskepp
WHERE Planeter.Nummer = Utryckningar.Planet
AND Utryckningar.Nummer = Deltar.Utryckning
AND Deltar.Rymdskepp = Rymdskepp.Nummer
AND Rymdskepp.Namn = 'Doomhammer of Doom';

SELECT DISTINCT Planeter.Namn
FROM Planeter JOIN Utryckningar ON Planeter.Nummer = Utryckningar.Planet
              JOIN Deltar ON Utryckningar.Nummer = Deltar.Utryckning
              JOIN Rymdskepp ON Deltar.Rymdskepp = Rymdskepp.Nummer
WHERE Rymdskepp.Namn = 'Doomhammer of Doom';

SELECT Namn
FROM Planeter
WHERE Nummer IN (SELECT Planet
                 FROM Utryckningar
                 WHERE Nummer IN (SELECT Utryckning
                                  FROM Deltar
                                  WHERE Rymdskepp IN (SELECT Nummer
                                                      FROM Rymdskepp
                                                      WHERE Namn = 'Doomhammer of Doom')));

d) (2p) Vilka av rymdskeppen har aldrig åkt på utryckningar? Vi vill veta deras nummer och namn.

SELECT Namn
FROM Rymdskepp
WHERE Nummer NOT IN (SELECT Rymdskepp FROM Deltar);

SELECT Rymdskepp.Namn
FROM Rymdskepp LEFT JOIN Deltar ON Rymdskepp.Nummer = Deltar.Rymdskepp
WHERE Deltar.Rymdskepp IS NULL;

e) (3p) Vad heter den planet som det har varit flest utryckningar till?

CREATE VIEW AntalUtryckningar AS
SELECT Planeter.Nummer AS Planetnummer, Planeter.Namn AS Planetnamn, COUNT(*) As Antal
FROM Utryckningar, Planeter
WHERE Planeter.Nummer = Utryckningar.Planet
GROUP BY Planeter.Nummer, Planeter.Namn;

SELECT Planetnamn
FROM AntalUtryckningar
WHERE Antal IN (SELECT MAX(Antal) FROM AntalUtryckningar);

CREATE VIEW AntalUtryckningar AS
SELECT Planet AS Planetnummer, COUNT(*) As Antal
FROM Utryckningar
GROUP BY Planet;

SELECT Namn
FROM Planeter
WHERE Nummer IN (SELECT Planetnummer
                 FROM AntalUtryckningar
                 WHERE Antal IN (SELECT MAX(Antal) FROM AntalUtryckningar));

WITH AntalUtryckningar AS
(SELECT Planeter.Nummer AS Planetnummer, Planeter.Namn AS Planetnamn, COUNT(*) As Antal
FROM Utryckningar, Planeter
WHERE Planeter.Nummer = Utryckningar.Planet
GROUP BY Planeter.Nummer, Planeter.Namn)
SELECT Planetnamn
FROM AntalUtryckningar
WHERE Antal IN (SELECT MAX(Antal) FROM AntalUtryckningar);

Uppgift 4 (3 p)

• Deltar.Rymdskepp
• Deltar.Utryckning (men inget poängavdrag om den inte är med)
• Planeter.Namn
• Planeter.Nummer
• Planeter.Stjärna (men inget poängavdrag om den inte är med)
• Rymdskepp.Namn
• Rymdskepp.Nummer (men inget poängavdrag om den inte är med)
• Rymdskepp.Vikt
• Stjärnor.Nummer
• Utryckningar.Nummer
• Utryckningar.Planet (men inget poängavdrag om den inte är med)

Uppgift 5 (3 p)

Om konsistensbevarande (C) saknas: Man kanske lägger till en utryckning med samma nummer som en som redan fanns i tabellen Utryckninger. Då är primärnyckeln plötsligt inte unik längre. Eller så tar man bort en utryckning, men tar inte bort raderna i tabellen Deltar som handlar om den utryckningen. Då är referensintegriteten bruten, och det står i databasen att rymdskepp har deltagit i en utryckning som inte finns.

Om isolering (I) saknas: Två utryckninger har just avslutats och ska läggas in i databasen: en utryckning där rymdskepp 1 och 2 deltog, och en där rymdskepp 3 och 4 deltog. Två olika rymdpoliser sitter vid varsin dator och lägger in de nya utryckningerna i databasen. Båda rymdpoliserna ser att det högsta numret på en utryckning just nu är 3, så de försöker lägga in utryckning nummer 4. Redan där blir det en krock, men om vi antar att de nöjer sig med en enda, gemensam utryckning nummer 4, så lägger den första forskaren in att rymdskepp 1 och 2 deltog i utryckning 4, och den andra att rymdskepp 3 och 4 också deltog i utryckning 4. Då ser det ut som om det var en utryckning med fyra olika rymdskepp, och inte två olika utryckninger med två rymdskepp vardera.

Om hållbarhet (D) saknas: Ett av rymdpolisens rymdskepp gör en utryckning till planeten Saturnus, och kaptenen lägger in utryckningen i databasen. Men det visar sig att den utryckningen inte har sparats ordentligt, så det syns inte att de någonsin åkte till Saturnus. Därför får besättningen ingen övertidsersättning. (Med dagens teknik tar det åtta år att åka till Saturnus, så rymdpoliserna på skeppet går miste om mycket pengar.)

Uppgift 6 (3 p)

Om vi antar att ett diskblock är 4 kilobyte (4096 byte), att både nycklar och diskblockspekare är 64 bitar (8 byte), och vi använder ett helt diskblock för att lagra en nod i B-trädet, kommer B-trädet att vara av ordning (maximalt antal barn under en nod) (4096-8)/(8+8)+1 = 256. Om noderna är fulla blir antalet nivåer i B-trädet cirka ²⁵⁶log(8000000000) ≈ 4,1. Om vi räknar med att noderna är i genomsnitt 69 procent fulla, får vi en genomsnittlig fan-out från noderna på ¹⁷⁷log(8000000000) ≈ 4,7. Vi avrundar uppåt till 5.

(Det ger inte poängavdrag att bara anta en "typisk" fanout på till exempel 100.)

Med mindre matematik, och en fan-out på 177, kan man i stället räkna så här: Första nivån i B-trädet innehåller rotnoden, andra nivån innehåller 177 noder, tredje nivån innehåller 177² = 31329 noder, fjärde nivån innehåller 177³ = 5545233 noder, och femte nivån innehåller 177⁴ = 981506241 noder, vilket är mer än 8 miljarder. Alltså räcker fem nivåer, och det är så högt trädet blir.

b) Varför är B-träd bra just för databaser?

De flesta (vanliga) databaser är sekundärminnesbaserade (disk eller SSD), för att mycket stora datamängder ska få plats. Sekundärminnen är mycket långsamma jämfört med processorn och primärminnet, så man vill minimera antalet diskläsningar. Sekundärminnet (både disk och SSD) är "blockenheter" ("block devices" på engelska) dvs man läser och skriver alltid data blockvis, i hela block på en halv till några kilobyte. Om man utnyttjar hela blocket för data i en och samma nod, blir trädets ordning hög, så trädet blir brett och lågt, och man behöver läsa färre gånger när man söker i trädet.

Uppgift 7 (7 p)

Både tredje och fjärde raden har värdet 9 i kolumn C men olika värden i kolumn D (9 respektive 5). Om det finns ett ffb C → D måste värdena på D vara lika om värdena på C är lika.

Observera att funktionella beroenden inte är dubbelriktade, så exempelvis ettan i kolumn C på första raden och sjuan i kolumn C på andra raden, där båda raderna har en femma i kolumn D, strider inte mot beroendet C → D.

b) Vilka av normalformerna 1NF, 2NF, 3NF och BCNF uppfyller tabellen? Motivera svaret!

Den uppfyller 1NF men inte de andra.

1NF kräver att tabellen bara får innehålla enkla, atomära värden, dvs inga listor, mängder eller sammansatta värden, och det blir inte så mycket enklare och atomärare än ensiffriga heltal. 2NF förbjuder ffb på en del av en kandidatnyckel, och C → D är ett beroende på en del av den sammansatta kandidatnyckeln som består av B och C. Eftersom tredje 3NF och BCNF är starkare krav än 2NF, är inte heller de uppfyllda.

c) I SQL är det lätt att ange vad som är nycklar, med PRIMARY KEY och UNIQUE, och då kommer databashanteraren att kontrollera att man inte bryter mot nyckelvillkoren. Det finns inget lika enkelt sätt att ange funktionella beroenden. Men man kan söka i databasen efter brott mot funktionella beroenden. Skriv en SQL-fråga som hittar rader i tabellen ovan som bryter mot det fullständiga funktionella beroendet C → D!

SELECT rad1.* FROM Data AS rad1, Data AS rad2
WHERE rad1.C = rad2.C
AND rad1.D != rad2.D;

Uppgift 8 (3 p)

Så fort man lagt in raden i tabellen utlöses triggern ("after insert"), och den hämtar innehållet på raden från den nya raden ("new table"). Därefter tar den bort den raden.

(Ett undantag är om man lägger in null i någon kolumn. Eftersom alla jämförelser med null blir falska, uppfylls inte where-villkoret i delete-satsen.)