Klausur 12 Februar Winter 2009/2010, Fragen PDF

Preview

Summary

TU Informatik Lehrstuhl Datenbanksysteme Prof. Alfons Kemper, Ph. Klausur zur Vorlesung Grundlagen: Datenbanken WS 2009 2010 12. Februar 2010 Anrede: MatrNr: Nachname: Vorname: Studiengang: Hiermit ich, dass ich vor in Kenntnis gesetzt wurde, dass ich im Falle einer der auftretenden Erkrankung das A...

Description

TU München, Fakultät für Informatik Lehrstuhl III: Datenbanksysteme Prof. Alfons Kemper, Ph.D.

Klausur zur Vorlesung WS 2009 / 2010 12. Februar 2010

Anrede:

MatrNr:

Nachname: Vorname: Studiengang: Hiermit best¨atige ich, dass ich vor Pr¨ufungsbeginn dar¨uber in Kenntnis gesetzt wurde, dass ich im Falle einer pl¨otzlich w¨ahrend der Pr¨ufung auftretenden Erkrankung das Aufsichtspersonal umgehend informieren muss. Dies wird im Pr u¨ fungsprotokoll vermerkt. Danach muss unverz¨uglich ein R¨ucktritt von der Pr¨ufung beim zust¨andigen Pr¨ufungsausschuss beantragt werden. Ein vertrauens¨arztliches Attest – ausgestellt am Pr¨ufungstag – kann gegebenenfalls innerhalb der n¨achsten Tage nachgereicht werden. Wird die Pr u¨ fung hingegen in Kenntnis der gesundheitlichen Beeintr¨achtigung dennoch regul¨ar beendet, kann im Nachhinein kein Pr¨ufungsr¨ucktritt aufgrund von Krankheit beantragt werden.

Garching, den 12. Februar 2010 (Unterschrift)

Wichtige Hinweise zur Klausur: Bearbeitungszeit 90 Minuten Unterlagen • Verwenden Sie zur Bearbeitung der Aufgaben bitte nur die ausgeteilten Bl¨atter. • Beschriften Sie jedes Blatt mit Ihrem Namen und Ihrer Matrikelnummer! • Alle Bl¨atter (Angaben, bearbeitete Aufgaben, Bl¨atter mit Notizen) m¨ussen abgegeben werden. • Kontrollieren Sie die Vollst¨andigkeit Ihrer Unterlagen. Die Klausur umfasst – 10 Seiten bzw. 5 Bl¨atter (inklusive des Deckblatts) – 7 Aufgaben Sollten Sie feststellen, dass Ihre Unterlagen nicht vollst¨andig sind, weisen Sie bitte umgehend die Klausuraufsicht darauf hin! Klausurschein • Beschriften Sie den beiliegenden Briefumschlag mit Ihrer Adresse, damit Ihnen das Klausurergebnis per Post zugestellt werden kann. • Die Klausurergebnisse werden auch u¨ ber das TUMonline-Portal bekannt gegeben. ¨ • Der Termin zur Einsichtnahme wird Ende Februar im Internet auf denUbungsseiten bekannt gegeben. Aufgaben • Verwenden Sie bitte keine Bleistifte oder rote oder gr¨une Stifte. • Einige Aufgaben sind so formuliert, dass Sie die vorgegebenen Antworten als richtig oder falsch bewerten m¨ussen. Bei Fragestellungen mit zwei Spalten (f¨ur richtig und falsch) ist je Zeile nur eine der beiden Optionen auszuw¨ahlen. Bei Fragestellungen mit nur einer richtig-Spalte sind alle korrekten Antworten auszuw¨ahlen. Falls die Aufgabenstellung es erfordert, sollten Sie Ihre Auswahl sehr kurz in dem markierten Textfeld begr¨unden. Korrekt angekreuzte Felder geben Punkte, falsch angekreuzte Felder fuhren ¨ zu Punktabzug. Leergelassene Felder a¨ ndern die Punktzahl nicht. Die Gesamtpunktzahl einer Aufgabe kann jedoch nicht unter 0 Punkte sinken. Kreuze m ussen ¨ eindeutig zuzuordnen sein, d.h. Kreuze die mehrere Spalten/Zeilen u¨ berdecken werden nicht gewertet!

Name:

MatrNr.:

Aufgabe 1

B 6 Punkte

Geben Sie an, welche der folgenden Aussagen richtig oder falsch sind: (Korrekt angekreuzte Felder geben Punkte, falsch angekreuzte Felder fuhren ¨ zu Punktabzug. Leergelassene Felder a¨ ndern die Punktzahl nicht. Die Gesamtpunktzahl einer Aufgabe kann jedoch nicht unter 0 Punkte sinken.) richtig falsch √

√

√

√

√

√

Aussage Mit Ausnahme der Wurzel hat jeder Nicht-Blattknoten eines B-Baums mit Grad k mindestens k und maximal 2k Kindknoten. Mit logischer Datenunabh¨angigkeit bezeichnet man die Abschirmung von ¨ Benutzern und Anwendungen von Anderungen an der physischen Speicherung der Datenbank. Seien R, S zwei Relationen. Es gilt: R R.A=S.A S = (R R.A=S.A π A (S)) R.A=S.A S Die Zerlegung eines Relationenschemas in Teilschemata mittels des Dekompositionsalgorithmus ist immer verlustlos und abh¨angigkeitserhaltend. Bei Verwendung von Tupelidentifikatoren (TIDs) wird bei jedem Transfer eines Tupels auf eine neue Seite des Hintergrundspeichers die Verweiskette um ein Glied l¨anger. Sei R eine Relation. Es gilt: |π ABC (R)| ≤ |R|

Korrektur: je 1 Punkt pro richtigem Kreuz, je 1 Punkt Abzug pro falschem Kreuz

3

Name:

MatrNr.:

B

Aufgabe 2

4+4+4+4=16 Punkte

Welche der folgenden Relationenschemata sind korrekte bzw. nicht korrekte Umsetzungen des ER-Modells? Bitte kennzeichnen Sie jeweils alle Kandidatenschlussel ¨ der Relationen (z.B. durch Unterstreichung) und geben Sie jeweils eine kurze Begr¨undung f¨ur Ihre Wahl an. (Korrekt angekreuzte Felder geben Punkte, falsch angekreuzte Felder fuhren ¨ zu Punktabzug. Leergelassene Felder a¨ ndern die Punktzahl nicht. Die Gesamtpunktzahl einer Aufgabe kann jedoch nicht unter 0 Punkte sinken.) Korrektur: je richtigem Kreuz 1 Punkt, je falschem Kreuz 1 Punkt Abzug, je falschem Schlu¨ ssel 1/2 Punkt Abzug, je richtiger Begr¨undung 2 Punkte, falls schwammig nur 1 Punkt (bei falscher Begr¨undung kein Abzug) ER-Modell:

A1

A2 A

B1 R1

1 korrekt

nicht korrekt

C1

B2 R2

B 1

C 1

N

Relationen

C2

Begr¨undung

A : {[A1 , A2 , B1 ]} B : {[B1 , B2 , A1 ]} C : {[C1 , C2]} R2 : {[B1 , C1 ]}

R1 k¨onnte inkonsistent bef¨ullt werden.

√

A : {[A1 , A2 ]} B : {[B1 , B2 ]} C : {[C1 , C2 ]} R1 : {[A1 , B1 ]} R2 : {[B1 , C1 ]}

R1 als eigene Relation z.B. sinnvoll wenn viele nullWerte zu erwarten sind.

√

A : {[A1 , A2 , B1 ]}

1:1- bzw. 1:N-Beziehung.

B : {[B1 , B2 , C1 ]} C : {[C1 , C2 ]} √

A : {[A1 , A2 ]} B : {[B1 , B2 , A1 ]} C : {[C1 , C2 , B1 ]} √

4

R2 falsch umgesetzt.

Name:

MatrNr.:

Aufgabe 3

B 5+6+4=15 Punkte

Gegeben sei das Relationenschema R = {A, B, C, D, E, F }. ¨ sei Fa = {ABDE → F, E → C, F → A}. Geben Sie al(a) Die kanonische Uberdeckung le Kandidatenschlussel ¨ der Relation R sowie die bei der Zerlegung in 3NF entstehenden Relationen an und unterstreichen Sie einen Schlu¨ ssel in jeder Relation. • Kandidatenschlu¨ ssel: ABDE, BDEF • Rb1 = {A,B,D,E,F} / {A,B,D,E,F}, Rb2 = {E,C} je richtigem Kandidatenschl¨ussel 1 Punkt, je richtiger Relation 1 Punkt, je richtigem Schlu¨ ssel 1/2 Punkt (b) Gegeben seien die funktionalen Abh¨angigkeiten Fb = {ABDE → F C, F → A, C → B}. Zerlegen Sie die Relation R in die BCNF und unterstreichen Sie die Schl¨ussel der Teilrelationen. • Aufspalten nach 1. FD nicht m¨oglich, da ABDE ein Superschlu¨ ssel ist. • Aufspalten nach 2. FD → {A, F}, {B, C, D, E, F} • Aufspalten nach 3. FD → {A, F}, {B, C}, {C, D, E, F} je richtiger Relation 1 Punkt, je richtigem Schl¨ussel 1 Punkt (c) Gegeben sei die Menge von FDs Fc = {AB → C, CDF → E, D → EF, ABC → E}. ¨ Bestimmen Sie die kanonische Uberdeckung! AB → CE, D → EF Korrektur: pro richtiger FD 2 Punkte

5

Name:

MatrNr.:

B

Aufgabe 4

4+4=8 Punkte

Gehen Sie vom Universit¨atsbeispiel mit der Auspr¨agung auf Seite 11 aus. Geben Sie Relationenalgebra-Ausdrucke ¨ an, die Folgendes ermitteln: (a) Welche Studenten h¨oren schon im Grundstudium (Semester < 5) eine Spezialvorlesung (SWS = 2)? Geben Sie die Namen dieser Studenten aus. Π Name (σs.Semester 12 (c) Wessen Vorname f¨angt mit T an? s.Name, s.MatrNr Studenten s _________________________________________

... where s.Name like ’T%’ (d) Wer h¨ort die Logik-Vorlesung? s.Name, s.MatrNr Studenten s, h¨oren h, Vorlesungen v _________________________________________

... where s.MatrNr = h.MatrNr and h.VorlNr = v.VorlNr and v.Titel = ’Logik’ (e) Wer h¨ort mehr Vorlesungen als Carnap? s.MatrNr, s.Name Studenten s, h¨oren h _________________________________________ s.MatrNr, s.Name (*) > (

(*) Studenten s2, h¨oren h2 ________________________ ________________________ )

... where s.MatrNr = h.MatrNr ... where s2.MatrNr = h2.MatrNr and s2.Name = ’Carnap’ 8

Name:

MatrNr.:

B

Aufgabe 7

9+4=13 Punkte

(a) Folgende Auspr¨agung eines B-Baums mit k = 2 sei gegeben:

2

3

5

8

11

7

20

22

25

30

42

46

15

33

49

35

50

38

55

41

(i) Fu¨ gen Sie die 23 an und geben Sie den Baum nach der Einf¨ugeoperation an.

2

3

5

8

11

7

20

30

22

23

25

42

46

15

33

49

35

50

38

55

41

L¨osung ist falsch aber korrekter B-Baum: 1 GP (ii) In den urspr¨unglichen Baum wird die 53 eingef¨ugt. Geben Sie die Auspr¨agung des B-Baums nach dieser Operation an. 30

2

3

5

7

20

42

50

22

25

46

49 53

8

11

15

33

35

38

55

41

L¨osung ist falsch aber korrekter B-Baum: 1 GP (b) Erg¨anzen Sie den folgenden B-Baum mit k = 2 nur um die erforderlichen Eintr¨age, um einen g¨ultigen B-Baum zu erhalten:

20

5

15

25

35

70

60

40

Wurzel: Zahl ∈ ]40, 60[ rechtester Knoten: Zahl > 70 ∧ 6= 75 9

65

75

Name:

MatrNr.:

B

je richtiger Zahl 2 Punkte (sollten noch mehr richtige Eintr¨age eingef¨ugt worden sein: ignorieren)

10

Beispielauspr¨agung

PersNr 2125 2126 2127 2133 2134 2136 2137

VorlNr 5001 5041 5043 5049 4052 5052 5216 5259 5022 4630

Professoren Name Rang Raum Sokrates C4 226 Russel C4 232 Kopernikus C3 310 Popper C3 52 Augustinus C3 309 Curie C4 36 Kant C4 7

MatrNr 24002 25403 26120 26830 27550 28106 29120 29555

Studenten Name Xenokrates Jonas Fichte Aristoxenos Schopenhauer Carnap Theophrastos Feuerbach

Vorlesungen Titel SWS gelesenVon Grundz¨uge 4 2137 Ethik 4 2125 Erkenntnistheorie 3 2126 M¨aeutik 2 2125 Logik 4 2125 Wissenschaftstheorie 3 2126 Bioethik 2 2126 Der Wiener Kreis 2 2133 Glaube und Wissen 2 2134 Die 3 Kritiken 4 2137

h¨oren MatrNr VorlNr 26120 5001 27550 5001 27550 4052 28106 5041 28106 5052 28106 5216 28106 5259 29120 5001 29120 5041 29120 5049 29555 5022 25403 5022 29555 5001

Semester 18 12 10 8 6 3 2 2

voraussetzen Vorg¨anger Nachfolger 5001 5041 5001 5043 5001 5049 5041 5216 5043 5052 5041 5052 5052 5259

PersNr 3002 3003 3004 3005 3006 3007

Assistenten Name Fachgebiet Platon Ideenlehre Aristoteles Syllogistik Wittgenstein Sprachtheorie Rhetikus Planetenbewegung Newton Keplersche Gesetze Spinoza Gott und Natur

MatrNr 28106 25403 27550

pr¨ufen VorlNr PersNr 5001 2126 5041 2125 4630 2137

Boss 2125 2125 2126 2127 2127 2134

Note 1 2 2

Abbildung 1: Beispielauspr¨agung f¨ur eine Universit¨ats-Datenbank

11...