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

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)

Rita ett ER- eller EER-diagram för den beskrivna databasen. Använd informationen i scenariot ovan, men tänk också på att det ska gå att svara på frågorna i uppgift 4 nedan.

ER- och EER-diagram kan ritas på flera olika sätt. Om du använder en annan notation än kursboken, måste du förklara den notation som du använder.

Svar:

Ett ER-diagram

Uppgift 2 (6 p)

Implementera den beskrivna databasen i relationsmodellen, dvs översätt ER-diagrammet till tabeller.

Du behöver inte skriva create table-kommandon i SQL, men du ska ange vilka relationer som finns och vilka attribut varje relation innehåller. Ange också alla kandidatnycklar, vilken av dessa som är primärnyckel, samt vilka referensattribut som finns och vad de refererar till.

Implementationen ska vara bra.

Svar:

Stjärnor(Nummer, Namn, Rektascension, Deklination, Luminositet, Magnitud)
Stjärnbilder(Nummer, Namn)
Ingår(Stjärna, Stjärnbild)
Fotografier(Nummer, Datum, Stjärnbild)
VisarStjärnor(Fotografi, Stjärna)

Primärnycklarna är understrukna. I tabellen Stjärnbilder är även Namn en kandidatnyckel, I tabellen Stjärnor är även Namn en kandidatnyckel, om man tillåter kandidatnycklar att vara null. Även positionen, dvs kombinationen av Rektascension och Deklination, kan vara en kandidatnyckel om vi antar att den har tillräcklig upplösning och precision för att särskilja alla stjärnor.

Främmande nycklar:

Ingår.Stjärna till Stjärnor.Nummer
Ingår.Stjärnbild till Stjärnbilder.Nummer
Fotografier.Stjärnbild till Stjärnbilder.Nummer
VisarStjärnor.Fotografi till Fotografier.Nummer
VisarStjärnor.Stjärna till Stjärnor.Nummer

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

DROP VIEW Stjärnbildsinformation CASCADE;
DROP TABLE VisarStjärnor CASCADE;
DROP TABLE Fotografier CASCADE;
DROP TABLE Ingår CASCADE;
DROP TABLE Stjärnbilder CASCADE;
DROP TABLE Stjärnor CASCADE;

CREATE TABLE Stjärnor
(Nummer INTEGER NOT NULL PRIMARY KEY,
Namn NVARCHAR(10) NULL UNIQUE,
Rektascension FLOAT NOT NULL,
Deklination FLOAT NOT NULL,
Luminositet FLOAT NOT NULL,
Magnitud FLOAT NOT NULL);

CREATE TABLE Stjärnbilder
(Nummer INTEGER NOT NULL PRIMARY KEY,
Namn NVARCHAR(13) NOT NULL UNIQUE);

CREATE TABLE Ingår
(Stjärna INTEGER NOT NULL REFERENCES Stjärnor(Nummer),
Stjärnbild INTEGER NOT NULL REFERENCES Stjärnbilder(Nummer),
PRIMARY KEY (Stjärna, Stjärnbild));

CREATE TABLE Fotografier
(Nummer INTEGER NOT NULL PRIMARY KEY,
Datum DATE NOT NULL,
Stjärnbild INTEGER NOT NULL REFERENCES Stjärnbilder(Nummer));

CREATE TABLE VisarStjärnor
(Fotografi INTEGER NOT NULL REFERENCES Fotografier(Nummer),
Stjärna INTEGER NOT NULL REFERENCES Stjärnor(Nummer),
PRIMARY KEY (Fotografi, Stjärna));

INSERT INTO Stjärnor (Nummer, Namn, Rektascension, Deklination, Luminositet, Magnitud)
VALUES (1, 'Sirius', 6.752476, -16.716116, 25.4, -1.47);
INSERT INTO Stjärnor (Nummer, Namn, Rektascension, Deklination, Luminositet, Magnitud)
VALUES (2, 'Canopus', 6.399197, -52.695661, 10700, -0.72);
INSERT INTO Stjärnor (Nummer, Namn, Rektascension, Deklination, Luminositet, Magnitud)
VALUES (3, 'Arcturus', 14.261028, 19.182417, 170, -0.04);
INSERT INTO Stjärnor (Nummer, Namn, Rektascension, Deklination, Luminositet, Magnitud)
VALUES (5, 'Vega', 18.615639, 38.783611, 51, 0.03);
INSERT INTO Stjärnor (Nummer, Namn, Rektascension, Deklination, Luminositet, Magnitud)
VALUES (6, 'Rigel', 5.242298, -8.201638, 120000, 0.12);
INSERT INTO Stjärnor (Nummer, Namn, Rektascension, Deklination, Luminositet, Magnitud)
VALUES (8, 'Betelgeuse', 5.919528, 7.406944, 40000, 0.42);

INSERT INTO Stjärnbilder (Nummer, Namn) VALUES (1, 'Björnvaktaren');
INSERT INTO Stjärnbilder (Nummer, Namn) VALUES (2, 'Kölen');
INSERT INTO Stjärnbilder (Nummer, Namn) VALUES (3, 'Orion');
INSERT INTO Stjärnbilder (Nummer, Namn) VALUES (4, 'Stora hunden');
INSERT INTO Stjärnbilder (Nummer, Namn) VALUES (5, 'Lyran');
INSERT INTO Stjärnbilder (Nummer, Namn) VALUES (6, 'Smurfen');
INSERT INTO Stjärnbilder (Nummer, Namn) VALUES (7, 'Kalle Anka');

INSERT INTO Ingår (Stjärna, Stjärnbild) VALUES (1, 4);
INSERT INTO Ingår (Stjärna, Stjärnbild) VALUES (2, 2);
INSERT INTO Ingår (Stjärna, Stjärnbild) VALUES (3, 1);
INSERT INTO Ingår (Stjärna, Stjärnbild) VALUES (6, 3);
INSERT INTO Ingår (Stjärna, Stjärnbild) VALUES (8, 3);
INSERT INTO Ingår (Stjärna, Stjärnbild) VALUES (5, 5);

-- Fotografi 2 är riktigt. De andra är påhittade.

INSERT INTO Fotografier (Nummer, Datum, Stjärnbild) VALUES (1, DATE '1850-07-16', 3);
INSERT INTO Fotografier (Nummer, Datum, Stjärnbild) VALUES (2, DATE '1850-07-17', 5);
INSERT INTO Fotografier (Nummer, Datum, Stjärnbild) VALUES (3, DATE '1850-07-18', 5);

INSERT INTO VisarStjärnor (Fotografi, Stjärna) VALUES (1, 6);
INSERT INTO VisarStjärnor (Fotografi, Stjärna) VALUES (1, 8);
INSERT INTO VisarStjärnor (Fotografi, Stjärna) VALUES (2, 5);
INSERT INTO VisarStjärnor (Fotografi, Stjärna) VALUES (3, 5);

SELECT * FROM Stjärnor;
SELECT * FROM Stjärnbilder;
SELECT * FROM Ingår;
SELECT * FROM Fotografier;
SELECT * FROM VisarStjärnor;

Tabellerna med exempeldata:

Stjärnor
Nummer Namn Rektascension Deklination Luminositet Magnitud
1 Sirius 6.752476 -16.716116 25.4 -1.47
2 Canopus 6.399197 -52.695661 10700 -0.72
3 Arcturus 14.261028 19.182417 170 -0.04
5 Vega 18.615639 38.783611 51 0.03
6 Rigel 5.242298 -8.201638 120000 0.12
8 Betelgeuse 5.919528 7.406944 40000 0.42

Stjärnbilder
Nummer Namn
1 Björnvaktaren
2 Kölen
3 Orion
4 Stora hunden
5 Lyran
6 Smurfen
7 Kalle Anka

Ingår
Stjärna Stjärnbild
1 4
2 2
3 1
6 3
8 3
5 5

Fotografier
Nummer Datum Stjärnbild
1 1850-07-16 3
2 1850-07-17 5
3 1850-07-18 5

VisarStjärnor
Fotografi Stjärna
1 6
1 8
2 5
3 5

Uppgift 3 (3 p)

Välj en av tabellerna som du skapat i uppgift 2 ovan, och ange vilka av de fyra normalformerna 1NF, 2NF, 3NF och BCNF som tabellen uppfyller. Visa därefter att den uppfyller de normalformerna som den uppfyller, och att den inte uppfyller de normalformerna som den inte uppfyller,

Svar:

Som exempel kan vi ta tabellen Stjärnor. Vi antar också att både Namn och kombinationen av Rektascension och Deklination är kandidatnycklar, förutom Nummer. Det här är ett möjligt svar:

Ingen av normalformerna. För att uppfylla 1NF måste alla värden vara atomära, dvs enkla (inga listor) och odelbara (inte sammansatta av flera delar). I verkligheten är det inte alla stjärnor som har namn som Vega och Sirius. De kan också ha namn som PSR J1841-0500 och PSR J1719-1438, och de namnen kan delas upp i delar. PSR står till exempel för "pulsar" (en roterande neutronstjärna som genererar regelbundna pulser). Med det argumentet kan man säga att tabellen inte uppfyller 1NF. Eftersom 1NF, 2NF, 3NF och BCNF är starkare och starkare krav, uppfyller den inte heller de andra normalformerna.

Ett annat möjligt svar:

Alla normalformerna. Om man inte tänker på att stjärnor kan ha den typen av krångliga namn, eller aldrig bryr sig om delarna av namnen, kan man i stället betrakta namnen som atomära. Då uppfyller tabellen 1NF, och för att gå vidare behöver vi studera vilka fullständiga funktionella beroenden som finns i tabellen:

Nycklar och ffb i tabellen Stjärnor

(Bilden visar att det finns ett ffb från var och en av de olika kandidatnycklarna till vart och ett av alla andra attribut.)

2NF: Förutom att 1NF ska vara uppfylld, måste varje icke-nyckel-attribut vara ffb av varje kandidatnyckel, dvs den får inte vara ffb av en del av någon kandidatnyckel. Det får alltså inte finnas några ffb från en del av en kandidatnyckel till ett icke-nyckel-attribut. Det är bara Luminositet och Magnitud som inte ingår i någon kandidatnyckel, och alltså är icke-nyckel-attribut. Den enda sammansatta kandidatnyckel som finns är kombinationen av Rektascension och Deklination, och som vi ser är både Luminositet och Magnitud ffb av hela den kombinationen, och inte en del av den. Därför uppfyller tabellen 2NF.

3NF: Förutom att 2NF ska vara uppfylld (och därmed 1NF), får inget icke-nyckel-attribut vara ffb av något annat icke-nyckel-attribut. (Och inte heller av en kombination av icke-nyckel-attribut.) De icke-nyckel-attribut som finns i tabellen, Luminositet och Magnitud, har inga beroenden till varandra. Därför uppfyller tabellen 3NF.

BCNF: Förutom att 3NF ska vara uppfylld (och därmed 1NF och 2NF), förbjuder BCNF beroenden från en del av en kandidatnyckel till en del av en annan kandidatnyckel. En enklare definition av BCNF är att, förutom att 1NF ska vara uppfylld, måste varje determinant (dvs ett attribut eller en kombination av attribut som ett eller flera andra attribut är ffb av) vara en kandidatnyckel. Det får alltså bara finnas ffb från kandidatnycklar. Vi ser i bilden att alla ffb-pilarna går från kandidatnycklar, så BCNF är uppfylld.

Uppgift 4 (10 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) (1p) Vad är den skenbara magnituden på stjärnorna Sirius och Canopus?

Svar:

SELECT Magnitud
FROM Stjärnor
WHERE Namn = 'Sirius'
OR Namn = 'Canopus';

b) (2p) Vad heter de stjärnor med luminositet större än 100000 som ingår i stjärnbilden Orion?

Svar:

SELECT Stjärnor.Namn
FROM Stjärnor, Ingår, Stjärnbilder
WHERE Stjärnor.Nummer = Ingår.Stjärna
AND Ingår.Stjärnbild = Stjärnbilder.Nummer
AND Stjärnbilder.Namn = 'Orion'
AND Stjärnor.Luminositet > 100000;

c) (1p) Om man ställde alla stjärnorna bredvid varandra skulle den samlingen lysa ganska starkt. Vad är den sammanlagda luminositeten för alla stjärnorna i databasen?

Svar:

SELECT SUM(Luminositet) FROM Stjärnor;

d) (2p) Vilket datum togs det tidigaste foto som visar stjärnan Vega?

Svar:

SELECT MIN(Datum)
FROM Fotografier, VisarStjärnor, Stjärnor
WHERE Fotografier.Nummer = VisarStjärnor.Fotografi
AND VisarStjärnor.Stjärna = Stjärnor.Nummer
AND Stjärnor.Namn = 'Vega';

e) (3p) Skapa en vy som heter Stjärnbildsinformation. Den ska innehålla en rad för varje stjärnbild, och två kolumner: en med stjärnbildens namn, och en med antalet stjärnor som ingår i stjärnbilden. För full poäng ska även stjärnbilder som inte innehåller några stjärnor alls vara med i vyn, med noll som antalet stjärnor.

Svar:

CREATE VIEW Stjärnbildsinformation AS
SELECT Namn, COUNT(Ingår.Stjärnbild) AS AntalStjärnor
FROM Stjärnbilder LEFT JOIN Ingår ON Stjärnbilder.Nummer = Ingår.Stjärnbild
GROUP BY Namn;

-- Och om man vill se innehållet i vyn:

SELECT * FROM Stjärnbildsinformation;

f) (1p) Använd vyn för att ta fram namnet på den stjärnbild som innehåller flest stjärnor!

Svar:

SELECT Namn
FROM Stjärnbildsinformation
WHERE AntalStjärnor = (SELECT MAX(AntalStjärnor) FROM Stjärnbildsinformation);

Uppgift 5 (5 p)

Databasen innehåller många miljoner stjärnor och flera tusen stjärnbilder. Sökningen i delfråga 4b ovan körs ofta, men kanske med andra konstanter, till exempel att man söker efter de stjärnor i stjärnbilden Ormbäraren som har luminositet större än 700. Frågan tar för lång tid att köra. Vi ser att det inte finns några index i databasen, inte ens på nycklar.

a) Vilka index bör man skapa för att den sökningen ska bli snabbare?

Svar:

Här är det lämpligt att skapa index på de kolumner som används i where-villkoret:

b) Ge ett exempel på ett index som inte skulle få den sökningen att gå snabbare, och förklara varför det indexet inte hjälper.

Svar:

Uppgift 6 (3 p)

Hela tiden upptäcker astronomerna nya stjärnor och lägger in dem i databasen. Sökningen i delfråga 4c, om alla stjärnornas sammanlagda luminositet, körs ofta, och den går också för långsamt. Hur kan vi få den att gå fortare?

Svar:

Det finns några olika saker man kan prova:

Att bara skapa en vy av summan, och sen använda den vyn, kommer inte att göra summeringen snabbare.

Uppgift 7 (3 p)

Vi använder en databashanterare med auto-commit, vilket betyder att varje SQL-kommando räknas som en egen transaktion, så länge man inte uttryckligen startar en transaktion med kommandot "start transaction".

Vi startar två olika klientprogram som loggar in på samma databas, och ger följande SQL-kommandon, i den angivna ordningen, i de två klienterna.

Vad blir resultatet av var och en av select-frågorna?

Klient 1 Klient 2
create table Glas
(Nummer integer primary key,
Färg varchar(10));
 
insert into Glas values (1, 'ofärgat');  
select * from Glas; -- Fråga 1  
  select * from Glas; -- Fråga 2
  insert into Glas values (2, 'ofärgat');
  select * from Glas; -- Fråga 3
select * from Glas; -- Fråga 4  
start transaction;  
insert into Glas values (3, 'ofärgat');  
select * from Glas; -- Fråga 5  
  select * from Glas; -- Fråga 6
rollback;  
select * from Glas; -- Fråga 7  
  select * from Glas; -- Fråga 8

Svar:

Fråga 1:

Nummer Färg
1 ofärgat

Fråga 2:

Nummer Färg
1 ofärgat

Fråga 3:

Nummer Färg
1 ofärgat
2 ofärgat

Fråga 4:

Nummer Färg
1 ofärgat
2 ofärgat

Fråga 5:

Nummer Färg
1 ofärgat
2 ofärgat
3 ofärgat

Fråga 6 (eventuellt efter fördröjning till efter klient 1:s rollback-kommando):

Nummer Färg
1 ofärgat
2 ofärgat

Fråga 7:

Nummer Färg
1 ofärgat
2 ofärgat

Fråga 8:

Nummer Färg
1 ofärgat
2 ofärgat

Uppgift 8 (2 p)

Vi gör samma sak en gång till, och ger nu följande SQL-kommandon. Beskriv vad som händer!

Klient 1 Klient 2
start transaction;  
  start transaction;
insert into Glas values (4, 'ofärgat');  
  insert into Glas values (4, 'blått');
commit;  
  commit;

Svar:

Transaktionerna gör motstridiga ändringar, och endast en av dem kan genomföras. Databashanteraren ska förhindra det (C:et i ACID), och den ska också hindra transaktionerna från att störa varandra (I:et i ACID). Exakt vad som händer beror på vilken metod för isolering (I:et) som databashanteraren använder sig av.

Databashanteraren Mimer använder en optimistisk metod, som går ut på att man kör transaktionen, hoppas att det inte blir några krockar, och kontrollerar efteråt att det gick bra. Det som händer då är att klient 1 kör klart, inklusive commit-kommandot, och det ofärgade glaset sparas i databasen. När sedan klient 2 försöker ge commit-kommandot, kommer konflikten mellan transaktionerna att upptäckas, och transaktionen i klient 2 avbryts med ett felmeddelande ("Transaction aborted due to conflict with other transaction") och rullas tillbaka.

Många andra databashanterare använder pessimistiska metoder, där man låser data för att redan från början förhindra krockar. Det som händer då är att när klient 2 försöker köra sitt insert-kommando så är (den delen av) tabellen Glas låst av transaktionen i klient 1, så klient 2 får vänta. När klient 1 ger commit-kommandot släpper den låset, och klient 2 kan köra vidare, men eftersom det redan finns ett glas med nummer 4 går det inte att lägga in det blåa glaset. Man får ett felmeddelande, men den här gången inte om någon konflikt mellan transaktioner utan om en konflikt mellan värden på primärnyckeln. Transaktion 2 avbryts inte, utan kan köra klart och committa, men inte heller här går det att lägga in det blåa glaset.

I bägge fallen blir det alltså det ofärgade glaset som läggs in som glas nummer 4.

Uppgift 9 (3 p)

Det finns olika hot mot som man vill skydda databasen mot. Vilka hot är det?

Svar:

Här går det att svara på olika sätt beroende på hur man tolkar frågan. Man kan svara med vad som kan hända med databasens data:

Man kan också svara med varifrån hoten kommer:

Man kan också svara med vilken metod som används, eller den direkta orsaken:

Det går också att se en olämplig databasstruktur, med felaktigt konstruerade tabeller och felaktiga integritetsvillkor, som ett hot, eftersom det kan ge stora problem i användingen av databasen. Även en olämplig databashanterare, till exempel en där supporten upphör eller där det plötsligt tillkommer nya, dyra licensavgifter, kan ses som ett hot.


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 5 februari 2022