Databasteknik II: Hemtentamen 2015-05-31

Det här är hemtentan i kursen Databasteknik II. Den ska lämnas in senast söndag 31 maj 2015 klockan 08:00. 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. 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

Här är en bild på hur säkerhetspolisen, Säpo, vaktar en minister:

Säpo vaktar en minister

(Bild av Frankie Fouganthin, via Wikimedia, licens Creative Commons Attribution-Share Alike 4.0)

Säpo har anställda agenter, som vi förstås lagrar i en tabell. I en annan tabell lagrar vi ministrar. Dessutom vaktar agenterna ministrarna, enligt ett schema som vi lagrar i en tredje tabell.

Agenter
Nr Namn Telefon Chef
1 Anna 172622 null
2 Bob 267877 1
3 Charlie 172622 1
4 David null 3
5 Erik 189900 3

Ministrar
Nr Namn Titel Telefon
1 Stefan Statsminister null
2 Anders Inrikesminister 998099
3 Margot Utrikesminister 145567
4 Magdalena Finansminister null

Vaktar
Agent Minister Datum
3 4 2015-05-20
4 1 2015-05-21
4 1 2015-05-22
5 1 2015-05-22
5 2 2015-05-21

Här finns kommandon för att skapa och fylla dessa tabeller: skapa-sapo.txt

På riktigt kommer det att finnas tusentals agenter och kanske miljoner rader i vaktschema-tabellen. 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).

Uppgift 1 (5 p)

Skriv ett program som kopplar upp sig mot databasen, och som hjälper att redigera vaktschemat. Man ska kunna ta bort och lägga till vaktpass (dvs rader i tabellen Vaktar).

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 vilka säpo-agenter som vaktar statsministern 22 maj, så vi skriver följande SQL-fråga:
select Agenter.Nr, Agenter.Namn
from Agenter, Vaktar, Ministrar
where Agenter.Nr = Vaktar.Agent
and Vaktar.Minister = Ministrar.Nr
and Vaktar.Datum = DATE'2015-05-22'
and Ministrar.Titel = 'Statsminister';

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) Hur kommer den riktiga databashanteraren att optimera frågan, i den riktiga databasen med tusentals agenter och miljoner rader i vaktschema-tabellen? Hur skiljer sig den exekveringsplanen från den heuristiskt optimerade frågan ovan?

Uppgift 3 (5 p)

Några tekniker som tas upp i kursen är objektdatabaser (även kallade objektorienterade databaser, eller första generationens objektorienterade databaser), objektrelationella databaser, distribuerade databaser och NoSQL-databaser.

Vi lagrar säpo-databasen som en vanlig relationsdatabas. Hade det varit lämpligt att i stället använda:

a) en objektdatabas,
b) en objektrelationell databas,
c) en distribuerad databas, eller
d) en NoSQL-databas?

Motivera vart och ett av svaren.

Uppgift 4 (5 p)

Agenter slutar på Säpo och nya agenter tillkommer, de får nya telefonnummer, och chefsförhållanden ändras. Vi vill spara historik om hur personalen sett ut.

a) Vilken tidsdimension bör vi lägga till?

b) Visa hur man kan lagra tabellen Agenter med den tidsdimensionen i en vanlig relationsdatabas.

c) Blir det svårt att upprätthålla den unika primärnyckeln Nr? Vad kan man göra för att försöka säkra unikheten?

d) Blir det svårt att upprätthålla referensintegriteten i chefssambandet? Vad kan man göra för att försöka säkra referensintegriteten?

e) I tabellen Vaktar finns redan tidsuppgiften Datum. Kan man se den som en tidsdimension, och i så fall vilken?

Uppgift 5 (5 p)

I tabellen Vaktar finns två miljoner rader. Det enda index som finns är ett sammansatt primärindex på alla tre kolumnerna. Gör rimliga antaganden om blockstorlek med mera (och ange dem), och räkna ut hur lång tid det kommer att ta att köra var och en av följande SQL-frågor. Vi antar att varje fråga bara ger en enda rad som svar.

a)

select * from Vaktar where Agent = 14567;
b)
select * from Vaktar where Datum = DATE'2015-05-20';
c)
select Minister from Vaktar where Datum = DATE'2015-05-20';

Uppgift 6 (5 p)

På kursens webbplats finns en beskrivning av kursens innehåll
(http://basen.oru.se/kurser/db2/2014-2015-p34/innehall.html).
Den ser ut ungefär så här, om man först stryker de ämnen som redan nämnts i frågorna ovan:
  1. Transaktionshantering
  2. Legacy databases
  3. NewSQL
  4. Datautvinning ("data mining") och datalager ("data warehouses")
Välj ett av dessa sju ämnen, och skriv en introduktion om det. 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 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), 21 maj 2015