Örebro universitet
Institutionen för teknik
Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se)







Tentamen i

Databasteknik II

för D3 m fl

lördag 24 maj 2008 kl 08:00 - 12:00

Gäller som tentamen för:
DT3001 Datateknik C, Databasteknik II, provkod 0100
TDD119 Databaser, fortsättningskurs, provkod 0100






Hjälpmedel: Miniräknare.
Poängkrav: Maximal poäng är 38.
För betyget 3 krävs 19 poäng.
Resultat och lösningar: Meddelas via e-post eller på kursens hemsida, http://basen.oru.se/kurser/db2/2007-2008-p3/, senast lördag 14 juni 2008.
Återlämning av tentor: Efter att resultatet meddelats kan tentorna hämtas på institutionen. Man kan också få sin rättade tenta hemskickad.
Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-73 47 013.



LYCKA TILL!

Scenario till uppgifterna

Indien ska få ett system för elektroniska patientjournaler. Databasen ska konstrueras av forskare på SICS i Kista. (Här kan man läsa mer: http://computersweden.idg.se/2.2683/1.161843.) Det blir förstås en ganska stor databas, även om det finns många databaser som är större.

Här är ett ER-diagram för databasen. Den innehåller patienter, läkare och läkarbesök:

Ett ER-diagram

Vi antar att databasen lagras med en vanlig, diskbaserad relationsdatabashanterare på en vanlig, modern dator, men med mycket disk. Så här blir det:

Tabellen Patienter
(1 miljard rader)
Pid Namn Adress Stad Telefon
1 Singh Vägen 3 New Delhi 174590
2 Singh Gränden 11 Bangalore 260088
3 Gandhi Vägen 3 Bangalore 174590
... ... ... ... ...
Tabellen Läkare
(1 miljon rader)
Lid Namn Stad
1 Singh Bangalore
2 Krishnan New Delhi
3 Singh Mumbai
... ... ...
Tabellen Läkarbesök
(10 miljarder)
Bid Patient Läkare Datum
1 1 3 2008-05-20
2 1 645765 2008-05-20
3 987100966 3 2008-05-22
4 987100966 3 2008-05-23
... ... ... ...

Uppgift 1 (4 p)

Tabellen Patienter har en miljard rader. Vi vill söka efter en patient med ett visst nummer (Pid). Gör rimliga antaganden om blockstorlek mm (och ange dem!), och räkna sen ut hur lång tid det i genomsnitt tar att köra denna fråga, om tabellen är lagrad:

a) utan något index (eller annan sökväg) på numret

b) med ett primärindex i form av ett B+-träd på numret

c) som en hashtabell, hashad på numret

Ange antagandena, och visa hur du räknat!

Uppgift 2 (3 p)

Sverige, med 10 miljoner invånare, använder samma system. Hur lång tid tar frågan att köra i den svenska databasen, för de tre fallen a, b och c i uppgiften ovan?

(Du behöver inte göra uträkningarna på nytt, utan utgå från svaren i uppgiften ovan och resonera om hur tiderna ändras.)

Uppgift 3 (5 p)

Vi vill ha fram datumen för alla besök hos läkare i Bangalore:
select Datum
from "Läkare" as L, "Läkarbesök" as B
where L.Lid = B."Läkare"
and L.Stad = 'Bangalore';

a) (1p)

Skriv upp den systematiska (o-optimerade) översättningen av frågan, även kallad kanonisk form, som ett relationsalgebrauttryck.

b) (1p)

Rita upp samma relationsalgebrauttryck som ett träd.

c) (3p)

Visa hur en heuristisk frågeoptimerare, som inte tar hänsyn till datamängder eller lagringsstrukturer, optimerar den kanoniska formen från frågan ovan. Visa både vilka olika optimeringar som görs, och vad slutresultatet blir.

Uppgift 4 (8 p)

Beskriv fyra olika tekniker för att kommunicera med en relationsdatabas från ett vanligt program. (Vad heter de? Vilka språk och plattformar går de att använda på? Hur lättanvända är de? Vilket stöd av programmeringverktyg finns? Hur flexibla är de?)

Uppgift 5 (5 p)

a) (2p) Vilka två olika tidsdimensioner brukar man tala om i en temporal databas? Vad betyder de?

b) (1p) Och vad menas egentligen med en tidsdimension?

c) (2p) De flesta databashanteraren har inget inbyggt stöd för tidsdimensioner, men man kan representera tidsdimensionerna i en vanlig relationsdatabas genom att lägga till extra kolumner. Men vilka problem uppstår, som är svåra att hantera?

Uppgift 6 (3 p)

När man programmerar idag använder man oftast objektorienterad programmering, med klasser och objekt. Men trots att det finns objektorienterade databaser, så har de inte blivit särskilt populära, utan man fortsätter med relationsdatabaser, även när ett objektorienterat program ska lagra sina data.

Vad tror du att det beror på?

Uppgift 7 (6 p)

a) (2p)

Den vanligaste metoden för att hindra samtidiga transaktioner från att störa varandras uppdateringar och läsningar är tvåfaslåsning. Visa med ett exempel hur tvåfaslåsning fungerar!

b) (2p)

Grundläggande tvåfaslåsning hanterar inte deadlock. Hur kan man hantera problemet med deadlock i en databashanterare som använder tvåfaslåsning?

c) (2p) Grundläggande tvåfaslåsning har problem om transaktioner kan avbrytas och rullas tillbaka. Visa vad som kan hända, och hur man kan lösa problemet genom att ändra algoritmen.

Uppgift 8 (4 p)

a) Vad är ett datalager?

b) Vad använder man datalager till?

c) Varför har man datalager till det, i stället för att använda vanliga databaser?