Databasteknik II: Hemtentamen 2014-05-10

Instruktioner

1. Lös uppgifterna och skicka sen in svaren till mig (thomas.padron-mccarthy@oru.se) senast lördag 10 maj 2014. Sista inlämningsdagen håller på hela dagen, så senaste inlämningstid är vid midnatt.
2. Uppgiften ska lösas enskilt, dvs inga grupper av två eller flera studenter.
3. 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.
4. 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 tillåtas.
5. 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.
6. 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.
7. Antaganden utöver de som står i uppgifterna måste anges. Gjorda antaganden får inte förändra den givna uppgiften.
8. Oklara formuleringar kommer att misstolkas.
9. 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.
10. Om du behöver fråga något, så kontakta gärna mig. Om det är bråttom sig ä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 under lördagen.
11. Undvik Word-dokument. PDF eller text fungerar bättre.
12. 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

Träden består av noder och bågar, och vi kan beskriva dem med en tabell:

Varje nod har alltså ett unikt nummer, och högst en annan nod som förälder.

Exemplet ovan innehåller tretton noder och fyra träd. I schemat skogen i databasen dbk på Mimer-servern basen.oru.se finns ett större exempel, med ovanstående noder plus ytterligare en miljon:

SQL>select count(*) from skogen.noder;
 
===========
    1000013

                  1 row found

Alternativt kan man själv skapa och fylla databasen med hjälp av filen skapa-skogen.txt (64 megabyte) som innehåller SQL-kommandon för att skapa tabellen och fylla den med data. Den kan laddas ner här som en Zip-fil: skapa-skogen.zip (6 megabyte). Om man använder Mimer och Batch SQL kan filen läsas med Batch SQL:s kommando read, till exempel så här:

read all input from 'C:\Documents and Settings\tpy\Skrivbord\skapa-skogen.txt';

Uppgift 1 (5 p)

Exempel:

• Nod nummer 3 ska ge nod nummer 1 som rotnod.
• Nod nummer 4 ska ge nod nummer 1 som rotnod.
• Nod nummer 6 ska ge nod nummer 6 som rotnod.
• Nod nummer 100 ska ge nod nummer 100 som rotnod.
• I det större exemplet ska nod nummer 1000098 ge nod nummer 1000031 som rotnod.
• I det större exemplet ska nod nummer 1999997 ge nod nummer 1000000 som rotnod.

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)

select n1.nummer from noder as n1, noder as n2, noder as n3
where n1.foralder = n2.nummer
and n2.foralder = n3.nummer
and n3.nummer < 1000;

(Det är nod nummer 4, 5 och 17.)

a) Ange den systematiska översättningen av frågan, även kallad kanonsik 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) Vi antar att databashanteraren arbetar internt med relationsalgebra. Förklara skillnaden mellan att köra relationsalgebrauttrycket ovan med materialiserade mellanresultat och med strömmade mellanresultat ("pipe-lining").

d) 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.

e) Vilka saker finns i det optimerade uttrycket som en kostnadsbaserad frågeoptimerare (eller en heuristisk optimerare som bryr sig om datamängder och lagringsstrukturer) skulle kunna gjort bättre? (Alternativt, ifall det redan råkat bli helt perfekt, vad kunde den heuristiska optimeraren ha missat?)

Uppgift 3 (5 p)

Med kommandot SET EXPLAIN ON i Mimer kan man visa exekveringsplaner. Här är två sätt att visa vilka noder i exempeltabellen som har någon av noderna i det lilla exemplet som förälder.

SQL>set explain on;
SQL>select * from skogen.noder where foralder < 1000;
Start of explain result
 
L1:
      Index scan using index SKOGEN.FORALDER, end of table goto end
      compare, no hit goto L1
      Record found, goto L1
end:
 
End of explain result
 
     NUMMER    FORALDER
=========== ===========
          2           1
          3           1
          4           3
          5           3
          7           6
         11           6
         17          10
          8          19
         10          19

                  9 rows found

SQL>select * from skogen.noder where foralder < 1000000;
Start of explain result
 
L1:
      Sequential read SKOGEN.NODER, end of table goto end
      compare, no hit goto L1
      Record found, goto L1
end:
 
End of explain result
 
     NUMMER    FORALDER
=========== ===========
          2           1
          3           1
          4           3
          5           3
          7           6
          8          19
         10          19
         11           6
         17          10

                  9 rows found

SQL>

Förklara varför Mimer väljer olika exekveringsplaner!

Uppgift 4 (5 p)

Nu ska vi länka in det fjärde trädet från exemplet ovan, det med nod nummer 19 som rotnod, under ett av de andra träden. Vi startar en transaktion, som vi kan kalla transaktion A:

start transaction;                                   
select * from Noder where nummer = 19;

start transaction;                                 
select * from Noder where nummer = 19;
update Noder set foralder = 11 where nummer = 19;

update Noder set foralder = 5 where nummer = 19;

commit;

commit;

Man kan också skriva upp inmatningarna till de två SQL-sessionerna så här:

start transaction;
select * from Noder
where nummer = 19;

start transaction;
select * from Noder
where nummer = 19;
update Noder set foralder = 11
where nummer = 19;

update Noder set foralder = 5
where nummer = 19;

commit;

commit;

Vad händer? Visa hur låsen sätts och ändras, om någon av transaktionerna väntar, och vad resultatet blir. Avbryts någon transaktion? Kommer ändringar att rullas tillbaka?

Uppgift 5 (5 p)

Visa hur man kan använda tidsdimensionerna giltighetstid och transaktionstid i den här databasen för att lagra olika versioner av data. Hur behöver man ändra tabellerna? Blir det några särskilda problem, till exempel med integritetsvillkor? Finns det någon extra funktionalitet som det vore bekvämt att ha i databashanteraren?

Hade en temporal databas med transaktionstid hjälpt mot problemen ovan med ändringar i databasen? Visa hur, eller förklara varför det inte hade hjälpt.

Uppgift 6 (5 p)

a) Hade det varit bättre eller sämre att lagra den i form av en objektorienterad eller objektrelationell databas? Motivera svaret!

b) Hade det varit bättre eller sämre att inte lagra den som en databas alls, med databashanterare, utan bara med vanliga datastrukturer i ett språk som C eller Java? Motivera svaret!

c) Skogen växer från en miljon (10⁶) till en biljon (10¹²) noder. Ändras svaret i delfråga b? Motivera svaret!