Databasteknik II: Hemtentamen 2016-05-29

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

Skogen är full med blåbär som ingen håller reda på, och så kan vi inte ha det. Därför ska vi skapa en databas med skogens alla blåbär.

Här är ett ER-diagram för databasen: Ett ER-diagram

Det vi lagrar i databasen är detta:

Vi skapar tabellerna och lägger in några exempelrader:

drop table "Blåbär";
drop table Buskar;

create table Buskar
(nummer integer not null primary key,
"höjd" float not null,
latitud float not null,
longitud float not null);

insert into Buskar (nummer, "höjd", latitud, longitud)
    values (1, 15.2, 59.230, 15.250);
insert into Buskar (nummer, "höjd", latitud, longitud)
    values (2, 25.2, 59.240, 15.250);
insert into Buskar (nummer, "höjd", latitud, longitud)
    values (3, 35.2, 59.250, 15.250);

create table "Blåbär"
(nummer integer not null primary key,
diameter float not null,
vikt float not null,
buske integer null references Buskar(nummer));

insert into "Blåbär" (nummer, diameter, vikt, buske)
    values (1, 10.0, 0.8, 1);
insert into "Blåbär" (nummer, diameter, vikt, buske)
    values (2, 8.0, 0.8, 3);
insert into "Blåbär" (nummer, diameter, vikt, buske)
    values (3, 10.0, 0.8, 3);
insert into "Blåbär" (nummer, diameter, vikt, buske)
    values (4, 10.0, 0.1, null);
insert into "Blåbär" (nummer, diameter, vikt, buske)
    values (5, 20.0, 0.4, null);
Det finns en miljard (109) blåbär och tio miljoner (107) blåbärsplantor. 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 skapar också några ytterligare index:

create index Busklatitud on Buskar(latitud);
create index Busklongitud on Buskar(longitud);
create index "Växerpå" on "Blåbär"(buske);

Uppgift 1 (5 p)

Skriv ett program som kopplar upp sig mot databasen, och som hjälper oss att söka efter blåbärsplantor. Man ska kunna skriva in fyra gränser: minsta och största latitud, minsta och största longitud. Programmet ska skriva ut koordinaterna (latitud och longitud) för alla blåbärsplantor som finns inom de angiva gränserna.

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)

a) Hur stor plats tar databasen? (Om man vill kan man räkna med att en integer tar 4 byte, en float 8 byte, och en blockpekare 8 byte.) Går den in på hårddisken på en normal skrivbordsdator eller bärbar dator? Visa hur du räknat!

b) Vi vill veta hur mycket alla blåbären väger tillsammans, så vi ställer följande SQL-fråga:

select sum(vikt)
from "Blåbär";
Här kan frågeoptimeraren inte göra så mycket, utan databashanteraren måste läsa hela tabellen Blåbär från början till slut. Hur lång tid tar frågan att köra? Visa hur du räknat!

c) Kan man få frågan att köras fortare om man skapar ett sekundärindex på vikt? Motivera svaret?

Uppgift 3 (5 p)

Vi vill veta hur många riktigt stora blåbär det finns på blåbärsplantorna i en viss geografisk ruta, och ställer följande SQL-fråga:
select "Blåbär".*
from "Blåbär", Buskar
where "Blåbär".buske = Buskar.nummer
and Buskar.latitud > 59
and Buskar.latitud < 59.01
and Buskar.longitud > 17
and Buskar.longitud < 17.001
and "Blåbär".vikt > 3;

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 heuristisk frågeoptimerare tar normalt inte hänsyn till datamängder eller lagringsstrukturer, men det skulle vara möjligt att skapa regler som gör det. Ge ett exempel på en sådan regel, som skulle påverka optimeringen av den här SQL-frågan!

Uppgift 4 (5 p)

Riktiga databashanterare, som Mimer, MySQL och SQL Server, har en kostnadsbaserad frågeoptimerare.

a) Beskriv hur en kostnadsbaserad frågeoptimerare fungerar.

b) Visa hur den skulle optimera SQL-frågan från uppgiften ovan. Vilken exekveringsplan kommer att väljas? (Det kan förstås bero på exakt vilka data som finns i databasen, men gör rimliga antaganden.) Hur skiljer sig den exekveringsplanen från vad den heuristiska optimeraren åstadkommer? Vilka index kommer att användas, och varför?

Uppgift 5 (5 p)

I en databashanterare körs fem olika transaktioner (T1 till T5) enligt följande tidsschema. Transaktionerna arbetar med tre olika dataobjekt (X, Y och Z). Räkneoperationer är inte med i tidsschemat, utan bara läs- och skrivoperationer och start respektive commit av transaktioner.

Tid T1 T2 T3 T4 T5
1 Start        
2   Start      
3     Start    
4       Start  
5       Läs(Z)  
6 Läs(X)        
7 Läs(Y)        
8   Läs(X)      
9   Skriv(X)      
10   Commit      
11     Läs(X)    
12     Skriv(Y)    
13     Commit    
14 Skriv(X)        
15 Commit        
16       Skriv(Z)  
17       Commit  
18         Start
19         Skriv(X)
20         Commit

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

b) (1p) Om vi ska avgöra om tidsschemat ovan är serialiserbart, inser vi snart att vi kan ignorera T4 och T5. Varför?

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!) Ignorera T4 och T5.

Uppgift 6 (5 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 nämnts 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 ett av dessa ä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 2016