Kapitel 3 - Relationenalgebra und Normalisierung
|
Inhalt
|
- 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!
|
|
|
|
|
| Kapitel 1 | DBMS Konzept |
|
Eigenschaften, Bestandteile, Ebenen...
|
| Kapitel 2 | DB Entwurf |
|
Qualitätsmerkmale, funktionale Abhängigkeiten, ER...
|
| Kapitel 3 | Normalformen |
|
Übersicht Normalformen, Anomalien...
|
| Kapitel 4 | Relationalität |
|
Regeln und Vorgehensweisen...
|
| Kapitel 5 | Sprachen |
|
relationale Sprachen, SQL, Query...
|
| Kapitel 6 | Datenorganisation |
|
Tertiärspeicher, Adressierung, Indexe, ISAM...
|
| Kapitel 7 | Transaktionskonzept |
|
Datenintegrität, Serialisierbarkeit, ACID...
|
| Kapitel 8 | Concurrency Control |
|
Read-Write Modell, Schedules, Prinzip...
|
| Kapitel 9 | Scheduler & Recovery |
|
2-Phasen-Sperren,Deadlocks,Recovery...
|
|
|
|
|
|
|
|
|
Quellen:
|
Gottfried Vossen
Datenbankmanagementsysteme
|
Heuer und Saake
Konzepte und Sprachen
|
Prof. Benn
Skript und Vorlesung
|
Relationale Datenbanken
Andreas Kelz
|
Word Wide Web
Verschiedenste Seiten
|
|
|
|
|
|
|
Home 
Normalformen