Datenbanken:Prüfunglösung 2005.08.05 Lehner

Aufgabe 1

Variante 1:

// Anm. 1: hier kann irgendwas nich ganz hinhauen - gesucht waren bei der horizontalen/vertikalen Zerlegung zwei Relationen X,Y - mehr nicht.

// Anm. 2: Es sollte mit den Klassen X,Y gearbeitet werden, nicht mit den konkreten Objekten. Dann bleiben auch nur zwei Zeilen)

Tabelle: ...?

-Universalrelation:

Relation-O2(O2_ID, A1, A2, A3)

-horizontale Zerlegung:

O2(O2_ID, A1, A2)
O1(O1_ID, A1, A2, A3)
O3(O3_ID, A1, A2, A3)

-vertikale Zerlegung:

O2(O2_ID, A1, A2)
O1(O2_ID, A3, foreign key (O2_ID) is key of O2)
O3(O2_ID, A3, foreign key (O2_ID) is key of O2)

Variante 2:

- Universalrelation

X-Y (ObjectType, A1, A2, A3)

X-Y	Y	A11	A12	A13
	Y	A31	A32	A31
	X	A21	A22	null

- Vertikale Zerlegung:

 X (A1, A2)
 Y (A1, A2, A3)
 Fremschlüsselbeziehung: Y(A1)->X(A1), Y(A2)->X(A2)

- Horizontale Zerlegung:

 X(A1, A2)
 Y(A1, A2, A3)
 Fremdschlüsselbeziehung: keine

Aufgabe 3

a) Bitte mal einen Stammbaum malen ;)

b) ELTERN(eteil, kind) = $ ( (\rho_{eteil \leftarrow vater}(Vater) ) \cup (\rho_{eteil \leftarrow mutter}(Mutter) ) ) $

GESCHWISTER(kind1, kind2) = $ \pi_{kind1,kind2} ( (\rho_{kind1 \leftarrow kind}(\rho_{E1} (Eltern) ) ) \bowtie_{(E1.Eteil=E2.Eteil) \wedge (E1.kind1<>E2.kind2)} (\rho_{kind2 \leftarrow kind}(\rho_{E2} (Eltern) ) ) ) $

TANTE(kind, tante) = $ \rho_{Tante \leftarrow Kind2}( ( \pi_{Kind,Kind2} ( \sigma_{Geschlecht='w'} ( ( (Eltern) \bowtie_{Eltern.Eteil=Geschwister.kind1} (Geschwister) ) \bowtie_{kind2=name} (Geschlecht) ) ) ) ) $

c) ELTERN:

 SELECT mutter AS eteil, kind FROM MUTTER
 UNION
 SELECT vater AS eteil, kind FROM VATER

GESCHWISTER:

 SELECT DISTINCT tab1.kind AS kind1, tab2.kind AS kind2
 FROM ELTERN AS tab1, ELTERN AS tab2
 WHERE tab1.kind<>tab2.kind And tab1.eteil=tab2.eteil;

TANTE:

 SELECT kind, kind2 AS tante
 FROM ELTERN, GESCHWISTER, GESCHLECHT
 WHERE ELTERN.eteil=GESCHWISTER.kind1 AND GESCHWISTER.kind2=GESCHLECHT.name AND GESCHLECHT.geschlecht="w";

d)

GESCHWISTER	kind1	kind2
	tina	bergit
	bergit	tina

TANTE	kind	tante
	claudia	bergit
	caterina	tina

Aufgabe 4

a) Die Abhängigkeiten lassen sich finden, in dem man jedes Attribut {A..G} mit jedem anderen Attribut vergleicht und prüft, ob die Werte des einen Attributs eindeutig auf einen Wert aus dem anderen Attribut abgebildet werden. Nehmen wir A: Die Werte aus A werden eindeutig auf alle Werte aus B abgebildet (1 auf 0, 2 auf 0, 3 auf 0, 4 auf 2). Daraus folgt A->B. Dies gilt auch für alle anderen Attribute {C..G} - also A->BCDEFG. Diese Verfahren muss nun auf alle Attribute angewendet werden. Damit ergibeben sich folgende Abhängigkeiten: {A->BCDEFG, B->DG, D->BG, E->BDFG, F->BDEG, G->BD}

b) Abhängigkeiten, die von mehreren Attributen abhängen, lassen sich nicht aus dem Schema ableiten. So bspw. ABC->D oder auch EF->C.

c) Relationenschemata der 2NF:

(A, B, C)

(B, D, G)

(A, E, F)

Relationenschemata der 3NF:

(A, B, C)

(B, D, G)

(A, E)

(E, F)

d)

E	F
3	8
4	3
5	5

Aufgabe 5

Hüllen:

H(F,A) = {A,B,C,D,E,F}
H(F,B) = {A,B,C,D,E,F}
H(F,C) = {C}
H(F,D) = {A,B,C,D,E,F}
H(F,E) = {E}
H(F,F) = {A,B,C,D,E,F}

A,B,D,F sind Schlüsselkandidaten

Links-und Rechtsreduktion halten die Hüllen der einzelnen Elemente A,B,C,D,E,F gleich.

a) CD->ABE

CD->A => D->A
CD->B => D->B
CD->E => D->E

=> D->ABE

b)

1. F->DE ergibt F->D
   
2. D->CF ergibt D->F => F->F => F->leer
   
3. D->ABE ergibt D->AB (da D->B => B->E)
   
4. B->DEF ergibt B->EF (da B->F => F->D)
   
5. A->CD bleibt

c) A->C,D ; B->E,F ; D->A,B ; F->D

Zur Probe Hüllenvergleich:

H(F,A) = {A,B,C,D,E,F}
H(F,B) = {A,B,C,D,E,F}
H(F,C) = {C}
H(F,D) = {A,B,C,D,E,F}
H(F,E) = {E}
H(F,F) = {A,B,C,D,E,F}

A,B,D,F sind Schlüsselkandidaten

Aufgabe 6

a) Da im Schedule weder BoT noch EoT auftauchen ist anzunehmen (zumindest lt. Dr. Keller), dass vor dem gegebenen Auszug BoT und irgendwann nach dem Auszug EoT aufgerufen wird, d.h. die drei Transaktionen bekommen von den Änderungen der jeweils anderen nichts mit. So kommt es zu folgenden Konflikten (op1<op2 soll heißen op1 wird vor op2 ausgeführt): w2(B)<r1(B), w1(A)<r2(A), w1(A)<w2(A), w2(A)<r3(A), w2(A)<w3(A), w2(C)<r3(C) [evtl. auch noch r2(B)<w1(B)]

b) Naja sollte eigentlich jeder hinbekommen, wenn die Konfliktfälle bereits gefunden waren. Auf jeden Fall taucht in Vorgriff auf c) ein Zyklus auf.

c) Enthält der Graph Zyklen (unabhängig von der von der Kante beschriebenen Ressource) ist ein Ablaufplan nicht serialisierbar. Somit ist der gegebene Schedule nicht serialisierbar.

Aufgabe 7

a) //vorlesung[uhrzeit="9.00"][2]/preceding-sibling::vorlesung

b) Alle Vorlesungen, die mindestens einen Seminarleiter haben (sprich Vorlesungen mit Übungen).

c)

 <vorlesungsverzeichnis>
 {
   for $vorlesung in fn:doc("vorlesungen.xml")//vorlesung
   return
     <vorlesung>
     { $vorlesung/titel }
     { for $sleiter in $vorlesung/seminarleiter
       return
         <seminarleiter>
           {$sleiter/vorname, $sleiter/nachname}
           { for $person in fn:doc("personal.xml")//person
             where ($sleiter/vorname = $person/vorname) and ($sleiter/nachname = $person/nachname)
             return $person/status
           } 
         </seminarleiter>
     }
   </vorlesung>
 }
 </vorlesungsverzeichnis>

Aufgabe 8

Endzustand:

                      [4|8|12| ]
                      | | |  |
              [1|2|3|4] | | [13|14|15|26]
                        | |
                        | [9|10|11|12]
                        |
                     [5|6|7|8]