Tentamen Databases voor iku 17 april 2013 13:30 - 16:30, Educatorium-Gamma • Scheur de antwoordvellen doormidden. • Maak elke vraag op een ander vel. • Vermeld op elk vel je naam en studentnummer. Indien ´e´en van deze zaken ontbreekt, wordt het vel niet nagekeken. • Toon bij het inleveren je collegekaart. • Schrijf en formuleer duidelijk. • Je mag een A4 met aantekeningen raadplegen. • Het tentamen duurt 3 uur en bestaat uit 6 opgaven. • Gebruikte afko’s: 2PL = Two-phase locking 2PC = Two-phase commit BCNF = Boyce-Codd normaalvorm COORD = Coordinator DP = Dependency preserving FD = functional dependency RA = Relationele algebra SQL = SQL (Structured Query Language) • Vergeet niet de vakevaluatie in te vullen. Zie de education pagina. • Succes!
Puntentelling: 1: 20 punten 2: 20 punten 3: 20 punten 4: 20 punten 5: 10 punten 6: 10 punten 1
1
Algemeen
Geef van de volgende beweringen aan of deze correct zijn of niet. Een simpel JA of NEE volstaat. Er hoeft geen toelichting gegeven te worden, maar het mag wel, mits je het kort houdt. 1. De key-eigenschap is een speciaal geval van een FD. 2. De foreign key-eigenschap is een speciaal geval van een FD. 3. In een ER-diagram moet je altijd foreign keys vermelden. 4. Twee goede ontwerpers zullen voor dezelfde casus altijd hetzelfde ER-diagram opleveren. 5. Als een schema in 3NF is, is dit schema ook in BCNF. 6. Als een schema in 4NF is, is dit schema ook in BCNF. 7. Niet voor elk relatieschema is een verliesvrije DP BCNF decompositie mogelijk. Bovendien is deze in het algemeen moeilijk te vinden. 8. Als de recoverymanager werkt volgens het UNDO-mechanisme, dan mag deze nooit database-data naar disk schrijven nadat commitment heeft plaatsgevonden. 9. Voor elke database-toepassing is concurrency control noodzakelijk. 10. Als data uit een database wordt geanonimiseerd voordat deze openbaar wordt gemaakt, dan is de privacy van de personen in de database gegarandeerd.
2
2
Functional dependencies
We hebben het volgende relatieschema met gegevens betreffende films. IMDB (filmid, genre, company, director, actorid, year, title, character) Voor elke film bestaat een unieke, identificerende code. Hetzelfde geldt voor acteurs. Een film kan mogelijk passen bij verschillende genres. Elke film wordt uitgebracht door een filmmaatschappij (company) en heeft een titel en een regisseur (director). Binnen een film speelt een acteur een karakter. Een karakter kan in meerdere films terugkomen. Denk aan Tarzan of Q en miss Moneypenny in James Bond-films. Geef van de volgende FD’s aan of deze wel of niet geldig zijn. Geef een korte toelichting. 1. f ilmid → genre 2. f ilmid → company 3. f ilmid → year 4. title → company 5. director → company 6. f ilmid, actorid → company 7. actorid → character 8. character → actorid 9. character, f ilmid → actorid 10. actorid, f ilmid → character
3
3
Normalisatie
Gegeven zijn R = (ABCDEG) en F = {A → BC, CD → E, AC → DE, E → D} (i) Bereken een minimal cover voor F . Licht de stappen die u maakt kort toe. (ii) Geef een verliesvrije, 3NF, DP decompositie van R met behulp van het daartoe geschikte algoritme. (iii) Is het hierboven gevonden schema ook in BCNF? Licht toe.
4
Queries
Een bedrijf dat gegevens bijhoudt over 1-daagse wielrenklassiekers heeft een database met daarin een tabel waarin gegevens van renners worden bijgehouden, een tabel waarin gegevens van wedstrijden worden bijgehouden en een tabel waarin de deelname van renners aan wedstrijden wordt bijgehouden. Elke renner heeft een uniek rennernummer. Daarnaast wordt van elke renner de naam, het geslacht en het gewicht bijgehouden. Van elke wedstrijd wordt de naam, de datum en de lengte van het parcours bijgehouden. Eveneens heeft elke wedstrijd een uniek wedstrijdnummer. De registratie van de deelname van een renner aan een wedstrijd gaat vergezeld van de tijd waarin de renner de wedstrijd verreden heeft, de finish positie (1 voor de winnaar) en het aantal punten dat de renner in de wedstrijd behaald heeft. R ( rnr, naam, geslacht, gewicht ) WR ( wnr, rnr, tijd, positie, punten ) W ( wnr, naam, datum, lengte ) We hebben de volgende queries: Q1: Geef de namen van de vrouwelijke winnaars. Q2: Geef de namen van de renners die aan tenminste twee wedstrijden hebben deelgenomen. Q3: Geef de nummers en het aantal wedstrijden van de renners die aan tenminste twee wedstrijden hebben deelgenomen. Q4: Geef de nummers, namen en het aantal punten van de renners die tenminste 100 punten hebben gescoord. Hieronder volgen expressies in de RA of in SQL. Geef aan welke queries corresponderen met welke expressies. Effici¨entie is hier niet relevant. De relatie tussen queries en expressies is many-to-many en optioneel.
4
E1: W R2 := W R;
πnaam (R ./ W R ./ W R2)
E2: πnaam ((πwnr σpositie=1 (W R)) ./ σgeslacht=V R) E3: πnaam (σpositie=1,geslacht=V (W R ./ R) E4: SELECT R.naam FROM R WHERE geslacht = ’V’ AND rnr IN (SELECT WR.rnr FROM WR WHERE positie = 1) E5: SELECT R.naam FROM R WHERE geslacht = ’V’ AND EXISTS (SELECT WR.rnr FROM WR WHERE positie = 1) E6: SELECT R.naam FROM R, WR WHERE geslacht = ’V’ AND positie = 1 E7: SELECT R.naam FROM R, WR WR1, WR WR2 WHERE R.rnr = WR1.rnr AND R.rnr = WR2.rnr AND WR1.wnr <> WR2.wnr E8: SELECT R.rnr, R.naam, COUNT(WR.punten) FROM R, WR WHERE R.rnr = WR.rnr GROUP BY R.rnr, R.naam HAVING COUNT(WR.punten) >= 100 5
E9: SELECT R.rnr, R.naam, SUM(WR.punten) FROM R, WR WHERE R.rnr = WR.rnr GROUP BY R.rnr, R.naam HAVING SUM(WR.punten) >= 100 E10: SELECT R.naam, COUNT(*) FROM R, WR WHERE R.rnr = WR.rnr GROUP BY R.naam HAVING COUNT(*) >= 2 E11: SELECT R.naam, COUNT(WR.punten) FROM R, WR WHERE R.rnr = WR.rnr GROUP BY R.naam HAVING COUNT(WR.punten) >= 2
6
5
Recovery
We beschouwen nonquiescent recovery met UNDO logging. Hieronder vind je een log met before images. <START T1>
<START T2> <START T3> <START CKPT (T2, T3)> <START T4> <START T5> <END CKPT> Stel dat een crash optreedt direct na . (i) Welk gedeelte van de log file wordt gescand? (ii) Welke transacties worden undone? (iii) Welke transacties worden redone?
7
6
Concurrency
Hieronder zijn twee schedules gegeven. (i) Geef aan of deze schedules serializeerbaar zijn of niet. Zo ja, geef dan alle equivalente serie¨ele schedules. Zo nee, geef dan een cycle in de precedentiegraaf. (ii) Geef van beide schedules aan of deze door een 2PL-scheduler getolereerd zouden worden. Licht toe.
S1 T1
T2 w[x]
T3
S2
T4
T1
r[y]
T2 w[x]
T3
T4
w[y]
r[x]
r[x]
r[y] w[x] w[z]
r[y] w[z] w[z]
w[z]
Einde
8
