Databasteknik: Lösningar till tentamen 2018-05-28

Observera att detta är förslag på lösningar. Det kan finnas andra lösningar som också är korrekta. Det kan hända att en del av lösningarna är mer omfattande än vad som krävs för full poäng på uppgiften, eller att de bara hänvisar till var man kan läsa svaren. Dessutom har det inträffat i världshistorien att lärare skrivit fel i lösningsförslagen. Jag har förstås aldrig gjort det, men andra. Är det verkligen någon som läser såna här inledande texter? Jag vet inte. Det kan vara så. Rabarber rabarber rabarber. Det har jag hört att statisterna får säga på filminspelningar när det ska vara bakgrundssorl från en restaurang eller liknande. Här nedan kommer lösningsförslagen till uppgifterna.

Uppgift 1 (5 p)

En kommentar: ER-diagrammet visar en historisk databas, där vi sparar alla teportioner och bryggningar. Om man i stället vill ha en snapshot-databas, skulle varje tekopp bara användas till en enda teportion, och varje tekanna bara användas till en enda bryggning. Men hur löser man då att en teportion kan innehålla te från två olika bryggningar, som båda gjorts i samma tekanna? Kanske måste man ändå spara alla bryggningar, åtminstone alla som fortfarande har te i någon kopp? En del av sökningarna i uppgift 3 verkar också kräva en historisk databas, för hur kan man annars veta till exempel vilka kannor som någonsin innehållit Bolmörtsblandning?

Uppgift 2 (6 p)

Koppar(Nummer, Volym)
Kannor(Nummer, Volym)
Sorter(Namn)
Bryggningar(Nummer, Datum, Sort, Kanna)
Portioner(Nummer, Kopp)
Bryggning_I_Portion(Bryggning, Portion)

Primärnycklarna är understrukna.

Främmande nycklar:

Bryggning.Sort till Sorter.Namn
Bryggning.Kanna till Kannor.Nummer
Portioner.Kopp till Koppar.Nummer
Bryggning_I_Portion.Bryggning till Bryggning.Nummer
Bryggning_I_Portion.Portion till Portioner.Nummer

En kommentar: Man kan, om man vill, skapa en surrogatnyckel för tesorter.

Nedan visas create table-kommandon och exempeldata, för att underlätta provkörningar.

DROP TABLE Koppar;
DROP TABLE Kannor;
DROP TABLE Sorter;
DROP TABLE Bryggningar;
DROP TABLE Portioner;
DROP TABLE Bryggning_I_Portion;

CREATE TABLE Koppar
(Nummer INTEGER NOT NULL PRIMARY KEY,
Volym FLOAT NOT NULL);

CREATE TABLE Kannor
(Nummer INTEGER NOT NULL PRIMARY KEY,
Volym FLOAT NOT NULL);

CREATE TABLE Sorter
(Namn NVARCHAR(50) NOT NULL PRIMARY KEY);

CREATE TABLE Bryggningar
(Nummer INTEGER NOT NULL PRIMARY KEY,
Datum DATE NOT NULL,
Sort NVARCHAR(50) NOT NULL REFERENCES Sorter(Namn),
Kanna INTEGER NOT NULL REFERENCES Kannor(Nummer));

CREATE TABLE Portioner
(Nummer INTEGER NOT NULL PRIMARY KEY,
Kopp INTEGER NOT NULL REFERENCES Koppar(Nummer));

CREATE TABLE Bryggning_I_Portion
(Bryggning INTEGER NOT NULL REFERENCES Bryggningar(Nummer),
Portion INTEGER NOT NULL REFERENCES Portioner(Nummer),
PRIMARY KEY(Bryggning, Portion));

INSERT INTO Koppar (Nummer, Volym) VALUES (1, 0.4);
INSERT INTO Koppar (Nummer, Volym) VALUES (2, 0.5);
INSERT INTO Koppar (Nummer, Volym) VALUES (3, 0.6);
INSERT INTO Koppar (Nummer, Volym) VALUES (4, 0.7);

INSERT INTO Kannor (Nummer, Volym) VALUES (1, 1);
INSERT INTO Kannor (Nummer, Volym) VALUES (2, 2);
INSERT INTO Kannor (Nummer, Volym) VALUES (3, 3);
INSERT INTO Kannor (Nummer, Volym) VALUES (4, 4);

INSERT INTO Sorter (Namn) VALUES ('Söderblandning');
INSERT INTO Sorter (Namn) VALUES ('Döderblandning');
INSERT INTO Sorter (Namn) VALUES ('Bolmörtsblandning');
INSERT INTO Sorter (Namn) VALUES ('Gray Horror');
INSERT INTO Sorter (Namn) VALUES ('Grey Terror');
INSERT INTO Sorter (Namn) VALUES ('Stingray Bite');

INSERT INTO Bryggningar (Nummer, Datum, Sort, Kanna)
  VALUES (1, DATE '2018-05-27', 'Söderblandning', 1);
INSERT INTO Bryggningar (Nummer, Datum, Sort, Kanna)
  VALUES (2, DATE '2018-05-27', 'Döderblandning', 1);
INSERT INTO Bryggningar (Nummer, Datum, Sort, Kanna)
  VALUES (3, DATE '2018-05-27', 'Bolmörtsblandning', 1);
INSERT INTO Bryggningar (Nummer, Datum, Sort, Kanna)
  VALUES (4, DATE '2018-05-27', 'Bolmörtsblandning', 2);
INSERT INTO Bryggningar (Nummer, Datum, Sort, Kanna)
  VALUES (5, DATE '2018-05-27', 'Söderblandning', 3);

INSERT INTO Portioner (Nummer, Kopp) VALUES (1, 1);
INSERT INTO Portioner (Nummer, Kopp) VALUES (2, 1);
INSERT INTO Portioner (Nummer, Kopp) VALUES (3, 1);
INSERT INTO Portioner (Nummer, Kopp) VALUES (4711, 1);

INSERT INTO Bryggning_I_Portion(Bryggning, Portion) VALUES (1, 1);
INSERT INTO Bryggning_I_Portion(Bryggning, Portion) VALUES (1, 2);
INSERT INTO Bryggning_I_Portion(Bryggning, Portion) VALUES (1, 3);
INSERT INTO Bryggning_I_Portion(Bryggning, Portion) VALUES (2, 1);
INSERT INTO Bryggning_I_Portion(Bryggning, Portion) VALUES (2, 2);
INSERT INTO Bryggning_I_Portion(Bryggning, Portion) VALUES (2, 3);
INSERT INTO Bryggning_I_Portion(Bryggning, Portion) VALUES (1, 4711);
INSERT INTO Bryggning_I_Portion(Bryggning, Portion) VALUES (2, 4711);

SELECT * FROM Koppar;
SELECT * FROM Kannor;
SELECT * FROM Sorter;
SELECT * FROM Bryggningar;
SELECT * FROM Portioner;
SELECT * FROM Bryggning_I_Portion;

Uppgift 3 (11 p)

a) (1p) Vi behöver en stor tekopp! Vad är numren på de tekoppar som har större volym än en halv liter?

SELECT Nummer
FROM Koppar
WHERE Volym > 0.5;

b) (1p) Det finns en tesort som heter Earl Grey. Eller ska den kanske stavas Earl Gray? Visa alla namn på tesorter som innehåller Grey eller Gray!

SELECT Namn
FROM Sorter
WHERE Namn LIKE '%Grey%' OR Namn LIKE '%Gray%';

c) (2p) Det visar sig att tesorten Bolmörtsblandning är giftig, och alla tekannor som någonsin innehållit den sortens te måste kasseras. Vad är numren på de tekannor som vi bryggt den tesorten i?

SELECT DISTINCT Kanna
FROM Bryggningar
WHERE Sort = 'Bolmörtsblandning';

d) (2p) Här har jag en kopp med te. Den har nummer 4711. Vilka sorters te innehåller den? Vi vill veta namnen på tesorterna.

SELECT DISTINCT Sort
FROM Bryggningar
WHERE Nummer IN (SELECT Bryggning
                 FROM Bryggning_I_Portion
                 WHERE Portion = 4711);

Två alternativa sätt:

SELECT DISTINCT Bryggningar.Sort
FROM Bryggningar, Bryggning_I_Portion
WHERE Bryggningar.Nummer = Bryggning_I_Portion.Bryggning
AND Bryggning_I_Portion.Portion = 4711;

SELECT DISTINCT Bryggningar.Sort
FROM Bryggningar JOIN Bryggning_I_Portion ON Bryggningar.Nummer = Bryggning_I_Portion.Bryggning
WHERE Bryggning_I_Portion.Portion = 4711;

e) (2p) Vilka tesorter som finns med i databasen har vi ännu inte bryggt te med? Vi vill veta namnen på de tesorterna.

SELECT Namn
FROM Sorter
WHERE Namn NOT IN (SELECT Sort
                   FROM Bryggningar);

f) (3p) Vilken tekanna har använts flest gånger?

CREATE VIEW AntalBryggningarIVarjeKanna AS
SELECT Kanna, COUNT(*) AS Antal
FROM Bryggningar
GROUP BY Kanna;

SELECT * FROM AntalBryggningarIVarjeKanna;

SELECT Kanna
FROM AntalBryggningarIVarjeKanna
WHERE Antal IN (SELECT MAX(Antal)
                FROM AntalBryggningarIVarjeKanna);

Eller, med en CTE:

WITH AntalBryggningarIVarjeKanna AS
(SELECT Kanna, COUNT(*) AS Antal
FROM Bryggningar
GROUP BY Kanna)
SELECT Kanna
FROM AntalBryggningarIVarjeKanna
WHERE Antal IN (SELECT MAX(Antal)
                FROM AntalBryggningarIVarjeKanna);

Uppgift 4 (3 p)

Med databasen i lösningsförslaget ovan är det enkelt. Skapa bara ett index på Bryggningar.Sort:

CREATE INDEX Sortindex ON Bryggningar(Sort);

Störst nytta har man av index när man kombinerar flera tabeller, och när man söker efter bestämda värden i en stor tabell, så detta index gör förmodligen inte så stor prestandaförbättring.

Dessutom innehåller databasen så lite data ("många tusen rader"), att det nog inte märks att det går snabbare, för en enskild fråga.

Uppgift 5 (3 p)

Fråga 1:

nummer	färg
1	gul

Fråga 2:

nummer	färg
1	gul

Fråga 3:

nummer	färg
1	gul

Fråga 4:

nummer	färg
1	gul

Fråga 5:

nummer	färg
1	gul
2	gul

Fråga 6:

nummer	färg
1	gul
2	gul

Fråga 7:

nummer	färg
1	gul
2	gul

Fråga 8:

nummer	färg
1	gul
2	gul
3	gul

Fråga 9:

nummer	färg
1	gul
2	gul

Fråga 10:

nummer	färg
1	gul
2	gul

Uppgift 6 (3 p)

Några av de vanligaste databashanterarna:

Microsoft SQL Server är en stor och avancerad databashanterare, som (i de flesta versionerna) kostar pengar. Till skillnad från de flesta andra databashanterare fungerar den bara på Windows (och, i en tillsvidare ganska oprövad version, på Linux). Kan hantera mycket stora datamängder.
Microsoft Access är en ganska liten och enkel databashanterare, men med ett avancerat grafisk gränssnitt. Kostar pengar. Till skillnad från de flesta andra databashanterare fungerar den bara på Windows. Har problem med att hantera stora datamängder.
Oracle är en stor och avancerad databashanterare, som (i de flesta versionerna) kostar pengar. Kan hantera mycket stora datamängder.
SQLite är en liten och enkel databashanterare, som är open source och gratis.
Mimer är inte så spridd som de andra, och det är fortfarande ett svenskt företag. Dess utmärkande egenskap är att den försöker följa SQL-standarden.
MySQL utvecklades från början i Sverige. Finns både som gratisversion med open source och i versioner som kostar pengar. Var från början ganska enkel, men har utvecklats till att innehålla mer funktionalitet. Kan hantera mycket stora datamängder.

Uppgift 7 (3 p)

B-träd är alltid balanserade, så alla lövnoder befinner sig på samma nivå. Binära träd finns både i versioner som balanseras automatiskt, och i helt obalanserade versioner.

Men den stora skillnaden är ordningen, dvs hur många underträd en nod maximalt kan ha. Medan ett binärt träd bara har plats för högst två underträd under varje nod ("binär" betyder ju två), kan ett B-träd ha plats för betydligt fler underträd, kanske flera hundra. Det gör att B-trädet blir mycket lägre än ett binärt träd, så man behöver besöka färre noder för att hitta de data man söker. Exempelvis innehåller ett binärt träd med en miljon noder minst tjugo nivåer, medan ett B-träd av ordningen 100 behöver ungefär fyra nivåer för en miljon noder.

Eftersom B-träd av hög ordning är så låga, jämfört med binära träd, behöver man besöka färre noder vid en sökning. Å andra sidan är det mer arbete att göra i varje nod, med fler jämförelser. I en datastruktur i primärminne kan det gå på ett ut. Men vanliga databaser är sekundärminnesbaserade, och data lagras på hårddisk eller SSD. Både från hårddiskar och SSD:er läser man data i ganska stora block, och en sådan läsning är mycket långsam jämfört med åtkomst av primärminnet. Man tjänar inget på att läsa en mindre datamängd än ett helt block. Eftersom arbetet i en nod sker när den väl är inläst till primärminnet, kan det ofta försummas jämfört med tiden att läsa från det långsamma sekundärminnet, och man vill bara minimera antalet läsningar från sekundärminnet.

Notera att sökning i ett B-träd av exempelvis ordning 100 (med upp till 100 underträd under varje nod) har samma tidskomplexitet som sökning i ett balanserat binärt träd (som har ordning 2), nämligen O(log n). Det är bara en konstant faktor som skiljer. (Jämför med att en algoritm som alltid tar 1 sekund och en som alltid tar 1000 år båda har tidskomplexiteten O(1). Även där är det bara en konstant faktor som skiljer!)

Uppgift 8 (3 p)

Relationsdatabaser och frågespråket SQL är mängdorienterade, och arbetar med hela tabeller på en gång. Vanliga programmeringsspråk är värdeorienterade, och arbetar med ett värde i taget. Ska man gå igenom innehållet i en tabell i ett vanligt programmeringsspråk, måste man använda en loop (eller kanske en mappningsmekanism, som döljer loopen).

I databassammanhang är en cursor en sorts pekare som anger vilken rad i en tabell (antingen en lagrad tabell eller resultatet av en sökning), som man för tillfället befinner sig på, när man hanterar datat med ett vanligt programmeringsspråk.

Genom att stega fram cursorn rad för rad i en loop kan ett program arbeta sig igenom resultatet, ungefär som när man läser från en fil.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 16 juni 2018