Blatt 10 - DBS (2024-25)

Aufgabe 10-1 Synthesealgorithmus

Aufgabenstellung

Gegeben sei das folgende Relationsschema:

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 man damit alle Attribute erreichen kann. ChefPersNr und PersNr sind nicht eindeutig

b) Überführen Sie das Relationsschema 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

Schritt-für-Schritt Anwendung

1. Linksreduktion

Ziel: Reduzierung der linken Seiten der funktionalen Abhängigkeiten auf minimale Attribute.

Gegebene funktionale Abhängigkeiten:

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

Analyse:

• Alle linken Seiten bestehen bereits aus einzelnen Attributen.

Ergebnis:

Keine Änderungen erforderlich.

2. Rechtsreduktion

Ziel: Reduzierung der rechten Seiten der funktionalen Abhängigkeiten auf minimale Attribute.

Funktionale Abhängigkeiten nach Linksreduktion:

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

Reduzierung:

• ChefPersNr → ChefName
  • Keine Änderungen nötig.
• PersNr → Name, Fachgebiet, ChefPersNr, ChefName
  • Reduziert zu: PersNr → Name, Fachgebiet, ChefPersNr
  • Begründung: ChefName wird bereits durch ChefPersNr bestimmt (ChefPersNr → ChefName).
• MatrNr → PersNr, Name, Fachgebiet, ChefPersNr, ChefName, StudName, Semester, StudWohnOrt
  • Reduziert zu: MatrNr → PersNr, StudName, Semester, StudWohnOrt
  • Begründung: Name, Fachgebiet, ChefPersNr, ChefName werden durch PersNr und ChefPersNr bereits bestimmt.

Ergebnis nach Rechtsreduktion:

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

3. Entfernung von rechtsleeren Abhängigkeiten

Ziel: Entfernen von Abhängigkeiten, bei denen die rechte Seite leer ist.

Analyse:

Keine der funktionalen Abhängigkeiten hat eine leere rechte Seite.

Ergebnis:

Keine Änderungen erforderlich.

4. Zusammenfassen von Abhängigkeiten mit gleicher linker Seite

Ziel: Kombinieren von funktionalen Abhängigkeiten, die dieselbe linke Seite haben.

Analyse:

Keine zwei Abhängigkeiten teilen dieselbe linke Seite.

Ergebnis:

Keine Änderungen erforderlich.

5. Erzeugung neuer Relationen

Basierend auf den reduzierten funktionalen Abhängigkeiten werden neue Relationen erstellt:

1. Chef

   • Attribute: ChefPersNr, ChefName
   • Funktionale Abhängigkeit: ChefPersNr → ChefName
   • Primärschlüssel: $\underline{\text{ChefPersNr}}$

2. Assistent

   • Attribute: PersNr, Name, Fachgebiet, ChefPersNr
   • Funktionale Abhängigkeit: PersNr → Name, Fachgebiet, ChefPersNr
   • Primärschlüssel: $\underline{\text{PersNr}}$
   • Fremdschlüssel: ChefPersNr verweist auf Chef

3. Student

   • Attribute: MatrNr, PersNr, StudName, Semester, StudWohnOrt
   • Funktionale Abhängigkeit: MatrNr → PersNr, StudName, Semester, StudWohnOrt
   • Primärschlüssel: $\underline{\text{MatrNr}}$
   • Fremdschlüssel: PersNr verweist auf Assistent

6. Rekonstruktion eines Schlüsselkandidaten

Ziel: Sicherstellen, dass der Schlüsselkandidat der ursprünglichen Relation im neuen Schema erhalten bleibt.

Schlüsselkandidat der ursprünglichen Relation: MatrNr

Rekonstruktion:

Die Relation Student enthält MatrNr als Primärschlüssel, der alle erforderlichen Attribute bestimmt. Somit ist der Schlüsselkandidat im neuen Schema erhalten.

7. Elimination überflüssiger Relationen

Ziel: Entfernen von Relationen, die redundant sind.

Analyse:

Alle erstellten Relationen sind notwendig, um die funktionalen Abhängigkeiten und die Datenintegrität zu gewährleisten.

Ergebnis:

Keine Relationen werden eliminiert.

---

Finales Relationsschema in der 3. Normalform

Nach Anwendung des Synthesealgorithmus ergibt sich das folgende Relationsschema in der 3. Normalform:

1. Chef

   • Attribute: $\underline{\text{ChefPersNr}},\text{ChefName}$
   • Primärschlüssel: $\underline{\text{ChefPersNr}}$

2. Assistent

   • Attribute: $\underline{\text{PersNr}},\text{Name},\text{Fachgebiet},\text{ChefPersNr}$
   • Primärschlüssel: $\underline{\text{PersNr}}$
   • Fremdschlüssel: ChefPersNr verweist auf Chef

3. Student

   • Attribute: $\underline{\text{MatrNr}},\text{PersNr},\text{StudName},\text{Semester},\text{StudWohnOrt}$
   • Primärschlüssel: $\underline{\text{MatrNr}}$
   • Fremdschlüssel: PersNr verweist auf Assistent

Vorteile dieser Struktur

• Redundanzfreiheit:
  • Jede Information wird nur einmal gespeichert, was Speicherplatz spart und die Datenkonsistenz erhöht.
• Vermeidung von Anomalien:
  • Einfügeanomalie: Neue Daten können eingefügt werden, ohne dass unnötige oder unvollständige Daten entstehen.
  • Änderungsanomalie: Änderungen an Daten müssen nur an einer Stelle vorgenommen werden.
  • Löschanomalie: Das Löschen von Daten führt nicht zum Verlust anderer, unabhängiger Daten.
• Klarheit und Struktur:
  • Jede Relation hat einen klar definierten Zweck und eine eindeutige Schlüsselstruktur, was die Wartung und das Verständnis der Datenbank erleichtert.

---

Aufgabe 10-2 B-Baum

a) Definieren Sie einen B-Baum mit dem Grad $k=2$. Erklären Sie, was dies in Bezug auf die minimale und maximale Anzahl von Schlüsseln in den Knoten und die Anzahl möglicher Kinder bedeutet.

Ein B-Baum mit dem Grad $k=2$ erfüllt die folgenden Eigenschaften:

• Minimale Anzahl von Schlüsseln pro Knoten: Jeder Knoten (außer der Wurzel) muss mindestens $k-1=1$ Schlüssel enthalten.
• Maximale Anzahl von Schlüsseln pro Knoten: Jeder Knoten kann höchstens $2k-1=3$ Schlüssel enthalten.
• Anzahl der Kinder: Ein Knoten mit $n$ Schlüsseln hat genau $n+1$ Kinder.
  • Minimale Anzahl von Kindern: Jeder Knoten (außer den Blättern) muss mindestens $k=2$ Kinder haben.
  • Maximale Anzahl von Kindern: Jeder Knoten kann höchstens $2k=4$ Kinder haben.

Diese Definition stellt sicher, dass der Baum stets balanciert bleibt und Operationen wie Einfügen und Löschen effizient durchgeführt werden können.

b) Fügen Sie in einen anfangs leeren B-Baum mit dem Grad $k=2$ der Reihe nach die folgenden Schlüssel ein:

15, 8, 2, 9, 17, 5, 11, 19, 20, 3

• Zeigen Sie nach jedem Einfügevorgang den B-Baum (Diagramm oder Textstruktur) und erläutern Sie eventuelle Knoten-Splits.

1. Einfügen von 15

[15]

• Der Baum ist leer. 15 wird als Wurzel eingefügt.

2. Einfügen von 8

[8, 15]

• 8 wird vor 15 eingefügt. Keine Notwendigkeit zum Split.

3. Einfügen von 2

[2, 8, 15]

• 2 wird vor 8 eingefügt. Knoten erreicht maximale Kapazität (3 Schlüssel).

4. Einfügen von 9

• Der Knoten [2, 8, 15] ist voll. Einfügen von 9 führt zu einem Split.

Split-Vorgang:

• Mittlerer Schlüssel 8 wird zur neuen Wurzel.
• Links: [2]
• Rechts: [9, 15]

    [8]
   /   \
[2]   [9, 15]

5. Einfügen von 17

    [8]
   /   \
[2]   [9, 15, 17]

• 17 wird in den rechten Knoten eingefügt. Knoten [9, 15, 17] ist nun voll.

6. Einfügen von 5

    [8]
   /   \
[2, 5] [9, 15, 17]

• 5 wird in den linken Knoten eingefügt. Kein Split notwendig.

7. Einfügen von 11

• Der rechte Knoten [9, 15, 17] ist voll. Einfügen von 11 führt zu einem Split.

Split-Vorgang:

• Mittlerer Schlüssel 15 wird nach oben verschoben.
• Links: [9, 11]
• Rechts: [17]

      [8, 15]
     /    |    \
[2,5] [9,11] [17]

8. Einfügen von 19

      [8, 15]
     /    |    \
[2,5] [9,11] [17,19]

• 19 wird in den rechten Knoten eingefügt. Kein Split notwendig.

9. Einfügen von 20

    [8, 15]
   /   |   \
[2,5] [9,11] [17,19,20] → Split (Schlüssel 19 wird zur Wurzel)

• 20 wird in den rechten Knoten eingefügt. Knoten [17,19,20] ist nun voll.

        [15]
       /    \
    [8]     [19]
   /   \    /   \
[2,5][9,11][17][20]

10. Einfügen von 3

• Der linke Knoten [2,5] kann noch einen Schlüssel aufnehmen.

        [15]
       /    \
    [8]     [19]
   /   \    /   \
[2,3,5][9,11][17][20] → Split (Schlüssel 3 wird zum Elternknoten)

• 3 wird in den linken Knoten eingefügt. Knoten [2,3,5] ist nun voll.

          [15]
         /    \
      [3,8]    [19]
     /  |  \    /  \
   [2][5][9,11][17][20]

c) Löschen Sie aus dem resultierenden B-Baum nacheinander die Schlüssel 8, 17, 10. Zeigen Sie Schritt für Schritt, wie sich der Baum nach jedem Löschvorgang verändert.

Wir löschen die Schlüssel nacheinander und zeigen die Veränderungen des B-Baums nach jedem Löschvorgang.

Ausgangsbaum vor Löschungen

          [15]
         /    \
      [3,8]    [19]
     /  |  \    /  \
   [2][5][9,11][17][20]

1. Löschen von 8

• 8 ist ein Schlüssel in der inneren Knoten. Wir müssen einen Ersatz finden, entweder den Vorgänger oder Nachfolger.

Ersatz durch den Nachgänger 9:

• Ersetze 8 durch 9.

          [15]
         /    \
      [3,9]    [19]
     /  |  \    /  \
   [2][5][11][17][20]

2. Löschen von 17

• 17 ist ein Schlüssel in der rechten Blattknoten [17,19,20]. Entfernen von 17.

          [15]
         /    \
      [3,9]    [19,20]
     /  |  \
   [2][5][11]

• Der rechte Knoten hat nun [19,20], was mindestens die minimale Anzahl von Schlüsseln (1) erfüllt. Kein Umbalancieren nötig.

3. Löschen von 10

• Hinweis: 10 ist nicht im Baum vorhanden. Daher bleibt der Baum unverändert.

          [15]
         /    \
      [3,9]    [19,20]
     /  |  \
   [2][5][11]

• Keine Änderung, da 10 nicht existiert.

Zusammenfassung

Nach allen Einfügungen und Löschungen ist der finale B-Baum wie folgt strukturiert:

          [15]
         /    \
      [3,9]    [19,20]
     /  |  \
   [2][5][11]

Dieser Baum erfüllt weiterhin die Eigenschaften eines B-Baums mit Grad $k=2$.

---

×

MyUniNotes is a free, non-profit project to make education accessible for everyone. If it has helped you, consider giving back! Even a small donation makes a difference.

These are my personal notes. While I strive for accuracy, I’m still a student myself. Thanks for being part of this journey!