Databasteknik II: Hemtentamen 2015-08-30

Det här är hemtentan i kursen Databasteknik II. Den ska lämnas in senast söndag 30 augusti 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

Det här är samma scenario som på förra tentan, i maj, nämligen att Säpo vaktar ministrar.

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 dessa tabeller och lägga in exempelrader: skapa-sapo.txt

På riktigt kommer det att finnas tio ministrar och tio tusen agenter i databasen, och tio 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)

Hur stor plats tar databasen? Får den plats på en vanlig hårddisk? På en SSD? I primärminne?

Redovisa resonemang och beräkningar.

Uppgift 2 (5 p)

Skriv ett program som kopplar upp sig mot databasen, och som hjälper till med att visa upp vaktschemat. Vi vill kunna mata in ett datum, och så ska programmet lista alla vaktpassen den dagen, med namnen på både agenterna och ministrarna.

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 3 (5 p)

Vi vill veta telefonnumren till agenterna som var i tjänst 22 maj, så vi skriver följande SQL-fråga:
select Agenter.Telefon
from Agenter, Vaktar
where Agenter.Nr = Vaktar.Agent
and Vaktar.Datum = DATE'2015-05-22';

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? Skiljer sig den exekveringsplanen från den heuristiskt optimerade frågan ovan, och i så fall hur och varför?

Uppgift 4 (5 p)

Databashanteraren vi använder skapar automatiskt index på alla primärnycklar, men i övrigt finns inga index. Hur lång tid kommer det att ta att köra frågan i uppgiften ovan?

Redovisa resonemang och beräkningar.

Uppgift 5 och 6 (10 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. Objektdatabaser och objektrelationella databaser
  3. Distribuerade databaser, multidatabaser
  4. Legacy databases: nätverksdatabaser och hierarkiska databaser
  5. NoSQL
  6. NewSQL
  7. Datautvinning ("data mining") och datalager ("data warehouses")
  8. Tid i databaser, temporala databaser
Välj två (obs: två) av dessa åtta ä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), 22 augusti 2015