• Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara och tvetydiga formuleringar kommer att misstolkas.
• Skriv den personliga tentamenskoden på varje inlämnat blad. Skriv inte namn eller personnummer på bladen.
• Skriv bara på en sida av papperet. Använd inte röd skrift.
• Antaganden utöver de som står i uppgifterna måste anges. Gjorda antaganden får inte förändra den givna uppgiften.
• 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.

Scenario till uppgifterna

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

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

Uppgift 1 (4 p)

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)

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

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)

Uppgift 5 (5 p)

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)

Vad tror du att det beror på?

Uppgift 7 (6 p)

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)

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?