Databasteknik II: Hemtentamen 2016-09-15

Det här är hemtentan i kursen Databasteknik II. Den ska lämnas in senast torsdag 15 september 2016. Sista inlämningsdagen håller på hela dagen, så man kan lämna in tentan ända fram till midnatt. Ansvarig lärare är Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se) telefon 070-73 47 013.

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. Mimer-databasservern på basen.oru.se är ominstallerad. Gamla login och data finns inte kvar. Kontakta mig om du behöver provköra mot basen.oru.se, så får du ett nytt login och lösenord.
  13. Undvik Word-dokument. PDF eller text fungerar bättre.
  14. 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

Vi har byggt en databas som innehåller information om studenter, kurser och betyg.

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 Kurser
    (Kod VARCHAR(6) NOT NULL PRIMARY KEY,
    Namn VARCHAR(10) NOT NULL);

CREATE TABLE Studenter
    (ID INTEGER NOT NULL PRIMARY KEY,
    Personnummer VARCHAR(11) NOT NULL UNIQUE,
    Namn VARCHAR(40) NOT NULL);

CREATE TABLE Betyg
    (ID INTEGER NOT NULL PRIMARY KEY,
    Student INTEGER REFERENCES Studenter(ID),
    Kurs VARCHAR(6) REFERENCES Kurser(Kod),
    Betyg CHAR(2));

INSERT INTO Kurser (Kod, Namn) VALUES ('IK123', 'Atomfysik');
INSERT INTO Kurser (Kod, Namn) VALUES ('IK456', 'SQL Server');

INSERT INTO Studenter (ID, Personnummer, Namn)
    VALUES (1, '900123-1234', 'Bruce Wayne');
INSERT INTO Studenter (ID, Personnummer, Namn)
    VALUES (2, '900221-4321', 'Clark Kent');
INSERT INTO Studenter (ID, Personnummer, Namn)
    VALUES (3, '901118-2341', 'Barbara Gordon');
INSERT INTO Studenter (ID, Personnummer, Namn)
    VALUES (4, '900216-2431', 'Katherine Kane');

INSERT INTO Betyg  (ID, Student, Kurs, Betyg) VALUES (1, 1, 'IK123', 'G');
INSERT INTO Betyg  (ID, Student, Kurs, Betyg) VALUES (2, 1, 'IK456', 'VG');
INSERT INTO Betyg  (ID, Student, Kurs, Betyg) VALUES (3, 2, 'IK123', 'U');
INSERT INTO Betyg  (ID, Student, Kurs, Betyg) VALUES (4, 3, 'IK456', 'VG');
INSERT INTO Betyg  (ID, Student, Kurs, Betyg) VALUES (5, 4, 'IK123', 'G');
INSERT INTO Betyg  (ID, Student, Kurs, Betyg) VALUES (6, 4, 'IK456', 'VG');

På riktigt innehåller databasen tusen kurser, tio tusen studenter, och en miljon betyg. 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, och vi har inte skapat ytterligare index.

Uppgift 1 (5 p)

Skriv ett program som kopplar upp sig mot databasen, och som hjälper oss att söka efter betyg som en student har. Man ska kunna skriva in ett personnummer, och få en lista med kursnamn och betyg. Här är ett förslag på hur det skulle kunna se ut:
Kopplar upp sig... Ok.
Ange studentens personnummer: 900123-1234
Studenten med personnummer 900123-1234 har följande betyg:

Kurs            Betyg
====            =====
Atomfysik       G
SQL Server      VG

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)

Vi vill veta vilket betyg Bruce Wayne hade i kursen Atomfysik, och skriver följande SQL-fråga:
select Betyg.Betyg
from Studenter, Betyg, Kurser
where  Studenter.ID = Betyg.Student
and Betyg.Kurs = Kurser.Kod
and Studenter.Namn = 'Bruce Wayne'
and Kurser.Namn = 'Atomfysik';

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 endast på primärnycklar, och de angivna datamängderna? Varför?

Uppgift 3 (5 p)

a)

Vi söker efter ett betyg med ett visst ID-nummer i den riktiga databasen, den med en miljon betyg, och ställer följande SQL-fråga:

SELECT *
FROM Betyg
WHERE ID = 456789;
Eftersom kolumnen ID är primärnyckel i tabellen, och databashanteraren automatiskt skapar fysiska primärindex, finns ett primärindex på ID. Hur lång tid tar den frågan att köra? Gör rimliga antaganden om blockstorlek med mera, ange de antaganden du gjort, och visa hur du räknat.

b)

Nu söker vi efter ett betyg i en viss kurs, och skriver följande SQL-fråga.

SELECT *
FROM Betyg
WHERE Kurs = 'DT109G';
Det finns inget index på kolumnen Kurs. Hur lång tid tar frågan att köra? Ange de antaganden du gjort, och visa hur du räknat. (För enkelhets skull kan vi anta att det råkar finns bara ett enda betyg från kursen med den sökta kurskoden.)

c)

Vi skapar ett sekundärindex på Kurs:

SELECT *
FROM Betyg
WHERE Kurs = 'DT109G';
Hur lång tid tar frågan nu att köra? Ange de antaganden du gjort, och visa hur du räknat.

Uppgift 4 (5 p)

I en databashanterare körs tre olika transaktioner (T1, T2 och T3) enligt följande tidsschema. Transaktionerna arbetar med tre olika dataobjekt (A, B och C). Räkneoperationer är inte med i tidsschemat, utan bara läs- och skrivoperationer och start respektive commit av transaktioner.

Tid T1 T2 T3
1 Start    
2   Start  
3     Start
4     Läs(A)
5     Skriv(B)
6   Läs(A)  
7   Skriv(B)  
8 Läs(A)    
9 Läs(B)    
10 Skriv(A)    
11 Skriv(B)    
12   Skriv(C)  
13 Skriv(C)    
14     Skriv(C)
15   Commit  
16 Commit    
17     Commit

a) (1p) Vad innebär det att ett tidsschema är serialiserbart?

b) (1p) Är schemat ovan seriellt? Motivera svaret!

c) (1p) Är schemat ovan serialiserbart? Motivera svaret!

d) (2p) Välj en av följande metoder för isolering av transaktioner, och visa hur tidsschemat ovan skulle förändras om respektive metod användes. (Observera: Välj alltså en av dessa metoder!)

Uppgift 5 och 6 (10 p)

På kursens webbplats finns en beskrivning av kursens innehåll
(http://basen.oru.se/kurser/db2/2015-2016-p34/innehall.html).
Den ser ut ungefär så här, om man först stryker de ämnen som redan behandlats i frågorna ovan:
  1. Objektdatabaser och objektrelationella databaser
  2. Distribuerade databaser, multidatabaser
  3. Legacy databases
  4. SQL, NoSQL och NewSQL
  5. Datautvinning ("data mining") och datalager ("data warehouses")
  6. Tid i databaser, temporala databaser
Välj två av dessa ämnen, och skriv en introduktion om vart och ett av dem. Målgruppen är någon som kan "datorer" och programmering, och som gått en grundkurs om databaser.

Det kan vara lämpligt med en eller kanske två A4-sidor text per ämne 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:


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 7 september 2016