Kapitel 3 - Relationenalgebra und Normalisierung
- Wiederholung des Relationalen Modells.
- Relationenalgebra und Relationenkalkül.
- Was sind funktionale Abhängigkeiten?
- Welche Anomalien gibt es?
- Was heißt Dekomposition?
- Wozu dienen Normalformen und wie schauen die aus?
- Erweiterung der relationalen Algebra
Was ist das Entwurfsziel bei relationalen Datenbankschemata?
Eine Relationenschema soll einen Entity-Typ oder einen Beziehungstyp
beschreiben. Eine Relation sollte deshalb Informationen enthalten, die auch
wirklich zusammengehören. Dabei ist es nicht einfach beiden Ansprüchen der beiden
Kriterien zu genügen.
Ein Datenbankschema ist die Menge aller Relations-Schemata.
Was ist das relationale Datenmodell?
Daten werden als Relationen durch Tabellen (Entitätsmengen) dargestellt. Dabei
entspricht eine Zeile einer Entity und eine Spalte einem Attribut.
Ein Schlüssel einer Relation ist eine minimale Attributmenge die ein Tupel R D1 x
D2 x .... x Dn (D sind Domains bzw. Wertebereiche) eindeutig identifiziert. Ein
Relationsschema R(A1,....,An) spezifiziert eine Relation R mit den Attributen
A1,....,An. Dabei ist jedem Attribut Ai ist ein Wertebereich dom(Ai) zugeordnet.
Auf welche zwei Möglichkeiten kann man Abfragen an Relationen stellen?
Mit einer Relationenalgebra oder einem Relationenkalkül...
Was ist eine Relationenalgebra?
Die Relationenalgebra definiert Operationen auf Relationen, die neue
Relationen erzeugen.
Grundoperationen: Selektion (Auswahl bestimmter Tupel), Projektion (Auswahl
bestimmter Spalten), Vereinigung, Mengendifferenz, Kartesisches Produkt,
Umbenennung
Verbund, Durchschnitt und Division lassen sich aus den Grundoperationen
ableiten.
Beispiel: (ANGEST[ANGNR=ANGNR]ANG_PRO)[PNR=17][NAME]
Natural Join (nur gleiche Attributnamen) oder Teta Joins (mit Prädikat) werden auch
innere Joins genannt (inner join). Bei ihnen gehen diejenigen Tupel der
Argumentrelationen verloren, die keinen Join-Partner gefunden haben. Bei den
äußeren Join-Operatoren (outer joins) werden - je nach Typ des Joins - auch
partnerlose Tupel gerettet:
-
left outer join: Die Tupel der linken Argumentrelation bleiben
erhalten
-
right outer join: Die Tupel der rechten Argumentrelation
bleiben erhalten
-
full outer join: Die Tupel beider Argumentrelationen bleiben
erhalten
Was ist ein Relationenkalkül?
Durch ein Prädikat (eine Bedingung) wird die Menge der gewünschten Tupel
beschrieben mit Hilfe einer Formel der Pradikatenlogik 1. Stufe unter Verwendung
von Existenzquantoren, Allquantoren, And, Or und der Negation.
Beispiel:
{t|q}, dabei ist t eine Liste von Attributnamen
q: Prädikat
z.B. {STUDENT.WOHNORT|STUDENT.MATRIKEL=22762}
Worin unterscheiden sich Relationenalgebra und Relationenkalkül?
Die Relationenalgebra stellt konstruktive Regeln zur Erzeugung neuer
Relationen bereit, hier insbesondere die Grundoperationen (Vereinigung,
Differenz, kartesisches Produkt, Selektion, Projektion) und zusätzlich die
Operationen Join und Natural Join.
Der Relationenkalkül dagegen arbeitet mit deskriptiven Regeln. Mit
seiner Hilfe wird die Menge der bei einer Abfrage gewünschten Tupel beschrieben
indem eine Bedingung angegeben wird, die die Tupel erfüllen müssen.
Sind Abfrageergebnisse im Voraus beweisbar?
Die Relationenalgebra erlaubt eine sichere Bestimmung des Ergebnisses im
Voraus, da konstruktive Regeln verwendet werden.
Formulieren Sie eine Abfrage in Relationenalgebra und in Relationenkalkül!
Relationenalgebra: STUDENT[Name='Muller'][Matrikel]
Relationenkalkül: {STUDENT.Matrikel|STUDENT.Name='Muller'}
Wie werden Entitätstypen und Beziehungen in relationalen Datenbanken dargestellt?
Beide werden als Relationenschemata dargestellt.
Was ist das Ergebnis einer Selektion/Projektion auf einer Relation?
Wiederum ein Relation.
Was sind die drei wichtigsten Operationen der relationalen Algebra?
Was ist die Projektion?
Auswahl der Spalten einer Tabelle ohne dabei doppelte Zeilen zuzulassen.
Was ist Selektion?
Auswahl von Entitäten (Zeilen) aus einer Relation (Tabelle) unter einer
bestimmten Bedingung
Was ist der Natürliche Verbund?
Verbindet über die Vereinigung zweier oder mehrerer Attributmengen Relationen
zur einer neuen Relation.
Der unqualifizierte Join ist die teuerste Operation in der Relationenagebra,
denn er ergibt das kartesische Produkt zweier Mengen und bildet somit bei zwei
Tabellen der Mächtigkeiten n und m eine neue Relation der Mächtigkeit nm!
- ist kommutativ und assoziativ
- wenn die Attributmengen disjunkt sind wird ist die Operation ein kartesisches
Produkt
- Projektion und Verbund sind nicht invers zueinander, da bei Projektion
mehrfache Tupel herausfallen
Was sind funktionale Abhängigkeiten?
Man beachte den logischen Zusammenhang, welcher Attribute und ihre
Attributwerte untereinander haben. Zum Beispiel lässt sich durch einen
fortlaufenden CD-Index in einer CD-Datenbank eindeutig eine CD bestimmen, da die
dazugehörigen Attribute über diesen Schlüssel eindeutig definiert sind. Man sagt
nun auch, dass alle restlichen Attribute vom CD-Index voll funktional abhängig
sind. Also ist ein Primätschlüssel ein Beispiel für funktionale Abhängigkeit. Dabei
ist das Auffinden von funktionalen Abhängigkeiten nicht immer einfach. (sie
entstehen durch 1:n Kardinalitäten im ERD)
Voll funktional abhängig heißt, wenn B von keiner echten Teilmenge
von A abhängig ist. (Minimalitätsforderung)
Ein Attribut B ist von einem Attribut A funktional abhängig, wenn es zu jedem A
genau ein B gibt.
Wenn zwei Tupel einer Relation gleiche Werte für alle Attribute in A haben und auch
ihre B-Werte übereinstimmen, dann ist B von A funktional abhängig. Anders
formuliert, bestimmen die A-Werte eindeutig die B-Werte.
Für funktionale Abhängigkeiten gelten folgende Eigenschaften:
- Projektivität
- Distributivität
- Additivität
- Transitivität
- Pseudotransitivität
- Akkumulation
Erweiterung Kontextunabhängigkeit
funktionaler Abhängigkeiten heißt, das man eine gegebene Relation durch ergänzende
Attribute erweitern kann, ohne die funktionalen Abhängigkeiten zu zerstören.
Gibt es mehrere funktionale Abhängigkeiten können diese in mehrere Relationen
geteilt werden und durch einen verlustfreien Join auch wieder hergestellt werden.
Welche Arten von Anomalien gibt es?
Anomalien entstehen durch Auftreten bzw. Nichterkennen von funktionalen
Abhängigkeiten.
Was ist eine Einfüge-Anomalie?
Ein neues Tupel kann erst eingetragen werden, wenn alle X Informationen
vorliegen. Falls Nullwerte erlaubt sind, gibt es dann Probleme falls die fehlende
Info zum Schlüssel gehört.
Was ist eine Lösch-Anomalie?
Wird eine Information aus der Relation entfernt, so gehen mehr Informationen
verloren, als gewollt war. Tritt oft auf wenn in einer Relation mehr als eine
Entity vertreten ist!
Was ist eine Änderungs-Anomalie?
Falls eine Änderung der Daten vorgenommen werden muss, muss dies an mehreren
Stellen in der Relation geschehen, da sonst die Konsistenz bedroht ist.
Wozu dienen Normalformen?
Normalformen dienen der Vermeidung von Anomalien und zur Vermeidung von
Redundanz. Normalisierung heißt ein Aufteilen von Informationen in Relationen
entsprechend ihrer Semantik.
Beispiel:
LIEFER(Lieferant, Artikel,Adresse, Preis)
Einfüge-Anomalie:
Lieferant ohne Artikel (bisher keine Lieferung) kann nicht
berücksichtigt werden.
Lösch-Anomalie: Löschen eines Artikels führt möglicherweise auch zum Verlust
des Lieferanten.
Änderungsanomalie: Bei einer Preisänderung eines Artikels muß die ganze
Relation durchsucht werden
Wie sind die ersten vier Normalformen definiert und wie kann man sie erklären?
1.NF: Die Attributwerte sind unteilbar. (d.h. keine mengenwertigen
Attribute)
2.NF: Jedes Nichtschlüsselattribut A von R ist voll funktional abhängig von
jedem Schlüssel S von R (und nicht nur von Teilen des Schlüssels)
3.NF: Für alle implizierten Abhängigkeiten S A mit A S gilt: S enthält einen
Schlüssel oder A ist Schlüsselattribut(d.h. es gibt keine Abhängigkeiten zwischen
Nichtschlüsselattributen einer Relation)
BCNF (Boyce Codd Normalform): Für jede funktionale Abhängigkeit S A gilt: S
enthält einen Schlüssel für R. (d.h. es gibt keine Abhängigkeit zwischen
Nichtschlüsselattributen und Schlüsseln)
Was heißt Dekomposition?
Unter Dekomposition einer Relation in mehrere, einer Normalform genügenden
Relationen, versteht man eine Aufteilung der Ursprungsrelation, bei der keine
Information verloren geht.
Wir arbeitet das Dekompositionsprinzip?
Die Aufteilung geschieht durch geschickte Projektionen, die durch natürliche
Join-Operationen verlustfrei rückgängig zu machen sind.
Was bedeutet FD-treue Zerlegung?
Die Zerlegung eines Relationenschemas soll nicht mehr, aber auch nicht weniger
Integritätsbedingungen (hier funktionale Abhängigkeiten) enthalten als die
Ursprungsrelation.
Welche Normalformen gibt es?
Was definiert die erste Normalform?
Eine Relation ist in der Ersten Normalform, wenn jeder Attributwert
atomar ist, d.h. es gibt keine zusammengesetzten Attribute in Form
von Arrays, Sets oder Aufzählungstypen.
Was definiert die zweite Normalform
Eine Relation ist in der Zweiten Normalform, wenn sie in der Ersten Normalform
ist und jedes Nicht-Schlüsselattribut von jedem Schlüsselkandidaten
vollständig funktional abhängig ist.
Ein Attribut Y ist von einem Attribut X funktional abhängig, wenn es zu jedem X
genau ein Y gibt. Vollständig funktional abhängig bedeutet, daß das
Nicht-Schlüsselattribut nicht nur von einem Teil der Attribute eines
zusammengesetzten Schlüsselkandidaten funktional abhängig ist, sondern von allen
Teilen.
Datenfelder, die von einem Schlüsselkandidaten nicht vollständig funktional
abhängig sind, werden in weiteren T abellen untergebracht. Besteht der
Primärschlüssel nur aus einem einzigen, so ist eine Relation in Erster Normalform
automatisch in Zweiter Normalform.
- Es darf keine partiellen Abhängigkeiten zwischen Schlüsseln und Nicht-Schlüssel-Attributen geben
- Das heißt, es darf kein Nicht-schlüssel-Attribut von einem Schlüssel abhängen
- Dies wird aufgelöst, in dem die Abhängigkeit in eine extra Tabelle ausgelagert wird
Merktabelle: NF 2
Was definiert die dritte Normalform
Eine Relation ist in der Dritten Normalform, wenn Sie in der Zweiten
Normalform ist und jedes Nicht-Schlüssel-Attribut von keinem
Schlüsselkandidaten transitiv abhängig ist.
- Es darf keine transitiven Abhängigkeiten eines Nicht-Schlüssel-Attributes von einem Schlüssel geben
- Das heißt, es darf kein Nicht-schlüssel-Attribut von einem anderen Nicht-schlüssel-Attribut abhängen
- Das heißt Attribut B ist abhängig von Schlüssel und Attribut C ist abhängig von B
- Wird aufgelöst, in dem die beiden Spalten in eine extra Tabelle ausgelagert werden
- 3NF ist ein Spezialfall der Broyce-Codd-Normalform
Merktabelle: NF 3
Wie sieht die Boyce-Codd Normalform (BCNF) oder 3 1/2 NF aus?
Eine Relation ist in Boyce-Codd Normalform, wenn jeder Determinant ein
Schlüsselkandidat ist.
Ein Determinant ist eine Attributmenge, von der ein anderes
Attribut vollständig funktional abhängig ist. Die Boyce-Codd-Normalform ist eine
Weiterentwicklung der 3 NF. In der Dritten Normalform kann es vorkommen, daß ein
Teil eines (zusammengesetzten) Schlüsselkandidaten funktional abhängig ist von
einem Teil eines anderen Schlüsselkandidaten. Die Boyce-Codd-Normalform verhindert
dies.
Anders gesagt: In der BCNF wird jedes Attribut welches ein Schlüssel sein könnte,
zu einem Schlüssel gemacht.
- Es darf keine transitiven Abhängigkeiten eines Nicht-Schlüssel-Attributes oder eines Schlüssel-Attributesvon einem Schlüssel geben
- Das heißt, es darf kein Nicht-schlüssel-Attribut oder Schlüssel von anderen Attributen transitiv abhängen
- Das heißt Attribut B ist abhängig von Schlüssel und Attribut C ist abhängig von B
- Wird aufgelöst, in dem die abhängigen Spalten in eine extra Tabelle ausgelagert werden
- 3NF ist ein Spezialfall der Broyce-Codd-Normalform
Merktabelle: BCNF
Was definiert die vierte Normalform?
Eine Relation ist in Vierter Normalform, wenn sie in Boyce-Codd Normalform ist
und für jede mehrwertige Abhängigkeit einer Attributmenge Y von einer Attributmenge
X gilt:
- Die mehrwertige Abhängigkeit ist trivial ist oder
- X ist ein Schlüsselkandidat der Relation
Mehrwertige Abhängigkeit: (Multivalued Dependency, MVD)
Ein Schlüssel bestimmt nicht nur ein Attribut X sondern eine ganze Liste einer
Attributmenge X. Dann liegt eine mehrwertige Abhängigkeit vor. Die mehrwertige
Abhängigkeit ist trivial, wenn sich die Tabelle nicht weiter zerlegen läßt
- Mehrwertige Abhängigkeiten sind verboten
- Das heißt es darf keine Redundazen in funktional Abhängigen Attributen geben
- Beispiel ISBN (eindeutig) und Autor (uneindeutig, da mehrere Autoren)
- Wird aufgelöst, in dem die mehrwertigen Spalten in eine extra Tabelle ausgelagert werden
- 3NF ist ein Spezialfall der Broyce-Codd-Normalform
Merktabelle: NF 4
Was definiert die fünfte Normalform?
Eine Relation R ist in Fünfter Normalform (oder Project-Join-Normalform), wenn
sie in Vierter Normalform ist und für jede Join-Abhängigkeit (R1, R2, ..., Rn)
gilt:
- Die Join-Abhängigkeit ist trivial oder
- Jedes Ri aus (R1, R2, ..., Rn) ist Schlüsselkandidat der Relation
Join-Abhängigkeit(Join Dependency):
Eine Relation R genügt der Join-Abhängigkeit (R1, R2, ..., Rn) genau dann, wenn R
gleich dem Join von R1, R2, ..., Rn ist. Eine Join-Abhängigkeit ist trivial, wenn
ein Ri aus (R1, R2, ..., Rn) gleich R ist.
Was sollte wärend der Normalisierung immer getan werden?
Das normalisierte Schema mit dem ER-Diagramm auf Korrektheit überprüfen.
Was versteht man unter Erweiterung der relationalen Algebra?
Selektionskriterium: Im 1NF Modell beziehen sich
Selektionskriterien auf atomare Werte. Im 2NF-Modell beziehen diese sich nicht auf
einzelne atomare Werte sondern auf Mengen aus Werten des
Attribut-Wertebereichs. Daraus ergeben sich zusätzliche Operationen, wie gleich und
ungleich, and, or oder not...
Zusätzliche Operationen in der 2NF
Nest-Operation: Die Attributwerte eines Attributes einer Relation
werden zu einer Menge zusammengefaßt, falls die Werte aller restlichen Attribute
identisch sind.
Unnest-Operation: Ist die inverse Operation zu Nest.
Was ist eine "NF2-Relation"?
Bei dem NF2-Relationalen Datenmodell wird die erste Normalform aufgehoben.
Attribut-Wertebereiche dürfen Mengen sowie Mengen von Mengen sein. Die erste NF ist
ein Spezialfall mit atomaren Wertemengen.
Sind D1,D2,...,Dn atomare Wertebereiche (Domains) und ist eine Relation R eine
Teilmenge von C1 x C2 x ... Cm, also eine Teilmenge der kartesischen Produkte der
Wertebereiche, dann ist es gestattet, komplexe Wertebereiche als Potenzmenge der
atomaren Wertebereiche zu konstruieren. Es sind aber keine Wertebereiche
zugelassen, welche nur aus kartesischen Produkten bestehen!
|
|
Normalformen