Aufgabe 11-1 Synthesealgorithmus

Aufgabenstellung

Gegeben sei das folgende Relationenschema: AssistentProfessorDiplomand (

PersNr, ← Personalnummer des Assistenten

Name, ← Name des Assistenten

Fachgebiet, ← Fachgebiet des Assistenten

ChefPersNr, ← Personalnummer des Professors

ChefName, ← Name des Professors

MatrNr, ← Matrikelnummer des Studenten

StudName, ← Name des Studenten

Semester, ← Fachsemester des Studenten

StudWohnOrt ← Wohnort des Studenten )

Die Relation AssistentProfessorDiplomand enthält die Daten von Studierenden, deren Diplomarbeit von einem Assistenten betreut wird, welcher wiederum bei einem bestimmten Professor angestellt ist.

Gegeben seien folgende funktionale Abhängigkeiten:

ChefPersNr → ChefName

PersNr → Name, Fachgebiet, ChefPersNr, ChefName

MatrNr → PersNr, Name, Fachgebiet, ChefPersNr, ChefName, StudName, Semester, StudWohnOrt

(a) Bestimmen Sie alle Schlüsselkandidaten.

MatrNr ist der einzige Schlüsselkandidat da durch diesen alle anderen Attribute abhängig sind
Weder ChefPersnr oder PersNr sind eindeutig

(b) Überführen Sie das Relationenschema mit Hilfe des Synthesealgorithmus in die 3. Normalform.

Erinnerung

Schritte des Synthesealgorithmus:

Linksreduktion

Rechtsreduktion

Entfernung von rechtsleeren Abhängigkeiten

Zusammenfassen von Abhängigkeiten mit gleicher linker Seite

Neues Relationsschema erzeugen

Rekonstruktion eines Schlüsselkandidaten:

Elimination überflüssiger Relationen

Linksreduktion

ChefPersNr → ChefName
PersNr → Name, Fachgebiet, ChefPersNr, ChefName
MatrNr → PersNr, Name, Fachgebiet, ChefPersNr, ChefName, StudName, Semester, StudWohnOrt

Es gibt hier nichts zu ändern, da links jeweils nur ein Attribute steht

Rechtsreduktion

ChefPersNr → ChefName
- bleibt unverändert
PersNr → Name, Fachgebiet, ChefPersNr, ChefName
- wird zu PersNr → Name, Fachgebiet, ChefPersNr
- weil Chefname kommt in ChefPersNr schon vor
MatrNr → PersNr, Name, Fachgebiet, ChefPersNr, ChefName, StudName, Semester, StudWohnOrt
- wird zu: MatrNr → PersNr,, StudName, Semester, StudWohnOrt
- alles Andere kommts schon in PersNr und ChefPersNr vor

Entfernung von rechtsleeren Abhängigkeiten

gibt keine überflüssige Abhängigkeit

Zusammenfassen von Abhängigkeiten mit gleicher linker Seite

keine gleiche linke Seite

Relationsschema erzeugen

R_{1} (\underline{C h e f P ers N r}, C h e f N am e)

R_{2} (\underline{P ers N r}, N am e, F a c h g e bi e t, C h e f P ers N r, C h e f N am e)

R_{3} (\underline{M a t r N r}, P ers N r, N am e, F a c h g e bi e t, C h e f P ers N r, C h e f N am e, St u d N am e, S e m es t er, St u d W o hn O r t)

Rekonstruktion eines Schlüsselkandidaten:

→ Diplomand enthält Schlüsselkandidaten (MatrNr)

Elimination überflüssiger Relationen

→ nichts zu tun

Aufgabe 11-2 Kombinatorik von Schedules

Aufgabenstellung

Gegeben sei eine Menge von n Transaktionen ${T_{1}, \dots, T_{n}}$ , wobei jede Transaktion $T_{i}$ aus vielen Einzeloperationen besteht: $T_{i} = ⟨ A_{i, 1}, A_{i, 2}, \dots, A_{i, in} ⟩$

Beispiel:

$T_{1} = ⟨ A_{1, 1}, A_{1, 2}, A_{1, 3}, A_{1, 4} ⟩$

$T_{2} = ⟨ A_{2, 1}, A_{2, 2}, A_{2, 3} ⟩$

$T_{3} = ⟨ A_{3, 1}, A_{3, 2}, A_{3, 3} ⟩$

Erläutern Sie für das Beispiel ${T_{1}, T_{2}, T_{3}}$ sowie für den allgemeinen Fall ${T_{1}, \dots, T_{n}}$ :

(a) Wieviele beliebige Schedules gibt es?

Aktionen dürfen innerhalb der Transaktion nicht vertauscht werden → sonst beliebig angeordnet

Im Beispiel:

Es gibt 10 Aktionen → 10 freie Plätze im Schedule
Erste Transaktion bekommt 4 beliebige Plätze
Zweite TA bekommt 3 beliebige aus den übrigen 10-4 = 6 Plätzen
Dritte TA bekommt den Rest

F \overset{u}{¨} r T_{1} g i lt : (4 10) = \frac{10 !}{( 10 - 4 )! \cdot 4 !} = 210

F \overset{u}{¨} r T_{2} g i lt : (3 6) = \frac{6 !}{( 6 - 3 )! \cdot 3 !} = 20

F \overset{u}{¨} r T_{3} g i lt : (3 3) = \frac{3 !}{( 3 - 3 )! \cdot 3 !} = 1

$⟹ I n s g es am t e A n z ah l S c h e d u l es : 210 \cdot 20 \cdot 1 = 4200$

Anzahl beliebiger Schedules im allgemeinen

(\frac{( i _{1} + i _{2} + \dots + i _{n} )!}{i _{1} ! \cdot i _{2} ! \cdot \dots \cdot i _{n} !})

(b) Wieviele serielle Schedules gibt es?

Anzahl der Permutationen der Transaktionen → Jede Transaktion kann an einer beliebigen stelle stehen

3! = 6

Anzahl serieller Schedules im allgemeinen

n!

(c) Wieviele serialisierbare Schedules gibt es?

Kann man im allgemeinen nicht genau bestimmen, da die Anzahl von den Abhängigkeiten bestimmt wird.
Liegt aber zwischen der Anzahl beliebiger Schedules und der Anzahl der seriellen Schedules $6 \leq Anz. serialisierbarer Schedules \leq 4200$

Anzahl serialisierbarer Schedules im allgemeinen

n! \leq Anz. serialisierbarer Schedules \leq (\frac{( i _{1} + i _{2} + \dots + i _{n} )!}{i _{1} ! \cdot i _{2} ! \cdot \dots \cdot i _{n} !})

Aufgabe 11-3 Serialisierbarkeit von Schedules (Serialisierungsgraph)

Aufgabenstellung

Geben Sie für die folgenden Beispiele jeweils den vollständigen Abhängigkeitsgraphen sowie ggf. einen äquivalenten seriellen Schedule an bzw. begründen Sie kurz, warum dieser nicht existiert.

a)

S_{1} = (w_{1} (x), w_{2} (y), w_{3} (x), r_{1} (x), r_{2} (z), w_{4} (y), r_{4} (z), w_{4} (x), r_{3} (y), r_{1} (z))

x w_{1} w_{3} r_{1} w_{4} y w_{2} w_{4} r_{3} z r_{2} r_{4} r_{1}

Abhängigkeiten

• Auf Object $x$ : $w w_{1, 3} x$ , $w w_{1, 4} x$ , $w r_{3, 1} x$ , $w w_{3, 4} x$ , $r w_{1, 4} x$ • Auf Object $y$ : $w w_{2, 4} y$ , $w r_{2, 3} y$ , $w r_{4, 3} (y)$ • Auf Object 𝑧: wird nur gelesen → keine Abhängigkeiten

b)

S 2 = (w_{1} (x), r_{4} (x), r_{1} (y), r_{1} (z), w_{1} (z), w_{3} (x), r_{4} (z), w_{3} (y), w_{2} (y), w_{2} (z))

x w_{1} r_{4} w_{3} y r_{1} w_{3} w_{2} z r_{1} w_{1} r_{4} w_{2}

Abhängigkeiten

Auf Object x: $w_{1, 4} (x)$ , $w w_{1, 3} (x)$ , $r w_{4, 3} (x)$
Auf Object y: $r w_{1, 3} (y)$ , $r w_{1, 2} (y)$ , $w w_{3, 2} (y)$
Auf Object z: $r w_{1, 2} (z)$ , $w_{1, 4} (z)$ , $w w_{1, 2} (z)$ , $r w_{4, 2} (z)$

Aufgabe 11-4 Anomalien

Aufgabenstellung

Welche Anomalien treten in den folgenden Schedules auf? Begründen Sie Ihre Antwort. Hier sind die gegebenen Schedules entsprechend dem gegebenen Vorlagenformat umgeschrieben:

(a)

S_{1} = (r_{1} (x), r_{2} (y), w_{2} (x), r_{1} (z), r_{1} (x), w_{2} (y), w_{1} (z))

x r_{1} w_{2} r_{1} y r_{2} w_{2} z r_{1} w_{1}

→ Non-Repeatable Read

In diesem Fall ist das nur für $x$ der Fall
Muster: $r_{1} (x), w_{2} (x), r_{1} (x)$
Verstoß gegen Isolation

(b)

S_{2} = (r_{2} (y), r_{1} (x), w_{2} (x), w_{2} (y), w_{1} (x))

x r_{1} w_{2} w_{1} y r_{2} w_{2} z

→ Lost Update bezüglich $x$

Muster: $r_{1} (x), w_{2} (x), w_{1} (x)$

(c)

S_{3} = (r_{1} (x), r_{2} (z), w_{1} (y), r_{2} (y), w_{1} (x), w_{2} (z), w_{1} (y))

x r_{1} w_{1} y w_{1} r_{2} w_{1} z r_{2} w_{2}

→ Dirty Read bezüglich $y$

Muster: $w_{1} (x), r_{2} (y), w_{1} (y)$

🎓 MyUniNotes

Explorer

DBS-Blatt 11

Aufgabe 11-1 Synthesealgorithmus

(a) Bestimmen Sie alle Schlüsselkandidaten.

(b) Überführen Sie das Relationenschema mit Hilfe des Synthesealgorithmus in die 3. Normalform.

Linksreduktion

Rechtsreduktion

Entfernung von rechtsleeren Abhängigkeiten

Zusammenfassen von Abhängigkeiten mit gleicher linker Seite

Relationsschema erzeugen

Rekonstruktion eines Schlüsselkandidaten:

Elimination überflüssiger Relationen

Aufgabe 11-2 Kombinatorik von Schedules

(a) Wieviele beliebige Schedules gibt es?

Anzahl beliebiger Schedules im allgemeinen

(b) Wieviele serielle Schedules gibt es?

Anzahl serieller Schedules im allgemeinen

(c) Wieviele serialisierbare Schedules gibt es?

Anzahl serialisierbarer Schedules im allgemeinen

Aufgabe 11-3 Serialisierbarkeit von Schedules (Serialisierungsgraph)

a)

Abhängigkeiten

b)

Abhängigkeiten

Aufgabe 11-4 Anomalien

(a)

(b)

(c)

Graph View

Table of Contents

Backlinks