Databasteknik II: Hemtentamen 2014-08-30

Instruktioner

1. Lös uppgifterna och skicka sen in svaren till mig (thomas.padron-mccarthy@oru.se) senast lördag 30 augusti 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. 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 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 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 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

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 noderna 4 och 5 som svar.
• Nod nummer 4 ska inte ge några noder alls som svar.
• Nod nummer 6 ska ge noderna 7 och 11 som svar.
• Nod nummer 100 ska inte ge några noder alls som svar.
• I det större exemplet ska nod nummer 1500000 ge nod nummer 1913791 som svar.
• I det större exemplet ska nod nummer 1100000 ge noderna 1192188, 1963529, 1213436, 1274395, 1299314, 1436452 och 1711955 som svar

(Man kan också välja att ha med subträdets rotnod i utskriften, om det ger enklare kod.)

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 max(nummer) from skogen.noder;
select count(*) from skogen.noder;

Uppgift 3 (5 p)

select * from skogen.noder where foralder = 1000000;

a) Om det inte finns några index alls på tabellen.

b) Om det finns ett primärindex av typen B⁺-träd på kolumnen nummer.

c) Om det finns ett sekundärindex av typen B⁺-träd på kolumnen foralder.

d) Om det finns två olika index av typen B⁺-träd på kolumnerna nummer och foralder. Det är ett primärindex respektive ett sekundärindex.

e) Om det finns ett sammansatt index av typen B⁺-träd på kolumnerna nummer och foralder. Det är ett primärindex.

(Meningen är alltså att man ska resonera och räkna sig fram till svaret, inte att man ska provköra.)

Uppgift 4 (5 p)

select barnbarn.nummer from skogen.noder as mormor, skogen.noder as barn, skogen.noder as barnbarn
where mormor.nummer = 1000000
and barn.foralder = mormor.nummer
and barnbarn.foralder = barn.nummer
and barnbarn.nummer > 1500000

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 optimerare följer några enkla regler för vilka transformationer den ska göra på relationsalgebran. Finns det några uppenbara problem (dvs långsamma val) med det färdiga, optimerade trädet i c-uppgiften ovan, om man jämför med hur en riktig databashanterare som Mimer faktiskt skulle köra frågan?

Uppgift 5 (5 p)

I tidsschemat ovan användes ingen metod för att hålla transaktionerna isolerade från varandra.

a) Är tidsschemat serialiserbart? Motivera svaret!

b) Visa hur tidsschemat ovan skulle förändras om man använder strikt tvåfaslåsning med läs- och skrivlås, där inga lås (inte ens läslås) släpps förrän efter att transaktionen har committat. Visa också låsen och hur de låses och låses upp.

c) Visa hur det ursprungliga tidsschemat skulle förändras om man använder tidsstämpelmetoden, med lästids- och skrivtidsstämplar. Visa också tidsstämplarna.

Uppgift 6 (5 p)

1. Tid i databaser, temporala databaser
2. Objektorienterade och objektrelationella databaser
3. Datautvinning ("data mining") och datalager ("data warehouses")
4. Distribuerade databaser, multidatabaser
5. Legacy databases, mediatorer
6. SQL, NoSQL och NewSQL
7. Object-relational mapping

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.