Tentamen i Datateknik C, Databaser 2003-01-15

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

Tentamen i

Datateknik C, Databaser 5 poäng

onsdag 15 januari 2003

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

Hjälpmedel:	Inga hjälpmedel.
Poängkrav:	Maximal poäng är 60. För godkänt krävs 30 poäng.
Resultat och lösningar:	Meddelas på kursens hemsida senast onsdag 29 januari 2003.
Examinator och jourhavande:	Thomas Padron-McCarthy, telefon 070-7347013

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

Skriv tydligt och klart. Lösningar som inte går att läsa kan naturligtvis inte ge några poäng. Oklara formuleringar kommer att misstolkas.
Lös bara en uppgift per blad. 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 förstås inte förändra den givna uppgiften.

LYCKA TILL!

Scenario till uppgifterna

Hulda gör en databas över sina CD-skivor. Den består av tre tabeller:

Artist(Anr, Namn, Land)
Skiva(Snr, Namn, Artist)
Låt(Skiva, Ordningsnummer, Namn, Längd)

I tabellen Artist är Anr primärnyckel och Namn alternativnyckel. I tabellen Skiva är Snr primärnyckel, och Artist är referensattribut till Anr i tabellen Artist. Dessutom är kombinationen av Namn och Artist en alternativnyckel. I tabellen Låt bildar Skiva och Ordningsnummer en sammansatt nyckel, och Skiva är referensattribut till Snr i tabellen Skiva.

Uppgift 1 (5p)

Formulera följande frågor både i SQL och med relationsalgebra:

a) (1p) Vad är namnen på de de skivor som gjorts av artisten Carola?

b) (2p) Vad är den sammanlagda längden av alla låtar på skivan Främling av Carola?

c) (2p) Vilka artister finns med i databasen, utan att några av deras skivor finns med? Vi vill veta namnen på de artisterna.

Uppgift 2 (3p)

Frågor av typen (b) ovan, som kräver att man summerar låtlängderna på en skiva, visar sig vara mycket vanliga. För att snabba upp dessa frågor lägger Hulda till en kolumn Längd i tabellen Skiva, som ska innehålla den sammanlagda längden av alla låtarna på den skivan. Hulda tycker att det är besvärligt att hålla värdena i den kolumnen uppdaterade så att de stämmer med den verkliga summan av låtlängder. Till exempel måste hon komma ihåg att ändra innehållet i Längd om hon upptäcker att en låtlängd var fel och behöver ändras. Visa hur en aktiv databas skulle kunna underlätta det arbetet! (Du behöver inte skriva någon exakt riktigt SQL-kod för det här, men förklara vad Hulda ska göra, och vad databashanteraren kommer att göra.)

Uppgift 3 (8p)

Artisten Carola har spelat in en låt som heter Fjortonde maj, och vi vill veta vilken skiva den finns med på. Därför ställer vi följande SQL-fråga:

select Skiva.Namn
from Artist, Låt, Skiva
where Artist.Namn = 'Carola'
and Låt.Namn = 'Fjortonde maj'
and Låt.Skiva = Skiva.Snr
and Skiva.Artist = Artist.Anr;

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

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

c) (2p) Förklara vilka förändringar som gjordes av den heuristiska frågeoptimeraren, och varför de (förmodligen) gör att frågan går snabbare att köra.

d) (1p) Om ett frågeträd ska köras av databashanteraren, kan den göra på två olika sätt: materialisering eller pipe-lining (även kallat "stream-based processing"). Förklara skillnaden.

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

Uppgift 4 (7p)

a) (4p) Välj två olika algoritmer som databashanteraren kan använda internt för att utföra join-operationen, och beskriv hur de fungerar.

b) (2p) Är en av de två algoritmerna alltid bäst, eller kan vilken som är bäst variera, och vad beror det i så fall på?

c) (1p) Vad innebär "bäst" i delfråga b ovan?

Uppgift 5 (10p)

Här har vi nu skiva nummer 717. Vem har gjort den? Vi ställer följande SQL-fråga:

select Artist.Namn
from Skiva, Artist
where Snr = 717
and Skiva.Artist = Artist.Anr;

Hulda har 1000 skivor, med 100 olika artister. I genomsnitt finns det tio låtar på varje skiva. Hon har inte brytt sig om att definiera några index eller andra användbara fysiska datastrukturer. Databashanteraren har en bra frågeoptimerare.

a) (2p) 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.

b) (2p) Hulda börjar jobba på radiostationen Radio Megamix (med "den tråkigaste blandningen av låtar man hört förut") och bestämmer sig för att använda en likadan databas för radiostationens alla skivor. Radiostationens skivsamling är tusen gånger större än Huldas, så den databasen innehåller 1000000 (10⁶) skivor, med 100000 (10⁵) olika artister. Det finns fortfarande i genomsnitt tio låtar på varje skiva. Hur lång tid tar det nu att köra samma fråga, fortfarande utan några index eller andra användbara fysiska datastrukturer?

c) (2p) Hulda tycker att det går för långsamt. Vilka index bör hon skapa för att just den här frågan ska gå snabbt att köra? Motivera svaret.

d) (4p) Hulda skapar dessa index. Huldas databashanterare använder B⁺-träd för sina index. Hur lång tid tar frågan nu att köra? Visa hur du räknat.

Uppgift 6 (4p)

Radiostationen Radio Megamix ska göra sitt skivregister sökbart via webben, så att lyssnarna kan önska skivor. Därför behöver de koppla sin webbplats till databasen med skivregistret. Hulda funderar på att använda CGI-script.

a) (2p) Beskriv hur CGI-script skulle fungera i det här fallet, för att data från databasen ska komma till surfarens webbläsare.

b) (2p) Vilka alternativ finns det till CGI-script i det här fallet? Vilka fördelar och nackdelar har de, jämfört med CGI-script?

Uppgift 7 (4p)

De som arbetar på radiostationen behöver förstås också komma åt databasen. De skulle kanske kunna jobba via webben, men Hulda, som är databasadministratör, bestämmer sig för att skriva ett särskilt program. För att programmet ska kunna komma åt databasen väljer Hulda mellan tre olika tekniker: ODBC, ESQL och databashanterarens eget funktionsbibliotek. Förklara kort hur de olika teknikerna fungerar, och vilka fördelar och nackdelar de har jämfört med varandra. Skulle du rekommendera någon särskild av dem? Motivera svaret!

Uppgift 8 (12p)

Alla de anställda på radiostationen jobbar flitigt med att lägga in alla skivorna i databasen, och rätta eventuella fel. Som tur är har databashanteraren ACID-transaktioner.

a) (4p) Beskriv för var och en av de fyra egenskaperna (A, C, I och D) vad den innebär, och vad som skulle kunna hända om den inte fanns.

b) (4p) Databashanteraren använder tvåfaslåsning av enklaste sort, där alla data låses så sent som möjligt, och låses upp så tidigt som möjligt. Två transaktioner, T1 och T2, körs samtidigt, och om inga lås fanns skulle deras operationer köras i den här ordningen:

Steg	Transaktion T1	Transaktion T2
1	Read(A)
2	Read(B)
3	A = A + B
4	B = 0
5		Read(C)
6		B = C
7		C = 0
8		Write(B)
9	Write(B)
10	Write(A)
11		Write(C)

Visa hur de båda transaktionerna låser och låser upp dataobjekten A, B och C, och hur de (kanske) måste vänta.

c) (4p) Nu använder databashanteraren i tidsstämpelmetoden, som den beskrivis i kursboken, med den så kallade "Thomas's Write Rule". Transaktionernas operationer köras i samma ordning som i tabellen ovan. Visa vad som händer, inklusive hur tidsstämplarna i databasen ändras. Ange om någon transaktion måste avbrytas. (I så fall behöver du inte visa vad som händer efter att transaktionen avbryts, utan du kan avsluta din lösning där.)

Uppgift 9 (3p)

Hulda lägger in sökbara kartor i databasen, för att visa var radiostationens lyssnare finns. Visa hur ett k-d-träd respektive ett quad-träd, som ska indexera följande punkter, kan se ut:

Ett koordinatsystem med punkter

Förklara träden du har ritat.

Uppgift 10 (4p)

Förklara kort följande begrepp:

objekt-relationell databas (på engelska: object-relational database)
återskapandeprogram (på engelska: reconstruction program)
datalager (på engelska: data warehouse)
kaskad-rollback (på engelska: cascade rollback)