Home

Impressum

kreissl.info[rmation science]

best practices

Relationenalgebra und Normalisierung

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!

Inhalt

Anfang

zurück

vor

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...