Dit tentamen is in elektronische vorm beschikbaar gemaakt door de TB C van A–Eskwadraat. A–Eskwadraat kan niet aansprakelijk worden gesteld voor de gevolgen van eventuele fouten in dit tentamen.
Tentamen Databases 18 december 2002 09:00 - 12:00, Educatorium Gamma • Denk aan de vakevaluatie op http://www.cs.uu.nl/education/enquete. • 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. • Bij elke vraag wordt verwacht dat je laat zien hoe je aan het antwoord komt (tenzij anders wordt vermeld). • Je mag ten hoogste ´e´en A4 met aantekeningen raadplegen. • Gebruikte afko’s: 2PL = two-phase locking 3NF = derde normaalvorm BCNF = Boyce-Codd normaalvorm DP = dependency preserving ER = entity-relationship FD = functional dependency RA = relationele algebra SQL = SQL (Structured Query Language)
Puntentelling: 1: 16 2: 24 3: 24 4: 16 5: 20 1
1
Algemeen
Bij de onderstaande vragen zijn er 0 of meerdere antwoorden correct. Je dient alle correcte antwoorden aan te geven. Licht bij twijfel het antwoord toe. Vraag 1: Welke van de onderstaande uitspraken zijn waar? A: De BEFORE-image wordt gebruikt bij het terugdraaien van de effecten van een transactie. B: De AFTER-image wordt gebruikt bij het terugdraaien van de effecten van een transactie. C: De BEFORE-image wordt gebruikt bij het garanderen van de effecten van een committed transactie. D: De AFTER-image wordt gebruikt bij het garanderen van de effecten van een committed transactie.
Vraag 2: Welke van de onderstaande afleidingsregels voor FD’s zijn geldig? A: X → Y ⇒ XZ → Y B: XY → ZU ⇒ XY U → ZY C: XY → ZU ⇒ XU → ZY D: XY → Z ⇒ X → Z Vraag 3: Welke van de onderstaande uitspraken zijn waar? A: De waarde van een foreign key attribuut mag nooit NULL zijn. B: als we een candidate key met twee attributen hebben, is er gegarandeerd geen candidate key met ´e´en attribuut te vinden. C: De closure van de primary key van een relatieschema is altijd de gehele attribuutverzameling. Vraag 4: Welke van de onderstaande uitspraken zijn waar? A: Het BCNF algoritme geeft, gegeven een relatieschema en een verzameling FD’s, altijd dezelfde decompositie, ongeacht in welke volgorde de FD’s gebruikt worden. B: Het 3NF algoritme geeft, gegeven een relatieschema en een verzameling FD’s, altijd dezelfde decompositie, ongeacht in welke volgorde de FD’s gebruikt worden. C: Elk relatieschema in BCNF is automatisch ook in 3NF. D: Het is, gegeven een relatieschema en een verzameling FD’s, altijd mogelijk een DP BCNF decompositie te vinden. E: Het is, gegeven een relatieschema en een verzameling FD’s, altijd mogelijk een DP 3NF decompositie te vinden. 2
2
Queries
We hebben het volgende databaseschema ter ondersteuning van de redactie van een ’society magazine’. We houden gegevens bij van sterren en hun relaties. De tabel Ster bevat een unieke identifier, de naam en de ’stardom rating’, een getal tussen 0 en 100 dat aangeeft wat je (huidige) status is als ster. De tabel Aan bevat de actuele relaties tussen twee sterren en de ingangsdatum van de relatie. Deze tabel is symmetrisch in de eerste twee attributen: als < x, y, d >∈ Aan, dan ook < y, x, d >∈ Aan. De tabel Uit bevat de voormalige relaties tussen twee sterren. Deze relatie is ook symmetrisch in de eerste twee attributen. Ster ( sno, naam, rating ) Aan ( s1, s2, sinds ) Uit ( s1, s2, van, tot ) We hebben de volgende queries en expressies. Q1: Geef de sterren met een rating van tenminste 80 die momenteel een relatie hebben. Q2: Geef de sterren met een rating van tenminste 80 die momenteel geen relatie hebben. Q3: Geef de sterren die momenteel een relatie hebben en die ook al eerder een relatie hebben gehad (met wie dan ook). E1: πnaam (σrating≥80 (ST ER ./sno=s1 AAN)) E2: πnaam (σrating≥80 (ST ER ./sno=s2 AAN)) E3: πnaam (σrating≥80 (ST ER ./sno6=s1 AAN)) E4: πnaam ((ST ER ./sno=s1 AAN) ./sno=s1 (UIT )) E5: πnaam (ST ER ./sno=s1 (πs1 (AAN) ∪ πs1 (UIT ))) E6: SELECT naam FROM Ster WHERE rating >= 80 AND sno NOT IN (SELECT s2 FROM Aan) E7: SELECT naam FROM Ster, Aan WHERE rating >= 80 AND sno <> s1
3
E8: SELECT sno, naam FROM Ster WHERE rating >= 80 AND sno NOT IN (SELECT s1 FROM Aan GROUP BY s1 HAVING COUNT(*) = 0) Geef voor elk van de queries aan met welke expressies ze corresponderen. Let op: deze relatie is mogelijkerwijs many-to-many en optioneel.
3
Normaalvormen
(a) We hebben een relatieschema R(ABCDEF G) en een verzameling FD’s FR = {A → BC, C → DF, AD → F G, G → B, F → B}. Geef een verliesvrije DP 3NF decompositie van dit schema. Laat zien hoe je aan je antwoord komt. (b) We hebben een relatieschema S(ABCDE) en een verzameling FD’s FS = {A → BC, C → BDE}. Geef een verliesvrije BCNF-decompositie van S. Is deze decompositie dependency preserving? Licht je antwoord kort toe.
4
4
Functionele afhankelijkheden
Ten behoeve van de registratie van boeken in onze informatica-bibliotheek hebben we (onder andere) de volgende attributen: bknr, isbn, rubriek, volgnr, exnr, titel, auteur. Elk boek (exemplaar) heeft een uniek boeknummer (bknr) dat gebruikt wordt voor de registratie van uitleningen. Dit nummer is in een streepjescode aangebracht. Het begrip ISBN wordt bekend verondersteld. Elk boek wordt in een rubriek ondergebracht. Meerdere boeken binnen dezelfde rubriek worden met een volgnummer (volgnr) onderscheiden en meerdere exemplaren onder dit volgnummer met een exemplaarnummer (exnr). Voorbeeld: we hebben een rubriek G2.0 . Daarbinnen hebben we verschillende boeken: [G2.0 1], [G2.0 2] enzovoort. Het feit dat we twee exemplaren van [G2.0 69] wordt aangegeven met exemplaarnummers: [G2.0 69 (1)] en [G2.0 69 (2)]. Geef van de volgende FD’s aan of ze wel of niet geldig zijn. Licht bij twijfel het antwoord toe. 1. bknr → isbn 2. bknr → rubriek 3. bknr → volgnr 4. bknr → exnr 5. isbn → bknr 6. isbn → exnr 7. exnr → bknr 8. exnr → isbn 9. auteur, titel → bknr 10. bknr → auteur, titel 11. isbn → auteur, titel 12. volgnr, exnr → auteur, titel
5
5
Concurrency
(a) We hebben een database systeem ten behoeve van de administratie van een videotheek. Elke band of dvd heeft een uniek identificatienummer, dus exemplaren kunnnen onderscheiden worden. Een uitleen- of inneemactie correspondeert met een writeoperatie op de database. Een reserveringsactie correspondeert met een read-operatie (”is de band aanwezig?”), gevolgd door een write-operatie. De write-operatie - en dus de eigenlijke reservering - vindt uitsluitend plaats als de band niet uitgeleend is. We kunnen kiezen of we de reserveringsservice wel of niet leveren. In welke van de volgende gevallen is concurrency control een vereiste? Licht je antwoord kort toe. 1. E´en filiaal, ´e´en baliemedewerker, geen reserveringen. 2. E´en filiaal, meerdere baliemedewerkers, geen reserveringen. 3. Meerdere filialen, meerdere baliemedewerkers, geen reserveringen. 4. E´en filiaal, meerdere baliemedewerkers, wel reserveringen. 5. Meerdere filialen, meerdere baliemedewerkers, wel reserveringen. (b) We beschouwen de volgende twee schedules. Geef aan of deze schedules serializeerbaar zijn of niet. Licht je antwoord toe. Geef zo mogelijk de equivalente seri¨ele schedules.
T1
T2
S1 T3
T4 w(y)
T5
r(z)
T1
T2
S2 T3
T4 w(y)
r(z) r(y) w(z)
r(y) w(z) w(x)
w(x)
w(z)
w(x)
r(y) r(x)
T5
r(y) r(x)
6
