Databasteknik II: Hemtentamen 2017-06-04

Instruktioner

1. Lös uppgifterna och skicka sen in svaren till mig (thomas.padron-mccarthy@oru.se) senast den ovan angivna tiden.
2. Uppgiften ska lösas enskilt, dvs inget samarbete och inga grupper av två eller flera studenter.
3. Man måste ha lämnat in labbarna innan man gör tentan. Det är inte nödvändigt att de är rättade eller godkända, men de måste vara inlämnade.
4. För att få godkänt resultat den här hemtentan ska man ha besvarat frågorna på ett sätt som visar att man läst och förstått (delar av) kurslitteraturen.
5. Jag räknar ungefär så här: Varje uppgift blir antingen godkänd med 4 eller 5 poäng, eller underkänd med noll poäng. Inga halv- eller enpoängare för att man försökt lösa en uppgift och kanske lyckats få med någon detalj som är rätt. För godkänt på tentan krävs minst 5 godkända uppgifter, vilket motsvarar en godkänt-gräns på 20 poäng av maximalt 30. Vissa kompletteringar i efterhand kan komma att tillåtas.
6. Godkänt resultat på den här hemtentan ger betyget G på teoridelen av kursen. För att få hela kursen godkänd krävs dessutom godkända inlämningsuppgifter.
7. Du får använda dator, böcker och vilka andra hjälpmedel som helst, men du får inte samarbeta eller fråga någon (utom mig). Exempelvis är det tillåtet att söka och läsa på webbplatser som Stack Overflow, men inte att ställa egna frågor.
8. Antaganden utöver de som står i uppgifterna måste anges. Gjorda antaganden får inte förändra den givna uppgiften.
9. Oklara formuleringar kommer att misstolkas.
10. Skriv gärna förklaringar om hur du tänkt. Även ett svar som är fel kan ge poäng, om det finns med en förklaring som visar att huvudtankarna var rätt.
11. Om du behöver fråga något, så kontakta gärna mig. Om det är bråttom är det nog bäst att ringa eller SMS:a (se mobilnumret ovan), för det är inte säkert att jag sitter vid datorn, särskilt på helgerna.
12. Undvik Word-dokument. PDF eller text fungerar bättre.
13. Om du inte senast under måndagen får e-post från mig med en bekräftelse på att du skickat in något, bör du kontakta mig, enklast genom att ringa eller SMS:a mig (ifall det är e-posten som inte fungerar).

Scenario till en del av uppgifterna

ÖSÖ består av flera avdelningar, med patienter som vårdas på avdelningarna. Patienterna har diagnosticerats med olika sjukdomar.

Här är de SQL-kommandon som användes för att skapa databasen, och för att lägga in några exempelrader:

CREATE TABLE Avdelningar
(Nummer INTEGER NOT NULL PRIMARY KEY,
Namn NVARCHAR(50) NOT NULL UNIQUE);

CREATE TABLE Patienter
(ID INTEGER NOT NULL PRIMARY KEY,
Personnummer CHAR(12) NOT NULL UNIQUE,
Namn NVARCHAR(50) NOT NULL,
Avdelning INTEGER REFERENCES Avdelningar(Nummer));

CREATE TABLE Sjukdomar
(ID INTEGER NOT NULL PRIMARY KEY,
Namn NVARCHAR(50) NOT NULL UNIQUE);

CREATE TABLE Diagnoser
(ID INTEGER NOT NULL PRIMARY KEY,
Patient INTEGER NOT NULL REFERENCES Patienter(ID),
Sjukdom INTEGER NOT NULL REFERENCES Sjukdomar(ID),
UNIQUE(Patient, Sjukdom));

INSERT INTO Avdelningar (Nummer, Namn) VALUES (1, 'IVA');
INSERT INTO Avdelningar (Nummer, Namn) VALUES (2, 'Medicin');
INSERT INTO Avdelningar (Nummer, Namn) VALUES (3, 'Ortopedi');
INSERT INTO Avdelningar (Nummer, Namn) VALUES (5, 'Kirurgi');

INSERT INTO Patienter (ID, Personnummer, Namn, Avdelning) VALUES (1, '631211-1658', 'Anna Berg', null);
INSERT INTO Patienter (ID, Personnummer, Namn, Avdelning) VALUES (2, '631211-3696', 'Bo Berg', 1);
INSERT INTO Patienter (ID, Personnummer, Namn, Avdelning) VALUES (3, '631211-2672', 'Cesar Berg', 2);
INSERT INTO Patienter (ID, Personnummer, Namn, Avdelning) VALUES (4, '631211-1906', 'Donna Berg', 1);
INSERT INTO Patienter (ID, Personnummer, Namn, Avdelning) VALUES (5, '631211-4751', 'Erik Berg', 2);

INSERT INTO Sjukdomar (ID, Namn) VALUES (1, 'värk');
INSERT INTO Sjukdomar (ID, Namn) VALUES (2, 'smärtor');
INSERT INTO Sjukdomar (ID, Namn) VALUES (3, 'galenskap');
INSERT INTO Sjukdomar (ID, Namn) VALUES (4, 'pest');
INSERT INTO Sjukdomar (ID, Namn) VALUES (5, 'kolera');

INSERT INTO Diagnoser (ID, Patient, Sjukdom) VALUES (1, 1, 5);
INSERT INTO Diagnoser (ID, Patient, Sjukdom) VALUES (2, 2, 5);
INSERT INTO Diagnoser (ID, Patient, Sjukdom) VALUES (3, 3, 5);
INSERT INTO Diagnoser (ID, Patient, Sjukdom) VALUES (4, 4, 5);
INSERT INTO Diagnoser (ID, Patient, Sjukdom) VALUES (5, 5, 5);
INSERT INTO Diagnoser (ID, Patient, Sjukdom) VALUES (6, 1, 1);
INSERT INTO Diagnoser (ID, Patient, Sjukdom) VALUES (7, 2, 1);
INSERT INTO Diagnoser (ID, Patient, Sjukdom) VALUES (8, 3, 1);
INSERT INTO Diagnoser (ID, Patient, Sjukdom) VALUES (9, 4, 1);
INSERT INTO Diagnoser (ID, Patient, Sjukdom) VALUES (10, 1, 4);
INSERT INTO Diagnoser (ID, Patient, Sjukdom) VALUES (11, 2, 4);

Tabellerna med exempelraderna:

På riktigt finns tiotals avdelningar, många tusen sjukdomar och flera miljoner patienter och diagnoser. Vi antar att vi använder en normal, diskbaserad relationsdatabashanterare som använder sig av B⁺-trädsindex. Den har en bra frågeoptimerare. Data lagras på mekaniska hårddiskar (dvs inte SSD:er). Databashanteraren skapar automatiskt fysiska primärindex på de angivna primärnycklarna (PRIMARY KEY) och fysiska sekundärindex på alternativnycklarna (UNIQUE). Vi har inte skapat ytterligare index.

Uppgift 1 (5 p)

Kopplar upp sig... Ok.
Ange patientens personnummer: 631211-1658
Patienten med personnummer 631211-1658 har följande sjukdomar:

värk
pest
kolera

Programmet ska använda sig av någon form av databasåtkomst inifrån programmet, till exempel med JDBC från ett Java-program, ODBC eller ESQL från ett C-program, ADO.NET, eller liknande.

Uppgift 2 (5 p)

select Sjukdomar.Namn
from Patienter, Diagnoser, Sjukdomar
where Patienter.Personnummer = '631211-1658'
and Patienter.ID = Diagnoser.Patient
and Diagnoser.Sjukdom = Sjukdomar.ID;

a) Ange den systematiska översättningen av frågan, även kallad kanonisk form, till relationsalgebra. (Det är alltså den o-optimerade formen.) Skriv den som ett relationsalgebrauttryck.

b) Rita upp samma relationsalgebrauttryck som ett träd.

c) Visa hur en heuristisk frågeoptimerare, som inte tar hänsyn till datamängder eller lagringsstrukturer, optimerar den kanoniska formen. Visa både vilka olika optimeringar som görs, och vad slutresultatet blir.

d) En kostnadsbaserad frågeoptimerare har inte enkla regler för hur hur den ska köra frågan, utan jämför alla sätt att köra frågan som finns, och väljer det snabbaste. Hur är det troligt att den skulle välja att göra i det här fallet, med index och datamängder enligt scenariot. Varför? Blir det några skillnader jämfört med den heuristiska optimeraren?

Uppgift 3 (5 p)

Hur lång tid tar följande SQL-frågor att köra? Gör rimliga antaganden om blockstorlek med mera, ange de antaganden du gjort, och visa hur du räknat. Rita gärna bilder! För enkelhets skull antar vi att varje fråga bara ger en enda rad som resultat.

a)

SELECT *
FROM Diagnoser
WHERE ID = 456789;

b)

SELECT *
FROM Diagnoser
WHERE Patient = 456789;

c)

SELECT *
FROM Diagnoser
WHERE Sjukdom = 456789;

Uppgift 4 (5 p)

Plötsligt går strömmen. När strömmen kommit tillbaka och datorn startat om, ser den materialiserade databasen, dvs de data som faktiskt finns på disken, ut så här:

Loggfilen ser ut så här:

1. Transaktion T1: startar
2. T1: ändrar tal 1 från 17 till 18
3. T1: ändrar tal 2 från 17 till 18
4. T1: ändrar tal 3 från 17 till 18
5. Transaktion T1: commit
6. Checkpoint
7. Transaktion T2: startar
8. T2: ändrar tal 4 från 17 till 18
9. Transaktion T3: startar
10. T2: ändrar tal 5 från 17 till 18
11. T3: ändrar tal 7 från 17 till 18
12. T3: ändrar tal 8 från 17 till 18
13. T2: ändrar tal 6 från 17 till 18
14. T3: ändrar tal 9 från 17 till 18
15. Transaktion T3: commit

Vilka ändringar i databasen kommer att göras under recovery-processen, och hur ser databasen ut när den är klar?

Uppgift 5 (5 p)

Uppgift 6 (5 p)

1. Distribuerade databaser, multidatabaser
2. Frågeexekvering och frågeoptimering i Amos2
3. Alternativa datamodeller. Legacy databases. Mediatorer. SQL, NoSQL och NewSQL.
4. Datautvinning ("data mining") och datalager ("data warehouses")
5. Tid i databaser, temporala databaser

Det kan vara lämpligt med en eller kanske två A4-sidor text för själva beskrivningen. Men ha gärna med förklarande exempel, och i så fall kan det gå åt ytterligare en eller flera sidor för exemplen.

Använd gärna källor, men:

• Skriv med egna ord.
• Ange vilka källor du använt.