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

Uppgift 1 (5 p)

Uppgift 2 (6 p)

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)

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');

SELECT Partier.Namn
FROM Partier, Länder
WHERE Partier.Land = Länder.Nummer
AND (Länder.Namn = 'Sverige'
     OR Länder.Namn = 'Tyskland');

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

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)

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;

Uppgift 5 (5 p)

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)

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)

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;

GRANT UPDATE ON Svampar TO vladimir;

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;

Uppgift 8 (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 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)

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

• Redundans i form av upprepade faktauppgifter i lågt normaliserade tabeller
• Loggfilen
• Backup
• Buffring och cachning
• Replikering i distribuerade och parallella databaser, dvs att samma data lagras på flera olika datorer i nätverket