Databasteknik II: Hemtentamen 2013-05-18

Instruktioner

1. Lös uppgifterna och skicka sen in svaren till mig (thomas.padron-mccarthy@oru.se) senast klockan 08:00 söndag 19 maj 2013.
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. 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.
5. 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).
6. Antaganden utöver de som står i uppgifterna måste anges. Gjorda antaganden får inte förändra den givna uppgiften.
7. Oklara formuleringar kommer att misstolkas.
8. 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.
9. Om du behöver fråga något, så kontakta gärna mig. Det är nog bäst att ringa eller SMS:a (se mobilnumret ovan), för det är inte säkert att jag sitter vid datorn under lördagen.
10. Undvik Word-dokument. PDF eller text fungerar bättre.
11. 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

Sverige är uppdelat i 21 län, till exempel Örebro län och Jämtlands län. Varje län har ett unikt namn, men också en unik länskod och en unik länsbokstav (som i en del fall utgörs av två bokstäver!). Varje län har också en folkmängd. Dessutom har varje län en residensstad, där landshövdingen bor. Det är en tätort som ligger i det länet. (Läs mer om Sveriges län i Wikipedia.)

Varje län delas sedan in i flera kommuner, till exempel Örebro kommun och Kumla kommun, som båda finns i Örebro län. Totalt finns det 290 kommuner. Varje kommun har ett unikt namn och en unik kommunkod, och en folkmängd. (Läs mer om Sveriges kommuner i Wikipedia. De har hela listan.)

Varje kommun innehåller en eller flera tätorter. Som exempel finns i Örebro kommun 14 olika tätorter: Örebro, Hovsta, Garphyttan, Odensbacken, Vintrosa, Ekeby-Almby, Stora Mellösa, Glanshammar, Norra Bro, Latorpsbruk, Ölmbrotorp, Hampetorp, Kilsmo och Askersby. Totalt finns det 1956 tätorter. Varje tätort har ett namn och en folkmängd. Det kan inte finnas två tätorter med samma namn i en och samma kommun, men i olika kommuner kan det finnas tätorter som har samma namn. För att tätorterna ska få en enkel nyckel har de en unik tätortskod. De flesta av tätorterna (men inte riktigt alla) har kartkoordinater i form av latitud och longitud, och en höjd över havet ("elevation"). (Läs mer om Sveriges tätorter i Wikipedia. De har hela listan.)

Kod är primärnyckel i samtliga tabeller.

I tabellen Län är Bokstav och Namn två olika alternativnycklar.
I tabellen Kommuner är Namn en alternativnyckel.
I tabellen Tätorter bildar Namn och Kommun en sammansatt alternativnyckel.

Län.Residensstad refererar till Tätorter.Kod
Kommuner.Län refererar till Län.Kod
Tätorter.Kommun refererar till Kommun.Kod

Tabellerna finns i schemat sverige i databasen dbk på Mimer-servern basen.oru.se.

Alternativt kan man själv skapa och fylla databasen med hjälp av filen skapa-sverige-databasen.txt, som innehåller SQL-kommandon för att skapa tabellerna och fylla dem med data. 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-sverige-databasen.txt';

Uppgift 1 (5 p)

Uppgift 2 (5 p)

Uppgift 3 (5 p)

start transaction;                                   
select * from "Län"
where namn = 'Kalmar län';

start transaction;                                 
select * from "Län"
where namn = 'Kalmar län';

update "Län"
set namn = 'Smålands län'
where namn = 'Kalmar län';

update "Län"
set namn = 'Ölands län'
where namn = 'Kalmar län';

commit;

commit;

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

start transaction;
select * from "Län"
where namn = 'Kalmar län';

start transaction;
select * from "Län"
where namn = 'Kalmar län';

update "Län"
set namn = 'Smålands län'
where namn = 'Kalmar län';

update "Län"
set namn = 'Ölands län'
where namn = 'Kalmar län';

commit;

commit;

Vad händer? Visa hur låsen sätts och ändras, om någon av transaktionerna väntar, och vad resultatet blir.

Uppgift 4 (5 p)

SELECT "Tätorter".namn
FROM "Tätorter", Kommuner, "Län"
WHERE "Tätorter".kommun = Kommuner.kod
AND Kommuner."län" = "Län".kod
AND "Tätorter"."folkmängd" > 1000
AND Kommuner."folkmängd" < 4000
AND "Län".namn = 'Västerbottens län';

(Det är Malå, Sorsele, Dorotea och Åsele.)

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

Meningen är att man ska resonera och räkna sig fram till svaret, inte att man ska provköra. Gör rimliga antaganden om olika saker, och ange dessa antaganden. Förklara också hur du räknat.