Normalisierung: Aufgaben (Lösungen)

Normalisierung: Aufgaben (Lösungen)#

In diesem Tutorium behandeln wir das Thema Normalisierung.

Aufgabe 1: Hülle, Armstrong-Axiome, Schlüssel, Basis#

Es sind folgende funktionale Abhängigkeiten für die Relation R(A,B,C,D,E,F,G) gegeben.

  • A → B

  • B → D

  • {B, D} → C

  • F → E,F

  • {A, F} → G

  • G → A,B,C,D,E,F

Aufgabe 1.1: Hülle#

Geben Sie die Hülle {A}+ an.

Musterlösung

Musterlösung

Der Algorithmus ist auf Folie 16/17 der Vorlseung 4 zu finden.

  1. {A}+ = {A} + A → B

  2. {A}+ = {A,B} + B → D

  3. {A}+ = {A,B,D} + {B,D} → C

  4. {A}+ = {A,B,C,D}

  5. Es gibt keine funktinalen Abhängigkeiten, die auf der linken Seite Attribute der Menge {A}+ besitzen und Attribute funktional bestimmen, die noch nicht in der Menge {A}+ vorkommen. Somit ist {A}+ Final.

Aufgabe 1.2: Hülle#

Welche der folgenden funktionalen Abhängigkeiten können abgeleitet werden?

  • A → C

  • A → E

Musterlösung

Musterlösung

  • A → C, da C in der Hülle vorkommt.

  • A → E nicht, da E nicht in der Hülle vorkommt.

Aufgabe 1.3: Armstrong-Axiome#

Leite aus den gegebenen funktionalen Abhängigkeiten weitere funktionale Abhängigkeiten mit Hilfe der Armstrong-Axiome ab.

Musterlösung

Musterlösung

  • Aus B → D und {B, D} → C kann B → C abgeleitet werden und somit auch B → C, D (Transitivität).

  • Aus B → C, D und A → B kann A → C, D abgeleitet werden und somit auch A → B, C, D (Transitivität und Vereinigung).

  • Aus {A, F} → G und G → A, B, C, D, E, F kann {A, F} → A, B, C, D, E, F abgeleitet werden und somit auch {A, F} → A, B, C, D, E, F, G (Vereinigung).

  • (Es gibt noch viel mehr Kombinationen, aber das sind die wichtigsten für die nächste Aufgabe)

Aufgabe 1.4: Schlüssel#

  • Geben Sie 3 Superschlüssel für die Relation an.

  • Geben Sie alle Schlüsselkandidaten an. Welche Beziehung besteht zwischen den Schlüsselkandidaten und den Superschlüsseln?

  • Welcher der Schlüsselkandidaten eignet sich als Primärschlüssel?

Musterlösung

Musterlösung

  • Alle Attribut-Mengen, in denen G oder {A, F} vorkommen, sind Superschlüssel.

  • Nur die Attribut-Mengen {G} und {A, F} sind Schlüsselkandidaten, da sie die minimalen Superschlüssel sind.

  • Beide sind geeignet, jedoch kann G präferiert werden, da diese Menge nur aus einem Attribut besteht.

Aufgabe 1.5: Basis#

Geben Sie eine minimale Basis an.

Musterlösung

Musterlösung

Mögliche Lösung mittels Algorithmus:

  • Start mit allen gegebenen funktionalen Abhängigkeiten: {A → B; B → D; {B, D} → C; F → E, F; {A, F} → G; G → A, B, C, D, E, F}

  • alle trivialen funktionalen Abhängigkeiten löschen:

    • F → F wird eliminiert.

    • {A → B; B → D; {B, D} → C; F → E; {A, F} → G; G → A, B, C, D, E, F}

  • wiederholtes Vereinigungs-Axiom, Vereinfachung rechter/linke Seite anwenden

  • Vereinigungs-Axiom anwenden:

    • es ändert sich nichts, keine 2 gleiche linke Seiten.

    • Ergebnis: {A → B; B → D; {B, D} → C; F → E; {A, F} → G; G → A, B, C, D, E, F}

  • rechte Seite vereinfachen:

    • G → A, B, C, D, E, F ist die einzige funktionale Abhängigkeit, wo die rechte Seite vereinfacht werden kann.

    • G → A wird benötigt.

    • G → B wird nicht benötigt, da G → A und A → B zusammen G → B ergeben.

    • Analoge Anwendung für die restlichen funktionalen Abhängigkeiten G → …

    • Ergebnis nach Vereinfachung: {A → B; B → D; {B, D} → C; F → E; {A, F} → G; G → A, F}

  • linke Seite vereinfachen:

    • {B, D} → C hat 2 Attribute auf der linken Seite und es gilt B → D, somit kann {B, D} → C vereinfacht werden zu B → C.

    • {A, F} → G kann nicht vereinfacht werden, da weder A → F noch F → A gegeben ist noch abgeleitet werden kann

    • Ergebnis: {A → B; B → C, D; F → E; {A, F} → G; G → A, F }

  • Es kann nichts mehr vereinfacht und/oder vereinigt werden, somit haben wir eine minimale Basis:

    • {A → B ; B → C,D ; F → E ; G → A,F ; {A,F} → G }

Aufgabe 2: Funktionale Abhängigkeiten verletzen#

Gegeben sei das Relationenschema S(W, X, Y), wobei alle Attribute atomar und vom Typ CHAR sind.

Aufgabe 2.1#

Betrachten Sie folgende funktionale Abhängigkeiten: W → X und {X, Y} → W. Geben Sie eine möglichst kleine Instanz der Relation S an, die beide funktionale Abhängigkeiten gleichzeitig verletzt.

Musterlösung

Musterlösung 2.1

W

X

Y

a

x

y

a

y

z

b

x

y

Aufgabe 2.2#

Zeigen Sie mit einer möglichst kleinen Instanz der Relation S, dass die folgende Regel nicht gilt: wenn {W, X} → Y, dann W → Y oder X → Y.

Musterlösung

Musterlösung 2.2

W

X

Y

a

b

c

a

e

d

b

b

e

Aufgabe 3: Verlustfrei, Abhängigkeitstreu#

Gegeben sei die folgende Relation: Beamter (PersonalKennziffer, Tel-Nr., Name)

Dabei gelten die folgenden funktionalen Abhängigkeiten:

  • PersonalKennziffer → Tel-Nr.

  • PersonalKennziffer → Name

  • Tel-Nr. → Name

Die Relation soll nun normalisiert werden. Der Datenbank-Designer denkt dabei über verschiedene Alternativen der Zerlegung nach:

  • a) Erreichbar(PersonalKennziffer, Tel-Nr.) und Beamter(PersonalKennziffer, Name)

  • b) Erreichbar(PersonalKennziffer, Tel-Nr.) und Beamter(Tel-Nr., Name)

  • c) Erreichbar(PersonalKennziffer, Name) und Beamter(Tel-Nr., Name)

Begründen Sie, in welcher Normalform die Ausgangsrelation und die Relationen in a) bis c) jeweils stehen. Welche der gezeigten Zerlegungsalternativen würden Sie wählen und warum? Gehen Sie bei der Begründung insbesondere auf Eigenschaften der Zerlegung ein: Verlustfreiheit und Abhängigkeitserhaltung.

Musterlösung

Musterlösung 3. Verlustfrei, Abhängigkeitstreu

Name

NF

Begründung

Ausgangsrelation

2. NF

Dritte NF wird verletzt durch Tel-Nr. → Name

a)

BCNF

Verlustfrei, aber nicht abhängigkeitstreu, da Tel-Nr. → Name verloren geht.

b)

BCNF

Verlustfrei und Abhängigkeitstreu

c)

BCNF

Nicht verlustfrei, denn bei Join auf Name lassen sich Tupel generieren, die es vorher nicht gab. Auch nicht Abhängigkeitstreu, da es nicht mehr PersonalKennziffer → Tel-Nr. gibt.

Aufgabe 4: Normalisierung#

Gegeben sind die Relationen:

  • R1 (A, B, C, D, E)

  • R2 (A, C, F)

Und die funktionalen Abhängigkeiten:

  • A → B, E

  • A → D

  • F → A

  • {A, C} → F

  • {B, C} → E

  • C → A

Aufgabe 4.1#

Bestimmen Sie alle Schlüsselkandidaten.

Musterlösung

Musterlösung Aufgabe 4.1

  • Da C nie auf der rechten Seite einer funktionalen Abhängigkeit vorkommt, muss jeder Schlüssel C enthalten. Nach Bestimmung der Hülle von {C}+ = {CABDEF} und C minimal ist, ist C der einzige Schlüsselkandidat.

Aufgabe 4.2#

In welcher Normalform befinden sich die Relationen? Begründen Sie Ihre Antwort.

Musterlösung

Musterlösung Aufgabe 4.2

  • R1 und R2 befinden sich in der 1. Normalform, da alle Attribute atomar sind.

  • R1 und R2 befinden sich auch automatisch in 2. NF, da der Schlüsselkandidat nur aus einem Attribut besteht.

  • R1 und R2 befinden sich nicht in 3. NF. Transitive Abhängigkeit, da R1: C → A und A → BE. Transitive Abhängigkeit bei R2: C → F und F → A.

Aufgabe 4.3#

Überführen Sie die Relationen in die dritte Normalform und geben Sie die Schlüsselkandidaten an.

Musterlösung

Musterlösung Aufgabe 4.3

  • R1: Da eine transitive Abhängigkeit besteht, müssen die verletzenden funktionalen Abhängigkeiten A → D und A → B, E in eine eigene Relation R1a (A, B, E, D). Schlüsselkandidat dafür ist A.

  • R2: Da eine transitive Abhängigkeit besteht, muss die verletzende funktionale Abhängigkeit F → A in eine eigene Relation R2a (F, A). Schlüsselkandidat dafür ist F.

  • R1 (C, A)

  • R1a (A, B, D, E)

  • R2 (C, F)

  • R2a (F, A)

Aufgabe 4.4#

Sind die resultierenden Relationen in BCNF? Ist dies nicht der Fall, überführen Sie sie in BCNF.

Musterlösung

Musterlösung Aufgabe 4.4

Die BCNF ist nicht verletzt, da alle Relationen bereits nur aus zwei Attributen bestehen oder (im Falle von R1a) nur aus einer FD bestehen (A → B, D, E).

Aufgabe 5: Schlüssel und Normalformen#

Gegeben sei die Relation S(B, C, D, E) mit den atomaren Attributen B, C, D und E. Es gelten folgende und nur folgende funktionale Abhängigkeiten:

  • {B, C} → D

  • D → B

  • D → E

Überprüfen und begründen Sie die folgenden Aussagen:

  1. D ist der Primärschlüssel für diese Relation.

  2. {B, C} ist ein Schlüsselkandidat (für einen Primärschlüssel!).

  3. D ist ein Fremdschlüssel, weil er auf B verweist.

  4. S ist in der 1. NF (1. Normalform)

  5. Welche Abhängigkeiten müssten gelten (ein Beispiel!), wenn diese Relation nicht der 2. NF genügen soll.

  6. Die Relation S befindet sich in der 3. NF.

  7. S genügt der BCNF.

  8. Überführen Sie die Relation S in die BCNF.

Musterlösung

Musterlösung Aufgabe 5

  1. Nein, der Primärschlüssel ist {B, C}, da D nicht C bestimmt.

  2. Ja!

  3. Nein, es sind funktionale Abhängigkeiten angegeben.

  4. Ja, da alle Attribute atomar sind.

  5. z.B. {C, D} → E, damit eine partielle Abhängigkeit existiert.

  6. Nein. (Die Transitivität D → E ist verletzt)

  7. Nein. Da S sich sogar nicht in der 3. Normalform befindet, ist BCNF unmöglich.

  8. Zerlegung:

    • 1NF: S(B, C, D, E)

    • 2NF: S(B, C, D, E)

    • 3NF: S1(B, C, D) S3(D, E)

    • BCNF: S1(D, C), S2(D, B), S3(D, E)

Aufgabe 6: Anomalien#

Gegeben sei folgende Tabelle:

MatNo

Name

BirthDate

IName

IProfessor

IVehicle

IVSize

CName

CStreet

CZipCode

368251

Peter Smith

25.04.1993

Phys

Werner Heisenberg

Electron

2.8E-15

Berlin

Hertzallee

10623

105472

Margaret Hamilton

17.08.1936

Orbit

Walter Hohmann

Ariane VI

63

Houston

Avenue East

TX 77058

105472

Margaret Hamilton

17.08.1936

Phys

Werner Heisenberg

Electron

2.8E-15

Houston

Avenue East

TX 77058

105472

Margaret Hamilton

17.08.1936

ILR

Wernher von Braun

Ariane VI

63

Houston

Avenue East

TX 77058

65821

Hedy Lamarr

09.11.1914

HighFreq

Guglielmo Marconi

Electron

2.8E-15

New York

Avenue East

NY 10019

65821

Hedy Lamarr

09.11.1914

Math

Etienne Emmrich

Bezier-Curve

0

New York

Avenue East

NY 10019

254798

Markus Kavka

27.06.1967

ModLit

Günter Grass

tin drum

0,15

Munich

Gollierstraße

80807

168410

Gene Cernan

14.03.1934

Orbit

Walter Hohmann

Ariane VI

63

KSC

Titan Road

FL 32899

168410

Gene Cernan

14.03.1934

ILR

Wernher von Braun

Ariane VI

63

KSC

Titan Road

FL 32899

215439

Margaret Hamilton

25.04.1941

ModLit

Günter Grass

tin drum

0,15

Berlin

Berlin

28759

179547

Katherine Johnson

26.08.1918

Orbit

Walter Hohmann

Ariane VI

63

Houston

Titan Road

TX 77058

179547

Katherine Johnson

26.08.1918

Math

Etienne Emmrich

Bezier-Curve

0

Houston

Titan Road

TX 77058

179547

Katherine Johnson

26.08.1918

Phys

Werner Heisenberg

Electron

2.8E-15

Houston

Titan Road

TX 77058

345871

Linh

25.04.1993

DIMA

Volker Markl

bicycle

2

Berlin

Einsteinufer

10623

Zeige anhand verschiedener auch selbstgewählter Tupel, wie Einfüge-, Update- oder Löschanomalien auftreten können. Begründe deine Entscheidung!

Musterlösung

Musterlösung Aufgabe 6

Anomalien

MatNo

Name

BirthDate

IName

IProfessor

IVehicle

IVSize

CName

CStreet

CZipCode

U

368251

Peter Smith

25.04.1993

Phys

Werner Heisenberg

Electron

2.8E-15

Berlin

Hertzallee

10623

U

105472

Margaret Hamilton

17.08.1936

Orbit

Walter Hohmann

Ariane VI

63

Houston

Avenue East

TX 77058

U

105472

Margaret Hamilton

17.08.1936

Phys

Werner Heisenberg

Electron

2.8E-15

Houston

Avenue East

TX 77058

U

105472

Margaret Hamilton

17.08.1936

ILR

Wernher von Braun

Ariane VI

63

Houston

Avenue East

TX 77058

D

65821

Hedy Lamarr

09.11.1914

HighFreq

Guglielmo Marconi

Electron

2.8E-15

New York

Avenue East

NY 10019

U

65821

Hedy Lamarr

09.11.1914

Math

Etienne Emmrich

Bezier-Curve

0

New York

Avenue East

NY 10019

U

254798

Markus Kavka

27.06.1967

ModLit

Günter Grass

tin drum

0,15

Munich

Gollierstraße

80807

U

168410

Gene Cernan

14.03.1934

Orbit

Walter Hohmann

Ariane VI

63

KSC

Titan Road

FL 32899

U

168410

Gene Cernan

14.03.1934

ILR

Wernher von Braun

Ariane VI

63

KSC

Titan Road

FL 32899

U

215439

Margaret Hamilton

25.04.1941

ModLit

Günter Grass

tin drum

0,15

Berlin

Berlin

28759

U

179547

Katherine Johnson

26.08.1918

Orbit

Walter Hohmann

Ariane VI

63

Houston

Titan Road

TX 77058

U

179547

Katherine Johnson

26.08.1918

Math

Etienne Emmrich

Bezier-Curve

0

Houston

Titan Road

TX 77058

U

179547

Katherine Johnson

26.08.1918

Phys

Werner Heisenberg

Electron

2.8E-15

Houston

Titan Road

TX 77058

D

345871

Linh

25.04.1993

DIMA

Volker Markl

bicycle

2

Berlin

Einsteinufer

10623

  • UPDATE-Anomalien (U)

    • z.B. falls Werner Heisenberg sein Vehicle ändert, muss man dies an mehreren Stellen ändern.

  • DELETE-Anomalien (D)

    • beim Löschen gehen mehr Informationen verloren als gewünscht.

    • z.B. falls Volker Markl gelöscht werden würde, gingen auch die Informationen über Linh verloren.

  • INSERT-Anomalien (I):

    • neues Tupel erzeugt Ambivalenz z.B. Guglielmo Marconi hat nun plotzlich zwei verschiedene Autos: (65821, Hedy Lamarr, 09.11.1914, HighFreq, Guglielmo Marconi, LINT, 54, New York, Avenue East, NY 10019)

    • oder neues Tupel hat NULL-Werte z.B. könnte ein Vehicle ohne Person hinzugefügt werden: (NULL, NULL, NULL, NULL, NULL, EasyMile, 8, NULL, NULL, NULL)

Aufgabe 7: Normalisierung Lieferant (Zusatzaufgabe)#

Gegeben sei die folgende Ausgangsrelation:

Lieferant#

LieferantNr Ort Entf(km) Lieferung
BteilNr BteilBez Anzahl Bearbeiter
L1 London 600 T1 Schrauben 100 Meier
T2 Zangen 200 Müller
T3 Hammer 50 Oheim
L2 Paris 1000 T1 Schrauben 200 Meier
T4 Muttern 500 Schmidt
L3 London 600 T4 Muttern 1000 Busse
L4 Stockholm 600 T5 Muttern 800 Leicher

Die funktionalen Abhängigkeiten sind die Folgenden:

  • LieferantNr → Ort, Entf

  • BteilNr → BteilBez

  • LieferantNr, BteilNr → Anzahl, Bearbeiter

  • Bearbeiter → BteilNr

  • Ort → Entf

Aufgabe#

  • Normalisieren Sie die Relationen bis zur BCNF.

  • Protokollieren Sie dabei funktionalen Abhängigkeiten, die zu einer Zerlegung der Tabellen geführt haben.

Musterlösung

Musterlösung

1. Normalform

  • Lieferant(LNr, Ort, Entf)

  • Lieferung(LNr, BteilNr, BteilBez, Anzahl, Bearbeiter)

Normalisiert wurde anhand der funktionalen Abhängigkeit: LieferantNr → Ort, Entf

oder

  • Lieferung(LNr, BteilNr, Ort, Entf, BteilBez, Anzahl, Bearbeiter)

2. Normalform

  • Lieferant (LNr, Ort, Entf)

  • Lieferung (LNr, BteilNr, Anzahl, Bearbeiter)

  • Bauteil (BteilNr, BteilBez)

Normalisiert wurde anhand der funktionalen Abhängigkeit: BteilNr → BteilBez und falls nicht im ersten Schritt geschehen (LieferantNr → Ort, Entf)

3. Normalform

  • Lieferant (LNr, Ort)

  • Entfernung (Ort, Entf)

  • Lieferung (LNr, BteilNr, Anzahl, Bearbeiter)

  • Bauteil (BteilNr, BteilBez)

Normalisiert wurde anhand der funktionalen Abhängigkeit: Ort → Entf

BCNF

  • Lieferant (LNr, Ort)

  • Entfernung (Ort, Entf)

  • Bauteil (BteilNr, BteilBez)

  • Lieferung (LNr, Bearbeiter, Anzahl)

  • Bearbeitung (Bearbeiter, BteilNr)

Normalisiert wurde anhand der funktionalen Abhängigkeit: Bearbeiter → BteilNr

Contents