Databasteknik II: Hemtentamen 2013-05-18

Det här är hemtentan som går lördag 18 maj 2013 i kursen Databasteknik II. 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 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

Vi lagrar Sveriges län, kommuner och tätorter i de tre tabellerna Län, Kommuner och Tätorter:

Län
Kod Bokstav Namn Folkmängd Residensstad
01 AB Stockholms län 2127006 336
03 C Uppsala län 341977 656
18 T Örebro län 283113 6188
.... .... .... .... ....

Kommuner
Kod Namn Folkmängd Län
180 Stockholms kommun 881235 1
1880 Örebro kommun 138952 18
1881 Kumla kommun 20738 18
.... .... .... ....

Tätorter
Kod Namn Kommun Folkmängd Latitud Longitud Elevation
336 Stockholm 180 1372565 59.332580 18.064900 20
656 Uppsala 380 140454 59.858500 17.645430 10
6188 Örebro 1880 107038 59.274120 15.206600 30
5900 Askersby 1880 243 null null null
5924 Ekeby-Almby 1880 1271 59.260000 15.330000 25
6076 Odensbacken 1880 1374 59.166670 15.533330 18
6116 Stora Mellösa 1880 776 59.216670 15.500000 32
6020 Kumla 1881 14062 59.127700 15.143410 40
6164 Åbytorp 1881 755 59.116670 15.066670 60
.... .... .... .... .... .... ....

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';
Det finns också en annan fil där namn på tabeller och kolumner har rensats från svenska tecken: skapa-sverige-databasen-utan-aao.txt. Där heter tabellerna Lan, Kommuner och Tatorter. Välj själv om du vill använda den i stället.

Uppgift 1 (5 p)

Skriv ett program som kopplar upp sig mot databasen. Programmet ska fråga efter namnet på en kommun, och sen skriva ut alla tätorter som ligger i den kommunen. Det ska ske med 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)

Databasens innehåll ändras ibland. Kommuner slås ihop och delas, folkmängder ändras, och så vidare. Dessutom förekommer det fel i databasen, som rättas. 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?

Uppgift 3 (5 p)

Vi tänker oss att databasen hanteras av en databashanterare som använder tvåfaslåsning med läs/skriv-lås. Nu ska vi byta namn på Kalmar län, men det är lite oklart exakt vad det nya namnet ska bli. Vi startar en transaktion, låt oss kalla den transaktion A:
start transaction;                                   
select * from "Län"
where namn = 'Kalmar län';
Strax efteråt startar någon annan en annan transaktion, transaktion B:
start transaction; select * from "Län" where namn = 'Kalmar län';
Därefter fortsätter transaktion A:
update "Län"
set namn = 'Smålands län'
where namn = 'Kalmar län';
Och sedan fortsätter transaktion B:
update "Län"
set namn = 'Ölands län'
where namn = 'Kalmar län';
Transaktion A committar:
commit;
Transaktion B committar:
commit;

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

Step Transaktion A Transaktion B
1
start transaction;
select * from "Län"
where namn = 'Kalmar län';
 
2  
start transaction;
select * from "Län"
where namn = 'Kalmar län';
3
update "Län"
set namn = 'Smålands län'
where namn = 'Kalmar län';
 
4  
update "Län"
set namn = 'Ölands län'
where namn = 'Kalmar län';
5
commit;
 
6  
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)

Här är en SQL-fråga som söker fram vilka tätorter i Västerbottens län som har mer än 1000 invånare och som ligger i kommuner som har mindre än 4000 invånare.

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)

Ungefär hur lång tid tar det att köra SQL-frågan från uppgiften ovan?

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.


Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 18 maj 2013