Databasteknik II: Hemtentamen 2016-05-29

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 ett ER-diagram för databasen:

Det vi lagrar i databasen är detta:

• Blåbär. Varje blåbär har ett unikt nummer, en diameter (mätt i millimeter) och en vikt (mätt i gram).
• Blåbärsbuskar. Varje blåbärsbuske har ett unikt nummer, en höjd (mätt i centimeter), och en position (som anges med latitud och longitud).
• Blåbären växer på blåbärsbuskarna. En del blåbär har ramlat ner på marken och ligger där och skräpar, men annars hör varje blåbär till en blåbärsbuske.

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);

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)

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)

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";

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

Uppgift 3 (5 p)

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)

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)

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.

• Tvåfaslåsning med enkla binära lås
• Tvåfaslåsning med läs- och skrivlås
• Tidsstämpelmetoden, utan Thomas skrivregel (Thomas's Write Rule)
• Tidsstämpelmetoden, med Thomas skrivregel (Thomas's Write Rule)
• En optimistisk metod som i Mimer

Uppgift 6 (5 p)

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

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.