Corrected version. 2002-01-31.
Mitthögskolan ITE Thomas Padron-McCarthy (tpm@nekotronic.se) Tentamen i Databaser C fredag 18 januari 2002
Hjälpmedel: Inga hjälpmedel. Poängkrav: Maximal poäng är 45. För godkänt krävs 23 poäng. Resultat: Meddelas på vanligt sätt. Visning: Tid för visning meddelas senare. Examinator och jourhavande: Thomas Padron-McCarthy, telefon 070-73 47 013
Anvisningar Läs igenom hela skrivningen och notera eventuella oklarheter innan du börjar lösa uppgifterna. 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, och 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: En databas för Mitthögskolans kurser och studenter innehåller följande tabeller. Du antas ha så mycket erfarenhet av datamodellering att du genast förstår vad tabellerna och kolumnerna betyder. student(snr, snamn, stad, födelsedatum) kurs(knr, knamn, institution) läser(student, kurs) godkänd(student, kurs) institution(inr, inamn)
Uppgifter: 1. (5p) Formulera följande frågor i relationsalgebra: a) Vilka studenter är godkända på en kurs som heter "Databaser C"? Svaret ska innehålla studenternas nummer och namn. b) Vilka studenter läser en kurs som heter "Databaser C" men är inte godkända på en kurs som heter "C++"? Svaret ska innehålla studenternas nummer och namn. c) Hur många kurser läser varje student? Studenter som inte läser några kurser ska inte vara med i svaret. Svaret ska innehålla studenternas nummer och namn, samt antalet. d) Hur många kurser läser varje student? Studenter som inte läser några kurser ska vara med i svaret, med antalet 0. Svaret ska innehålla studenternas nummer och namn, samt antalet. e) Vilka studenter läser ALLA kurser som ges av institutionen som heter "Elektromekanik"? Svaret ska innehålla studenternas nummer och namn. 2. (5p) Antag följande SQL-fråga: select student.snr, student.snamn from student, kurs, institution, läser where student.snr = läser.student and läser.kurs = kurs.knr and kurs.institution = institution.inr and institution.inamn = 'Vårdmatematik' a) Ange den systematiska översättningen till relationsalgebra. b) Rita upp frågeträdet för detta relationsalgebrauttryck, dvs det initiala frågeträdet ("initial query tree"). c) Vilka transformationer av frågeträdet görs i en heuristisk optimering? Beskriv de olika transformationerna, gärna med exempel, men du behöver inte rita upp hela trädet steg för steg. Rita dock upp hela slutresultatet. 3. (2p) Förklara principen för en kostnadsbaserad frågeoptimerare ("cost-based query optimizer"). Varför kan en sådan ge bättre resultat än en heuristisk frågeoptimerare? 4. (3p) Vilka likheter och skillnader finns mellan ODBC och ESQL? Vilka fördelar finns med ODBC jämför med ESQL? 5. (3p) I scenariot ovan använde Mitthögskolan en särskild tabell, läser, för att ange vilka studenter som läser vilka kurser. En överbetald konsult rekommenderar i stället Mitthögskolan att slå ihop tabellen kurs och tabellen läser, så att det står direkt i kurstabellen vilka studenter som läser kursen: kurs(knr, knamn, institution, student) a) Vad är primärnyckel i denna tabell? b) Vilka fullständiga funktionella beroenden ("full functional dependencies") finns? c) Vilken är den högsta normalform som tabellen uppfyller? d) Beskriv, med exempel, de problem som kan uppstå till följd av den låga normaliseringsgraden jämfört med det ursprungliga schemat. 6. (3p) Efter att ha fått skäll för sitt dåliga förslag ovan, föreslår samma inkompetenta konsult Mitthögskolan att i stället slå ihop tabellerna läser och godkänd, så att det blir så här: läser_gk(student, läser_kurs, godkänd_kurs) a) Vad är primärnyckel i denna tabell? b) Vilka fullständiga funktionella beroenden ("full functional dependencies") finns? c) Vilka flervärda beroenden ("multi-valued dependencies") finns? d) Vilken är den högsta normalform som tabellen uppfyller? e) Beskriv, med exempel, de problem som kan uppstå till följd av den låga normaliseringsgraden jämfört med det ursprungliga schemat. 7. (3p) Vilka är skillnaderna mellan objektorienterade databaser ("object-oriented databases"), ibland kallade "första generationens objektorienterade databaser", och objektrelationella databaser ("object-relational databases"), ibland kallade "andra generationens objektorienterade databaser"? För vilka typer av tillämpningar passar respektive typ? 8. (2p) Hur väljer man vilka index som är lämpliga för en viss databas? 9. (4p) Tabellen kurs innehåller tio tusen rader. Tabellen institution innehåller tio rader. Vi skapar (endast) följande index: create index foo1 on kurs(knr); create index foo2 on kurs(knamn); create index foo3 on institution(inr); Vi vill köra följande SQL-fråga: select kurs.knamn, kurs.knr from kurs, institution where institution.inamn = 'Vårdelektronik' and institution.inr = kurs.institution Antag att vi har en bra frågeoptimerare. Gör rimliga antaganden om blockstorlek mm, och ange dessa antaganden. a) Databasens index utgörs av (tillräckligt stora) hashtabeller. Hur lång tid kan man anta att det tar att köra frågan? b) Databasens index utgörs av B⁺-träd. Hur lång tid kan man anta att det tar att köra frågan? Förklara hur du räknat ut tiderna, gärna med figurer. 10. (2p) Hur skiljer sig strikt tvåfaslåsning ("strict two-phase locking") från vanlig tvåfaslåsning ("two-phase locking")? Vilket problem är det man löser med strikt tvåfaslåsning? Visa med exempel! 11. (2p) Vad behöver göras vid återstart ("återhämtning", "recovery") av ett databassystem? Tala om vad det är man vill åstadkomma, och (kort) hur det görs. 12. (5p) Vad är, och varför behöver man, ... a) datalager ("data warehouses")? b) XML c) k-d-träd ("k-d trees") d) CORBA e) RAID 13. (2p) En webbplats kan lagra data i en databas. Ett sätt att komma åt datat från webben är att använda CGI-script. Vilket (eller vilka) principiella alterantiv finns till CGI-script, och vad är fördelarna och nackdelarna med CGI respektive alternativen? 14. (4p) Mitthögskolan, som är en distribuerad högskola, vill förstås ha en distribuerad databas. Man fragmenterar tabellen student horisontellt med hjälp av attributet stad, enligt följande fragmenteringsschema: S₁ = SELECT_{stad="Sundsvall"}(student) S₂ = SELECT_{stad="Östersund"}(student) S₃ = SELECT_{stad="Bispgården"}(student) ("SELECT" ska egentligen vara grekiska bokstaven lilla sigma, men den går inte att skriva här.) a) Vilka antaganden måste vara uppfyllda för att denna fragmentering ska uppfylla fullständighetsvillkoret ("completeness")? b) Ange rekonstruktionsprogrammet ("reconstruction program") för relationen student. c) Vi vill veta kursnummer och kursnamn på de kurser som läses av studenter i Östersund. Formulera det som en SQL-fråga på de globala relationerna. d) Översätt till relationsalgebra. e) Lokalisera frågan genom att ersätta globala relationer med deras rekonstruktionsprogram. f) Förenkla detta relationsalgebrauttryck genom att reducera bort tomma deluttryck.