Corrected version. 2002-03-22.

Mitthögskolan
ITE
Thomas Padron-McCarthy (tpm@nekotronic.se)
Tentamen i

Datateknik C, Databaser 5 poäng

onsdag 20 mars 2002

(This exam is available in a Swedish and an English version.)

Hjälpmedel: Inga hjälpmedel.
Poängkrav: Maximal poäng är 43.
För godkänt krävs 21 poäng.
Resultat: Meddelas på kursens hemsida senast onsdag 3 april 2002.
Visning: Tid för visning meddelas i samband med resultatet.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-7347013

Förutom anvisningarna på skrivningsomslaget gäller följande:

LYCKA TILL!

Scenario till uppgifterna:

Statens Järnvägar, SJ, har en databas för biljettbokningar. Som en del i den databasen ingår en tidtabell över alla tåglinjer. Den innehåller tågturer, stationer, hur tågturerna stannar på stationerna, och tåg.

En tågtur, eller "route" på engelska, är, till exempel, tåget från Östersund till Sundsvall varje vardag klockan 09:12. Ett "tåg" är ett verkligt, individuellt tåg, till exempel det där tåget där borta som just nu lämnar Östersund på väg mot Sundsvall.

Här är ett Entity-Relationship-diagram:

Och här är tabellerna:

Station(Snr, Name)
Stops(Route, Station, Number, Time);
Route(Rnr, Days)
Train(Tnr, Route, Date)

Exempeldata:

Stops
Route Station Number Time
3 3 1 09:12
3 2 2 10:41
3 1 3 10:44
3 4 4 16:31
... ... ... ...
              Station
Snr Name
1 Sundsvalls Central
2 Sundsvalls Västra
3 Östersunds Central
4 Stockholms Central
... ...
 
Route
Rnr Days
1 Sun
2 Mon, Tue, Wed, Thu, Fri, Sat, Sun
3 Mon, Tue, Wed, Thu, Fri
4 Sun
... ...
              Train
Tnr Route Date
1 3 2002-03-20
2 3 2002-03-21
3 3 2002-03-22
... ... ...

Radantal i tabellerna:

Uppgift 1 (2p)

Det finns ett normaliseringsproblem med tabellen Route. Förklara vad problemet är, och varför det är ett problem.

Uppgift 2 (7p)

Vi vill ha svar på följande fråga:

Vilka tåg stannar på stationen Sundsvalls Västra datumet 2002-03-20? Svaret ska innehålla tågnumret (Tnr).

Vi använder den här SQL-frågan: 

select Train.Tnr
from Station, Stops, Route, Train
where Station.Name = 'Sundsvalls Västra'
      and Station.Snr = Stops.Station
      and Stops.Route = Route.Rnr
      and Route.Rnr = Train.Route
      and Train.Date = '2002-03-20'

a) (1p) Gör den systematiska översättningen av SQL-frågan till det initiala frågeträdet, och rita upp trädet!

b) (1p) Skriv detta initiala frågeträd som ett relationsalgebrauttryck (alltså inte uppritat som ett träd).

c) (2p) En heuristisk frågeoptimerare gör om frågeträdet till en mer effektiv form. Rita upp resultatet!

d) (2p) Förklara varför detta nya träd är mer effektivt än det initiala frågeträdet. Vilka förbättringar har gjorts? Varför går frågan (förmodligen) snabbare att köra nu?

e) (1p) Vilka brister finns med en heuristisk frågeoptimerar av den här typen? Om man i stället använder kostnadsbaserad frågeoptimerare, kan en del av bristerna övervinnas. Hur?

Uppgift 3 (2p)

Vi vill ha svar på följande fråga:

Jag vill åka från Sundsvalls Västra till Stockholms Central datumet 2002-03-20. Vilka tider kan jag åka?

Vi använder den här SQL-frågan: 

select firststop.Time
from Station as firststn, Station as laststn,
     Stops as firststop, Stops as laststop, Route, Train
where firststn.Name = 'Sundsvalls Västra'
      and firststn.Snr = firststop.Station
      and firststop.Route = Route.Rnr
      and laststn.Name = 'Stockholms Central'
      and laststn.Snr = laststop.Station
      and laststop.Route = Route.Rnr
      and Route.Rnr = Train.Route
      and Train.Date = '2002-03-20'
      and firststop.Number < laststop.Number
Formulera SQL-frågan som ett relationsalgebrauttryck på valfritt sätt. (Om du vill kan du i stället rita den som ett frågeträd, men det är inte nödvändigt.)

Uppgift 4 (5p)

Frågor av typen i de två uppgifterna ovan är vanliga i den här databasen. (Man kan förstås ha olika stationsnamn och datum.) Vi använder en databashanterare som har index i form av B+-träd.

a) (4p) Vilka index bör man skapa?

b) (1p) Kan DBA:n göra något mer, förutom att skapa index, för att snabba upp frågorna?

Uppgift 5 (5p)

Vi vill veta vilket datum tåg nummer 4711 går, och ställer följande SQL-fråga: 
select Date
from Train
where Tnr = 4711
Gör rimliga antaganden om diskblocksstorlek mm, och räkna ut hur lång tid frågan i genomsnitt kommer att ta att köra

a) med tabellen Train lagrad som en osorterad heap, och inga index

b) med ett primärindex i form av ett B+-träd på attributet Tnr, och inga andra intressanta lagringsstrukturer

c) med ett sekundärindex i form av en hashtabell på attributet Tnr, och inga andra intressanta lagringsstrukturer.

Uppgift 6 (2p)

SJ expanderar, och tar över all tågtrafik i hela världen. Databasen växer förstås, med alla nya tågturer, och alla fyra tabellerna blir tusen gånger större: Vad händer nu med svarstiderna i a-c i uppgiften ovan?

Uppgift 7 (3p)

SJ vill lägga in kartor över tåglinjer och stationer i sin databas.

a) (1p) Varför fungerar vanliga index, som B+-träd och hashtabeller, inte så bra med tvådimensionella data, som kartor?

b) (2p) Ge exempel på en datastruktur som man kan använda i stället, och beskriv kort hur den fungerar.

Uppgift 8 (3p)

Vi vill veta hur många tågturer som stannar på varje station, och vi börjar med att prova den här SQL-frågan: 
select Station.Name, count(*)
from Station, Stops
where Station.Snr = Stops.Station
group by Station.Name
a) (1p) Översätt den givna SQL-frågan till ett relationsalgebrauttryck.

b) (1p) Det finns några nybyggda stationer, där inga tågturer stannar än. De stationerna kommer inte med alls i resultatet av frågan ovan. Skriv en ny SQL-fråga, där även de nya stationerna finns med i resultatet, med noll i kolumnen för antalet tågturer som stannar.

c) (1p) Översätt den nya SQL-frågan till ett relationsalgebrauttryck.

Uppgift 9 (2p)

Många databashanterare erbjuder ett bibliotek av funktioner, som man kan använda för att komma åt en databas inifrån ett program. Ett annat alternativ är ODBC. Vilka fördelar och nackdelar finns med att använda ODBC i stället för databashanterarens eget funktionsbibliotek?

Uppgift 10 (5p)

Som vi nämnt ovan, så tar SJ över all tågtrafik i hela världen. På grund av detta lägger vi till en landskolumn, Country, i tabellen Station:

Station
Snr Name Country
1 Sundsvalls Central Sweden
2 Sundsvalls Västra Sweden
2877 Trondheim Norway
4876 Notting Hill Gate UK
6777 New Delhi East India
... ... ...

Vi vill också distribuera databasen. Varje land får sitt eget fragment av tabellen Station, med hjälp av primär horisontell fragmentering baserad på attributet Country:

Vi vill också fragmentera tabellen Stops, och lagra raderna för stoppen i de olika länderna. Vi använder sekundär horisontell fragmentering, baserad på fragmenteringen av tabellen Station.

a) (1p) Ange fragmenteringsschemat för relationen Stops

b) (0.5p) Ange återskapandeprogrammet ("reconstruction program") för relationen Station

b) (0.5p) Ange återskapandeprogrammet för relationen Stops

d) (1p) Vi vill veta den tidigaste tid på dagen som ett tåg någonsin stannar på Sundsvalls Central i Sverige (Sweden). Vi använder den här SQL-frågan: 

select min(Stops.Time)
from Station, Stops
where Station.Snr = Stops.Station
and Station.Name = "Sundsvalls Central"
and Station.Country = "Sweden"
Översätt detta till ett effektivt relationsalgebrauttryck, med de globala relationerna.

e) (1p) Lokalisera ("localize") relationsalgebrauttrycket ovan genom att byta ut de globala relationerna mot deras återskapandeprogram.

f) (1p) Förenkla det relationsalgebrauttrycket genom att reducera bort deluttryck som ger tomma resultat.

Uppgift 11 (4p)

Isolering i ACID-transaktioner görs för det mesta med lås.

a) (1p) Ibland används läs- och skrivlås, i stället för vanliga binära lås. Hur fungerar läs- och skrivlås?

b) (1p) Varför vill man använda läs- och skrivlås i stället för vanliga binära lås?

c) (2p) Varför är låsning svårare i en distribuerad databas än i en centraliserad databas? Hur gör man? Blir det några särskilda svårigheter om man vill ha läs- och skrivlås i en distribuerad databas?

Uppgift 12 (3p)

I vissa system, som Microsoft ASP och Roxen WebServer, kan man stoppa in SQL-frågor i vanliga HTML-webbsidor. Här är ett exempel från Roxen WebServer, som visar en sådan SQL-fråga i HTML-kod: 
<table border="1">
<tr><th>Number</th> <th>Name</th></tr>
<emit source="sql" host="foodbase" query="select id, name
                                          from person order by id">
<tr><td>&_.id;</td> <td>&_.name;</td></tr>
</emit>
</table>
a) (1p) Förklara kort vad som händer inuti webbservern när den stöter på en SQL-fråga som den här.

b) (2p) Det är praktiskt att kunna stoppa in SQL-frågor i HTML-koden så här, men finns det andra fördelar jämfört med alternativen? Och vilka är alternativen?