Databasteknik: Lösningar till tentamen 2019-06-03

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)

Ett EER-diagram

Uppgift 2 (6 p)

Länder(Nummer, Namn)
Partigrupper(Nummer, Namn)
Partier(Nummer, Namn, Land, Partigrupp)
Val(År)
Deltar(Parti, Val, Röster)

Primärnycklarna är understrukna.

Främmande nycklar:

Partier.Land till Länder.Nummer
Partier.Partigrupp till Partigrupper.Nummer
Deltar.Parti till Partier.Nummer
Deltar.Val till Val.År

En kommentar: Man kan, om man vill, låta bli att skapa surrogatnycklarna Nummer, och använda namnen som primärnycklar. SQL-frågorna blir enklare då.

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

DROP VIEW Partigruppsröster2019;
DROP TABLE Deltar;
DROP TABLE Val;
DROP TABLE Partier;
DROP TABLE Partigrupper;
DROP TABLE Länder;

CREATE TABLE Länder
(Nummer INTEGER NOT NULL PRIMARY KEY,
Namn VARCHAR(20) NOT NULL UNIQUE);

CREATE TABLE Partigrupper
(Nummer INTEGER NOT NULL PRIMARY KEY,
Namn VARCHAR(20) NOT NULL UNIQUE);

CREATE TABLE Partier
(Nummer INTEGER NOT NULL PRIMARY KEY,
Namn VARCHAR(20) NOT NULL UNIQUE,
Land INTEGER NOT NULL REFERENCES Länder(Nummer),
Partigrupp INTEGER REFERENCES Partigrupper(Nummer));

CREATE TABLE Val
(År INTEGER NOT NULL PRIMARY KEY);

CREATE TABLE Deltar
(Parti INTEGER REFERENCES Partier(Nummer),
Val INTEGER REFERENCES Val(År),
Röster INTEGER NOT NULL,
PRIMARY KEY (Parti, Val));

INSERT INTO Länder VALUES (1, 'Sverige');
INSERT INTO Länder VALUES (2, 'Tyskland');
INSERT INTO Länder VALUES (3, 'UK');
INSERT INTO Länder VALUES (4, 'Danmark');

INSERT INTO Partigrupper VALUES (1, 'Stalin-Kommunisterna');
INSERT INTO Partigrupper VALUES (2, 'Ultrahögern');
INSERT INTO Partigrupper VALUES (3, 'Tröttmitten');
INSERT INTO Partigrupper VALUES (4, 'EUNSP');
INSERT INTO Partigrupper VALUES (5, 'EPP');

INSERT INTO Partier VALUES (1, 'Folkpartiet', 1, 5);
INSERT INTO Partier VALUES (2, 'VPK', 1, 1);
INSERT INTO Partier VALUES (3, 'Högern', 1, 2);
INSERT INTO Partier VALUES (4, 'Baader-Meinhof-ligan', 2, 1);
INSERT INTO Partier VALUES (5, 'Alte Kameraden', 2, 2);
INSERT INTO Partier VALUES (6, 'Vi som hatar EU', 3, NULL);
INSERT INTO Partier VALUES (7, 'EUNSP-1', 4, NULL);
INSERT INTO Partier VALUES (8, 'EUNSP-2', 4, 3);
INSERT INTO Partier VALUES (9, 'EUNSP-3', 4, 4);
INSERT INTO Partier VALUES (10, 'EUNSP-4', 4, 4);

INSERT INTO VAL VALUES (2014);
INSERT INTO VAL VALUES (2019);

INSERT INTO Deltar VALUES (1, 2014, 100);
INSERT INTO Deltar VALUES (1, 2019, 47);
INSERT INTO Deltar VALUES (2, 2014, 100);
INSERT INTO Deltar VALUES (2, 2019, 90);
INSERT INTO Deltar VALUES (3, 2014, 100);
INSERT INTO Deltar VALUES (3, 2019, 200);
INSERT INTO Deltar VALUES (4, 2014, 10);
INSERT INTO Deltar VALUES (5, 2019, 10);
INSERT INTO Deltar VALUES (6, 2019, 1000);

SELECT * FROM Länder;
SELECT * FROM Partigrupper;
SELECT * FROM Partier;
SELECT * FROM Val;
SELECT * FROM Deltar;

Uppgift 3 (9 p)

Formulera följande frågor i SQL. Definiera gärna vyer eller CTE:er om det underlättar, men skapa inte nya tabeller.

a) (2p) Vilka partier finns i Sverige och Tyskland? Vi vill alltså veta namnen på alla partier från Sverige och från Tyskland.

SELECT Namn
FROM Partier
WHERE Land IN (SELECT Nummer FROM Länder WHERE Namn = 'Sverige')
OR Land IN (SELECT Nummer FROM Länder WHERE Namn = 'Tyskland');
En alternativ lösning:
SELECT Partier.Namn
FROM Partier, Länder
WHERE Partier.Land = Länder.Nummer
AND (Länder.Namn = 'Sverige'
     OR Länder.Namn = 'Tyskland');
En tredje lösning:
SELECT Partier.Namn
FROM Partier JOIN Länder ON Partier.Land = Länder.Nummer
WHERE Länder.Namn = 'Sverige'
OR Länder.Namn = 'Tyskland';

b) (2p) Vilka partier från Sverige är med i partigruppen EPP?

SELECT Partier.Namn
FROM Partier, Länder, Partigrupper
WHERE Partier.Land = Länder.Nummer
AND Partier.Partigrupp = Partigrupper.Nummer
AND Länder.Namn = 'Sverige'
AND Partigrupper.Namn = 'EPP';

c) (2p) Totalt hur många röstade i Sverige i EU-valet 2019?

SELECT SUM(Röster)
FROM Partier, Länder, Deltar
WHERE Partier.Land = Länder.Nummer
AND Partier.Nummer = Deltar.Parti
AND Deltar.Val = 2019
AND Länder.Namn = 'Sverige';

d) (3p) Vad heter den partigrupp som fick flest röster i EU-valet 2019?

CREATE VIEW Partigruppsröster2019 AS
SELECT Partigrupper.Namn, SUM(Röster) AS Röster
FROM Partier, Partigrupper, Deltar
WHERE Partier.Partigrupp = Partigrupper.Nummer
AND Partier.Nummer = Deltar.Parti
AND Deltar.Val = 2019
GROUP BY Partigrupper.Namn;

SELECT Namn
FROM Partigruppsröster2019
WHERE Röster IN (SELECT MAX(Röster) FROM Partigruppsröster2019);
Eller med en CTE:
WITH Partigruppsröster2019 AS
(SELECT Partigrupper.Namn, SUM(Röster) AS Röster
FROM Partier, Partigrupper, Deltar
WHERE Partier.Partigrupp = Partigrupper.Nummer
AND Partier.Nummer = Deltar.Parti
AND Deltar.Val = 2019
GROUP BY Partigrupper.Namn)
SELECT Namn
FROM Partigruppsröster2019
WHERE Röster IN (SELECT MAX(Röster) FROM Partigruppsröster2019);

Uppgift 4 (2 p)

Man kanske vill ha med inte bara antalet röster som varje parti fick, utan också hur många procent av rösterna de fick. Hur skulle man kunna lösa det med en vy? Om du inte vill skriva SQL-kod, kan du i stället förklara hur det skulle fungera.

Räkna ut summan av antalet röster i det valet, och dela varje partis röster med den summan, gånger 100 så det blir procent. Om man gör det som en vy slipper man dubbellagringen att också ha procentandelen lagrad i databasen.

Det blir enklare om man först skapar en vy (eller CTE) för totalt antal röster per val.

CREATE VIEW TotaltAntalRösterPerVal AS
SELECT Deltar.Val, SUM(Röster) AS Röster
FROM Partier, Deltar
WHERE Partier.Nummer = Deltar.Parti
GROUP BY Deltar.Val;

CREATE VIEW RösterMedProcent AS
SELECT Partier.Namn, Deltar.Val, Deltar.Röster, 100.0 * Deltar.Röster / TotaltAntalRösterPerVal.Röster AS Procent
FROM Partier, Deltar, TotaltAntalRösterPerVal
WHERE Partier.Nummer = Deltar.Parti
AND Deltar.Val = TotaltAntalRösterPerVal.Val;

SELECT * FROM RösterMedProcent;
En kommentar: Jag tänkte mig procent av alla röstande i hela EU, men egentligen är det förstås mer realistiskt med procent av de röstande i samma land som partiet är från. Det är förstås inte fel att ha gjort en sådan lösning.

Uppgift 5 (5 p)

Här är ett försök att lösa uppgift 2 ovan, med en databas som bara består av en enda tabell. Den ser ganska rimlig ut, och skulle man visa valresultatet som en tabell i en tidning skulle den mycket väl kunna se ut så här.

Valresultat
Parti Land Grupp År Röster
Vänsterpartiet Sverige GUE/NGL 2019 267949
Socialdemokraterna Sverige S&D 2019 940131
Miljöpartiet Sverige G/EFA 2019 454336
Kristdemokraterna Sverige EPP 2019 344884
Centerpartiet Sverige Alde 2019 429811
Liberalerna Sverige Alde 2019 163169
Moderaterna Sverige EPP 2019 670931
Sverigedemokraterna Sverige ECR 2019 614699

a) Om vi betraktar tabellen som en tabell i en relationsdatabas, och inte en tabell som är tryckt i en tidning, vilka kandidatnycklar finns i tabellen?

Den enda kandidatnyckeln är kombinationen av Parti och År. Enbart Parti räcker inte, om man ska kunna lagra resultaten av flera olika val, och det ska man ju enligt scenariot.

b) Vilka fullständiga funktionella beroenden finns i tabellen?

{ Parti, År } -> Röster
Parti -> Land
Parti -> Grupp

c) Vilka av de fyra normalformerna 1NF, 2NF, 3NF och BCNF uppfyller tabellen?

Endast 1NF.

d) Motivera svaret i c-uppgiften ovan!

Tabellen uppfyller 1NF eftersom den endast innehåller enkla, atomära värden. Inga rutor innehåller listor eller tupler. ("GUE/NGL", "S&D" och "G/EFA" är namn på partigrupper, och betyder inte att partierna är med i flera olika partigrupper.)

Tabellen uppfyller inte 2NF eftersom det finns ffb från delar av primärnyckeln, nämligen beroendena Parti -> Land och Parti -> Grupp.

Tabellen uppfyller inte 3NF och BCNF eftersom högre normalformer (i ordningen 1NF, 2NF, 3NF och BCNF, där BCNF är en högsta normalformen) bygger på lägre, så en tabell som inte uppfyller 2NF kan inte heller uppfylla 3NF eller BCNF.

Uppgift 6 (4 p)

a) Vad skulle transaktioner kunna behövas till i EU:s valdatabas?

ACID-transaktioner har egenskaperna atomicitet, konsistensbevarande, isolering och hållbarhet, och alla är viktiga i EU-valet. Hållbarhet är förstås viktigt, för när man räknat röster i en vallokal och lägger till dem till partiernas röstsummor, vill man inte att de räknade rösterna ska försvinna. Isolering är viktigt, eftersom man räknar röster på många olika platser samtidigt, och då får det inte bli några förlorade uppdateringar eller liknande problem när man lägger till dem i databasen. Atomicitet behövs, så inte bara en del röster läggs in i databasen, och en del försvinner. Det är också viktigt att transaktionerna är konsistensbevarande, så man inte får inkonsistenser i databasen, till exempel att ett parti som inte finns har fått röster registrerade.

b) Databashanterare brukar använda en loggfil. Vad är det som lagras på loggfilen, och vad har man för nytta av den i samband med transaktioner?

På loggfilen lagras alla ändringar som görs i databasen. Man lagrar vilka data det är som ändrats, och det gamla och det nya värdet, och vilken transaktion det var som gjorde ändringen. Man lagrar också när en transaktion startas och när den avslutas, med commit eller rollback. (Dessutom skrivs så kallade checkpoints, men det tar vi inte upp här.)

Om en transaktion avbryts mitt i och måste rullas tillbaka (för att uppfylla egenskapen atomicitet) kan databashanteraren se i loggfilen vilka data som ändrats, tillsammans med de gamla värdena, så den kan ändra tillbaka.

Om systemet kraschar, till exempel vid ett strömavbrott, och färdiga transaktioners alla ändringar kanske inte hunnit fysiskt skrivas till sekundärminnet, kan databashanteraren se i loggfilen vilka data som ändrats, tillsammans med de nya värdena, så den kan skriva dem på nytt, för att garantera att de verkligen finns permanent lagrade (för att uppfylla egenskaperna atomicitet och hållbarhet).

Uppgift 7 (5 p)

a) (3p) Visa med ett par enkla exempel vad man har SQL-kommandona grant och revoke till. Glöm inte att förklara vad som händer!

Grant och revoke är två kommandon som används för att ange vad olika användare får göra med de data som finns i databasen. Med grant delar man ut rättigheter, och med revoke tar man bort dem igen. Normalt är det databasadministratören som gör detta.

Exempel:

GRANT SELECT, INSERT ON Svampar TO vladimir;
Det ger användaren vladimir rätt att göra sökningar i tabellen Svampar, och att lägga till rader i den tabellen, men inte att ta bort eller ändra rader.
GRANT UPDATE ON Svampar TO vladimir;
Nu har Vladimir även fått rätt att ändra existerande rader, men fortfarande inte att ta bort rader.

REVOKE INSERT ON Svampar FROM vladimir;

Nu har Vladimir inte längre rätt att ta lägga till nya rader, men han kan fortfarande både söka i tabellen och ändra existerande rader.

b) (2p) Visa hur man kan kombinera grant och revoke med vyer för att ge en mer finkornig kontroll av vad användarna får göra med databasen.

Man kan styra åtkomsten mer finkornigt genom att skapa vyer, och dela ut rättigheter till dessa vyer, i stället för till de tabeller som de baseras på. Exempel:

REVOKE SELECT ON Svampar FROM vladimir;

CREATE VIEW ViktenPåGulaSvamparISkåne AS
SELECT Vikt
FROM Svampar
WHERE Färg = 'Gul'
AND Placering IN (SELECT Nummer FROM Landskap WHERE Namn = 'Skåne');

GRANT SELECT ON ViktenPåGulaSvamparISkåne TO vladimir;
Nu har Vladimir rätt att se vikten på gula svampar i Skåne men inga andra kolumner, och inga andra svampar.

Uppgift 8 (3 p)

Förklara vad ett B-träd är, och särskilt hur B-träd skiljer sig från binära träd. Varför används B-träd ofta i databashanterare?

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 nog) 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 9 (4 p)

I databaser kan det förekomma redundans av olika slag. Förklara vad som menas med redundans. Beskriv också två olika typer av redundans som kan förekomma, och i vilka sammanhang de förekommer. Vilka fördelar och nackdelar finns med de olika typerna av redundans?

Några förslag på olika typer av redundans:

Dessa har olika fördelar och nackdelar. Exempelvis ger redundans i lågt normaliserade tabeller förstås nackdelen att upprepade data tar upp onödig plats i databasen, men också att det lätt kan bli inkonsistenser i databasen vid ändringar, om man glömmer att ändra alla förekomsterna av samma uppgift. Låg normalisering kan ha fördelen att databasen blir snabbare, eftersom man behöver färre joinar mellan tabeller, och den kan i vissa fall faktiskt bli mer lättförståelig och lätt att arbeta med.


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 19 juni 2019