Hol' Dir diese Lernkarten, lerne & bestehe Prüfungen. Kostenlos! Auch auf iPhone/Android!

Bei der Informationsverarbeitung ohne DBMS treten Probleme auf:

• Redundanz und Inkonsistenz (Herr Herrlein wird Herr Fiebig). Grund: Information für verschiedene Gruppen interessant, daher mehrfach gespeichert -> Redundanz, bei Änderungen Inkonsistenz
• Beschränkte Zugriffsmöglichkeiten (alle Eigenschaften von Herrn Müller lesen müssen, nur um seine Telefonnummer zu sehen)
• Probleme beim Mehrbenutzerbetrieb (A überschreibt Änderungen von B)
• Verlust von Daten (Dateibackup reicht nicht)
• Integritätsverletzungen (Eigenschaften sicherstellen)
• Sicherheitsprobleme (Jeder darf jedes Gehalt sehen?)
• Hohe Entwicklungskosten für Anwendungsprogramme (für jede Anwendung das Rad neu erfinden)

Man unterscheidet drei Abstraktionsebenen im DBMS

• Auf der physischen Ebene wird beschrieben, wie diese Daten physisch gespeichert werden.
• Auf der logischen Ebene beschreiben wir in Schemata, welche Daten gespeichert werden.
• Sichten stellen Teilmengen der Daten zur Verfügung, die auf die Bedürfnisse unterschiedlicher Benutzergruppen zugeschnitten sind.

Es der Datenabstraktion folgt Datenunabhängigkeit: Veränderungen an der physischen Ebene ändern nichts an der logischen (physische DU). Die logische Datenunabhängigkeit kann zum Teil durch Sichten erreicht werden.

1. Anforderungsanalyse: Den Ausschnitt der Welt verstehen: Welche Informationen liegen vor, wie werden sie verarbeitet? -> Spezifikation
2. Konzeptueller Entwurf: ER-Schema aufstellen
3. Implementationsentwurf: Relationen herleiten:

• Für jede Entität eine Relation erstellen
• Für jede Beziehung eine Relation aus den Attributen der Beziehung und den Schlüsselattributen der zugeordneten Entitäten (Fremdschlüssel)
• Verfeinern: 1:1 Beziehungen mit gleichem Schlüssel zusammenfassen etc.
• Relationen normalisieren

4. Physischer Entwurf: Physische Ebene optimieren, Kenntnisse des OS und der Hardware nötig

Ein Entity Relationship-Schema wird am besten als Diagramm modelliert.
Entities sind wohlunterscheidbare physische oder gedankliche Konzepte der zu modellierenden Welt, grafisch als Rechtecke dargestellt mit Namen drin.
Relationships sind Beziehungen, die zu Beziehungstypen abstrahiert werden. Als Raute repräsentiert, die mit den beteiligten Entities über ungerichtete Kanten verbunden sind.
Beide können mit Attributen charakterisiert werden, welche in ovale Kreise geschrieben und dem Ziel zugeordnet werden.
Es gibt auch Rollen, Multiplizitäten (Konsistenzbedingungen!), Generalisierung und Aggregation. Ausserdem: Schwache Entities.

Generell können Relationen, die den gleichen Schlüssel beinhalten, manchmal zusammengefasst werden.
1:1 Relationen können problemlos zusammengefasst werden. Allerdings sollten dabei Null-Werte vermieden werden (Jeder Professor hat ein Dienstzimmer, aber nicht jeder Raum ist ein Dienstzimmer).
Wenn 1:N oder N:1-Relationen zusammengefasst werden, ist ein Faktum mehrfach in der Relation enthalten. Durch diese Redundanz entsteht die Update-Anomalie: Wenn ein Wert zu einem Schlüssel geändert wird, ist der Schlüssel kein Schlüssel mehr (Inkonsistenz!).

Szenario: Zwei Relationen A und B mit 1:N-Beziehung wurden zusammengefasst.

• Die Update-Anomalie: Was passiert, wenn ein Wert für ein Element aus A sich ändert? Alle Tupel, die diese Entität betreffen, müssen angepasst werden.
• Die Lösch-Anomalie: Wenn die letzte Information aus A zu einer Entität gelöscht wird, gehen auch die Informationen aus B verloren.
• Die Einfüge-Anomalie: Wenn ein Element aus A keine Korrespondenz in B hat, kann man sie nicht einfügen.

Mit der relationalen Algebra kann man Daten aus relationalen Modellen extrahieren, es ist also eine Abfragesprache.

Sie kennt u. a. die folgenden Operatoren:
(Selektion), (Projektion), (Kreuzprodukt), (Join), (Umbenennung), - (Mengendifferenz), (Division), (Vereinigung), (Mengenschnitt) und diverse Derivate des Join-Symbols für die Join-Arten.

Ein (natürlicher) Join ist ein Kreuzprodukt, bei dem nur die Tupel enthalten sind, deren Attribute in gleichbenannten Spalten identisch sind.

Die Structured Query Language (SQL) ist eine standardisierte Datendefinitions- (DDL), Datenmanipulations- (DML) und Abfragesprache (also mehr als nur eine Query Language, aber gut).
Von der ANSI standardisiert, etwa SQL99 oder SQL3. Es gibt objektrelationale Erweiterungen.

SQL-Anfragen können direkt in die relationale Algebra überführt werden.
Besonderheiten sind: Mengen (union, intersect, minus), Gruppierung samt Aggregationsfunktionen (avg, max, ...) mit having und geschachtelte Queries (Unteranfragen).

Es gibt korrelierte und unkorrelierte Anfragen. Bei korrelierten Anfragen greift die Unteranfrage auf Attribute der umschließenden Anfrage zu. Sie können manchmal zu einem Join entschachtelt werden
Unkorrelierte Anfragen haben den Vorteil, das sie nur einmal insgesamt ausgeführt werden müssen, statt einmal pro Tupel.

Sichten werden aus verschiedenen Gründen verwendet:

• Für den Datenschutz: Sicht erstellen, die nur die für die Benutzergruppe relevanten Attribute enthält
• Zur Vereinfachung von Anfragen: Oft verwendete, komplexe Anfragen als Sicht speichern. DRY-Prinzip (Don't repeat yourself)
• Zur Gewährleistung der Datenunabhängigkeit: Um Schema verändern zu können, etwa Spalten umzubennen, ohne die Applikationen zu verändern.

Den Relationalen Tupelkalkül:
Bsp:

Zugriffskontrolle dient sowohl der Privacy (User muss nicht mehr sehen als er auch verarbeiten muss) als auch der Security (User darf nicht schreibend auf Tupel zugreifen können, die er nicht verändern muss).

Erzielt durch Authentifizierung und Zugriffsrechte mit GRANT.

Das Ziel ist, "gute" relationale Schemata zu definieren und auch algorithmisch herzuleiten. Jede Relation soll genau einer Objektmenge entsprechen und frei von Redundanzen sein. Die drei Anomalien treten nicht auf.

Beispiel für schlechtes Relationenschema:

PersNr	Name	Raum	VorlNr	Titel
2125	Sokrates	226	5041	Ethik
2125	Sokrates	226	5049	Mäeutik
2132	Schlick	52	5259	Der Wiener Kreis

Update-Anomalie: Sokrates zieht um,.
Einfüge-Anomalie: Neuer Prof ohne Vorlesung.
Löschanomalie: Vorlesung von Schlick löschen.

Schema: (R ist geschwungen!)
Ausprägung:
Seien , dann ist
("Alpha bestimmt Beta") genau denn wenn mit
Notation: oder

Dazu dienen die Armstrong-Axiome:

• Reflexivität: Falls , dann gilt immer . Es gilt immer
• Verstärkung: Falls gilt, dann gilt auch .
• Transitivität: Falls und  gilt, dann gilt auch  .

Diese Axiome sind vollständig und korrekt. Weitere Axiome zur leichteren Herleitung:

• Vereinigungsregel: Wenn  und  gelten, gilt auch 
• Dekompositionsregel: Inverse der Vereinigungsregel
• Pseudotransitivitätsregel: Wenn  und  gelten, dann gilt auch  .

Dazu dienen Indexstrukturen. Statt eines Table Scans muss nur der kleinere Index durchsucht werden, und selbst im Worst Case nicht alle Seiten davon. Dafür müssen sie gewartet werden. Also schnelleres Lesen, langsameres Schreiben.

Bäume sind gut für Daten, bei denen unkompliziert eine Ordnung aufgestellt werden kann, vor allem numerische Werte. ISAM-Strukturen entsprechen flachen Präfix-Bäumen, intuitiv dem Daumenindex eines Lexikons. Hashing ist optimal für alle nicht-numerischen Objekte, wichtig ist, dass sich das Hash schnell berechnen lässt.

Normale Binärbäume lassen sich schlecht auf Seiten abbilden und sind deswegen ungeeignet. Besser sind da B-Bäume, deren Knotengrößen auf Seitengröße abgestimmt werden und auf eine Seite abgebildet werden. Jeder Eintrag im Knoten umfasst Schlüssel und Tupel.
Die Anzahl der Seitenzugriffe beim Zugriff entspricht der Höhe des Baums, durch die Balancierung ist jedes Blatt gleich weit weg von der Wurzel. Jeder Knoten hat zwischen und Einträge, nur die Wurzel hat Einträge. Auf Einträge folgen an Nicht-Blättern Kinder.
Beim Löschen oder Einfügen muss der Baum ggf. neu balanciert werden, damit diese Eigenschaften erfüllt werden.

Besser: B+-Bäume

Bei flachen Bäumen müssen weniger Seiten nachgeladen werden. Für flache Bäume ist der B+-Baum gut, denn er hat die Tupel nur in den Blättern und deswegen mehr Elemente im Knoten -> flachere Bäume. Ausserdem verweist jedes Blatt auf Vorgänger und Nachfolger für guten sequentiellen Zugriff (Scans, Ranges). Und Referenzschlüssel müssen nicht realen Schlüsseln entsprechen, so können die Blätter besser ausgelastet werden.

Ansonsten gleiche Eigenschaften wie B-Baum.

Noch besser: Präfix-B+-Bäume:
Diese sind gerade bei der Indizierung von Zeichenketten sehr nützlich, da nur ein Teil des Schlüssels als Referenzschlüssel verwendet wird und es so zu einer besseren Verzweigung führt (und Schlüssel noch kleiner).

Manchmal müssen mehrere Attribute in den Index aufgenommen werden, etwa in CAD, GIS, etc. Anfragen sind dann Punkt- oder Bereichsabfragen. Bei eindimensionalen Indizes muss eine aufwändige Schnittmengenbildung erfolgen.
Wertebereiche sind .

Mögliche Abfragen:

• Exact Match Query
• Partial Match Query, wo ein Teil der Dimensionen gegeben ist
• Range Query mit Suchintervall für alle Dimensionen
• Partial Range Query mit Suchintervall für manche Dimensionen

Eigenschaften: Atomare Gebiete (rechteckig), vollständig (alle Gebiete decken gesamten Datenraum ab), disjunkt
R-Baum: atomar, k-D-Baum: atomar, disjunkt, vollständig

Die Anfrage stellt zwar das "was" dar, aber nicht, "wie" es gesucht werden soll. Jetzt wird die SQL-Abfrage über einen algebraischen Ausdruck in Code überführt, wobei dieser i. Alg. nicht optimal ist, es soll nur der worst-case vermieden werden. Es können mehrere "wie" zu einem was gefunden werden.

Der Ablauf ist:

• Deklarative Anfrage -> Scanner, Parser, Sichtenauflösung -> Algebraischer Ausdruck ("kanonische Übersetzung")
• -> Anfrage-Optimierer (logische Optimierung) -> Auswertungs-Plan (QEP)
• -> Code-Erzeugung, Ausführung (physische Optimierung)

Es gibt folgende Äquivalenzerhaltende Transformationsregeln:
1. Aufbrechen von Konjunktionen im Selektionsprädikat:
2. ist kommutativ
3. -Kaskaden: Falls , dann gilt

4. Vertauschen von und
  Falls die Selektion sich nur auf die Attribute der Projektionsliste bezieht, können die beiden Operationen vertauscht werden:
5. und sind kommutativ:

....

Zur Anfrageoptimierung wird wie folgt vorgegangen:

• Konjunktive Selektionsprädikate werden in Kaskaden von -Operationen zerlegt.
• Selektionsoperationen werden soweit "nach unten" propagiert wie möglich.
• Bei   werden Blattknoten so vertauscht, dass derjenige, der das kleinste Zwischenergebnis liefert, zuerst ausgewertet wird.
• Eine -Operation gefolgt von einer -Operation wird wenn möglich in eine -Operation umgeformt.
• Projektionen werden so weit wie möglich nach unten propagiert.
• Operationen wenn möglich zusammenfassen (, etc.)

Für einen logischen Operator kann es mehrere mögliche physische Operatoren geben.
Durch Iteratoren können alle Datenquelle eine abstrakte Schnittstelle anbieten und können so beliebig miteinander kombiniert werden: open, next, close, size, cost. Iteratoren werden dann zu einem baumförmigen Auswertungsplan kombiniert. Das ganze geschieht Pull-basiert, also die Wurzel fordert Elemente an.

Im Idealfall kann Pipelining angewendet werden: Jede Quelle sendet das nächste Element, und diese können direkt verknüpft werden. Pipeline-Breaker sind Operationen wie Sort, unique, Mengendifferenz bei denen erst die gesamte Datenmenge vorliegen muss, damit der Iterator weiter arbeiten kann.

Es werden nun alle denkbaren Anfrageauswertungspläne (QEP) generiert und deren Kosten bewertet.

Verteilte Datenbanken dienen dem geographisch verteilten Zugriff auf Datenbanken (verteilte Datenbanken, Data Warehousing) oder der Integration verschiedener Datenbanken (Multi-DBMS mit Legacy DBs). Eine Client-Server-Architektur mit einem zentralen DBMS-Server ist nicht gemeint.

Die Daten werden fragmentiert und auf den verschiedenen Servern gespeichert. Dabei muss zwischen horizontaler (Tupelmenge aufteilen) und vertikaler (Attributmengen auf verschiedenen Systemen zusammenfassen, Primärschlüssel auf allen) Fragmentierung unterschieden werden.

Die Daten müssen rekonstruierbar, vollständig und disjunkt (ein Datum ist nicht mehreren Fragmenten zugeordnet, nicht für Primärschlüssel) sein.

Transaktionen werden mit der BOT-Operation gestartet, durch commit deren Änderungen in die Datenbasis übernommen und bei Abort die Datenbasis auf den Zustand vor BOT zurückgesetzt. Sowohl commit als auch abort führen zum Abschluss der Transaktion.

Zusätzlich können Anwendungen mit "define savepoint" einen solchen definieren, auf die die noch aktive Transaktion per "backup transaction" zurückgesetzt werden kann.

Transaktionen erfüllen die ACID-Eigenschaften.

1. Analyse:

• Temporäre Log-Datei wird analysiert
• Winner- und Loser-Mengen werden ermittelt

2. Redo-Phase:

• alle protokollierten Änderungen werden in der Reihenfolge der Ausführung in die Datenbasis eingebracht.

3. Undo-Phase:

• Die Änderungsoperationen der Loser-TAs werden in umgekehrter Reihenfolge rückgängig gemacht.

Auch das Recovery wird geloggt, damit auch Abstürze während des Recoveries die Idempotenz nicht stören. Dazu werden CLRs (Compensation Log Records) für jede Undo-Operation angelegt, die beim nächsten Redo ausgeführt, beim Undo übersprungen werden. Notation mit spitzen Klammern.

Es können folgende Fehler auftreten:

• Lost update: überschreibt Änderungen von .
• Dirty read: Lesen von temporären Werten, also vor commit.
• Phantomproblem: Dieselbe Operation führt zu zwei verschiedenen Ergebnissen.

Deswegen will man die serielle Ausführung von Operationen ("Isolation") vorgaukeln, ohne auf die Vorzüge der verzahnten Ausführung zu verzichten.

Dazu müssen durch Synchronisation die Historien mindestens serialisierbar gemacht werden.

Eine Historie ist eine zeitliche Anordnung der verzahnt ausgeführten Elementaroperationen von nebenläufig bearbeiteten Transaktion.

Eine Historie ist serialisierbar, wenn sie äquivalent zu einer seriellen Historie ist, aber parallel ausgeführt werden kann. Nur zwei Reads sind serialisierbar, alle anderen Konstellationen an Operationen sind Konfliktoperationen. Zwei Historien sind äquivalent, wenn sie die Konfliktoperationen der nicht abgebrochenen TAs in derselben Reihenfolge ausführen.

Historien haben einen Serialisierbarkeitsgraphen, bei dem Konfliktoperationen in unterschiedlichen TAs zu einer Kante von der TA führen, die die Operation zuerst ausgeführt hat, zur anderen TA. Ist dieser Graph azyklisch, ist die Historie serialisierbar.

Eine Historie heisst rücksetzbar, falls immer die schreibende TA vor der lesenden Transkation ihr commit durchführt, also . Anders ausgedrückt: Eine TA darf erst ihr commit durchführen, wenn alle TAs, von denen sie gelesen hat, beendet sind. Rücksetzbare TAs können zurückgesetzt werden, ohne dass bereits abgeschlossene TAs in Mitleidenschaft gezogen werden.

Historien ohne kaskadierendem Rücksetzen (ACA) zwingen bei ihrem Abbruch andere TAs, die von ihnen gelesen haben nie zum Abbruch, sind also eine Untermenge der rücksetzbaren Historien.

Strikte Historien überschreiben nie veränderte Daten einer noch laufenden Transaktion, sind also eine Untermenge der ACA-Historien.

Der DBMS-Scheduler reiht die Operationen so, dass sie mindestens serialisierbar sind, meistens auch ohne Kaskadieren zurücksetzbar (also ##ACA \cap \SR).
Dazu gibt es verschiedene Ansätze:

• sperrbasierte Synchronisation (häufig verwendet)
• Zeitstempel-basierte Synchronisation
• und statt den obigen pessimistischen Verfahren die optimistische Synchronisation (vor allem für vorwiegend lesende Zugriffe a la LDAP)

Es gibt zwei Sperrmodi, S (Shared) und X (eXclusive Lock), wobei ein X-Lock nur auf ein ungesperrtes Objekt gegeben werden kann, S-Lock aber auf ein bereits mit S-Lock versehenes Objekt. Kann eine Sperre nicht gegeben werden, muss die Transaktion auf die Freigabe warten (eigene Sperren müssen nicht erneut geholt werden).
Als Grundlage dient das Zwei-Phasen-Sperrprotokol (2PL). Zuerst kommt die Wachstumsphase, in der Sperren nur angefordert werden, und die Schrumpfphase, wo nur Sperren freigegeben werden. Am TA-Ende müssen alle Sperren freigegeben werden. 2PL erzwingt Serialisierbarkeit, aber Deadlocks sind möglich.

Als Erweiterung gibt es das strenge 2PL, bei dem alle Sperren bis TA-Ende gehalten werden (keine Schrumpfphase). Damit ist kaskadierendes Rücksetzen ausgeschlossen.

Bei Multi-Granularity Locking (MGL) gibt es nicht nur Sperren auf Satzebene, sondern auch auf Seiten, Segmente oder der Datenbasis.
Bei kleiner Sperrgranularität ist der Aufwand zur Verwaltung der Sperren sehr groß, bei großer Granularität wird zuviel unnötig gesperrt. Daher MGL.
Dabei werden neue Sperrmodi eingeführt (Intention Share=IS, Intention Exclusive=IX). Bevor S oder IS gewährt wird, muss man alle übergeordneten Hierarchieelemente mit IS oder IX gesperrt haben. Bevor X oder IX gewährt wird, muss man alle übergeordneten in IX haben. Freigabe bottom-up.

Selbst wenn beim Löschen und Einfügen automatisch X-Sperren vergeben werden ist das Phantomproblem nicht beseitigt. Deshalb muss der Zugriffsweg zusätzlich gesperrt werden, auf dem man zu dem Objekt gelangt ist.
Wenn also jemand mit Hilfe des Index liest, wird der gelesene Bereich im Index gesperrt. Will eine andere TA dort ein Tupel einfügen, muss sie warten.

Geht davon aus, dass Konflikte selten auftreten. TAs werden einfach ausgeführt und im Nachhinein geprüft, ob ein Konflikt aufgetreten ist.
1. Lesephase: Änderungsoperationen werden zunächst auf lokalen Kopien ausgeführt.
2. Validierungsphase: Prüft, ob TA zwischenzeitlich mit anderen TAs in Konflikt geraten ist. Jede TA kriegt in der Validierungsphase einen Zeitstempel. Alle älteren TAs müssen nun entweder abgeschlossen sein oder aber keine der von dieser TA gelesenen Elemente geschrieben haben, sonst ist diese TA in Konflikt. Immer nur eine TA in der Validierungsphase!
3. Schreibphase: Alle Änderungen werden in die Datenbasis eingebracht.

Es gibt verschiedene Strategien, die unterschiedliche Vorraussetzungen haben:

• Brute force: eine verschachtelte Schleife über alle Elemente
• Merge-Sort Join: Relationen werden parallel von oben nach unten abgearbeitet. An jeder Position ist bekannt, dass keine kleineren Tupel folgen. Dann identische Werte mergen. Beide Relationen müssen nach dem Join-Attribut sortiert sein.
Achtung: Sobald ein erster Join-Partner gefunden wird, muss dieser markiert werden. Existieren auf beiden Seiten gleichwertige Tupel, müssen diese auch mit diesem Tupel verknüpft werden.
• Hash Join: Join-Attribute mit Hash-Funktion auf dieselben Buckets abbilden, wo zu joinende Tupel liegen. Problem: Wenn die zu erstellende Hashtabelle nicht komplett in RAM passt, wird es langsam (eine Seite pro Zugriff laden). Daher werden beide Relation partitioniert, so dass nur kleine Partitionen miteinander verglichen werden müssen: Build- und Probe-Phase für jede Partition.

Gegeben sei eine Menge F von FDs.
Die Menge aller aus F logisch ableitbaren FDs wird als transitive Hülle F+ bezeichnet. Die Armstrong-Regeln bilden einen korrekten und vollständigen Ableitungskalkül für die FDs in F+.

Die kanonische Überdeckung ist intuitiv die kleinste noch äquivalente Menge von FDs. Diese wird durch vier Schritte aus einer Menge F von FDs der Form hergeleitet:

• Linksreduktion: Für alle überprüfen, ob überflüssig ist (mit Hilfe der AttrHülle). Wenn ja, dann aus nehmen.
• Rechtsreduktion: Für alle prüfen, ob überflüssig ist, ggf. aus nehmen.
• Alle leeren FDs der Form entfernen.
• Mit Hilfe der Vereinigungsregel alle , ... zusammenfassen

Es gibt zwei Korrektheitskriterien für die Zerlegung von Relationenschemata:

• Verlustlosigkeit: Die in der ursprünglichen Ausprägung enthaltenen Informationen müssen aus den neuen Ausprägungen rekonstruierbar sein. Gegenbeispiel: Biertrinker-Beispiel
• Abhängigkeitserhaltung: Die für geltenden funktionalen Abhängigkeiten müssen auf die neuen Schemata übertragbar sein. Also nicht FDs aufteilen.

Das Biertrinker-Beispiel hat ein , in dem steht, wer was wo trinkt. Wenn man nun zwei neue Relationen macht (wer trinkt wo, und wer trinkt was), lässt sich daraus nur eine viel größere Relation rekonstruieren (wer trinkt was in allen Orten), die nicht mit der ursprünglichen übereinstimmt, also nicht verlustlos.

Jede Normalform weist neben den Eigenschaften der "schwächeren" Normalformen eigene auf, sie schränkt die Menge der erlaubten Ausprägungen also ein.

• 1NF: Nur atomare Domänen, keine Relationen als Tupel etc
• 2NF: Intuitiv: In einer Relation dürfen nur Informationen über ein Konzept modelliert werden.
Eine Relation mit zugehörigen FDs F ist in zweiter Normalform, falls jedes Nichtschlüssel-Attribut voll funktional abhängig ist von jedem Kandidatenschlüssel der Relation. Eine Relation in 2NF ist frei von Anomalien.
• to be continued...

3NF: Intuitiv: Jeder Fakt darf nur einmal gespeichert werden.
Ein Relationenschema ist in dritter Normalform, wenn für jede für geltende FD mindestens eine dieser Bedingungen gilt:

• , d.h. die FD ist trivial
• Das Attribut ist in einem Kandidatenschlüssel von enthalten
• ist Superschlüssel von

Eine Relation lässt sich algorithmisch in Relationen in 3NF durch den Synthesealgorithmus zerlegen:

• Kanonische Überdeckung bestimmen
• Für jede FD ein neues Schema generieren und FDs zuordnen.
• Wenn keines dieser Schemata einen Kandidatenschlüssel enthält, muss ein Schema mit einem solchen generiert werden.
• Nun die Schemata eleminieren, die in einem anderen Schema enthalten sind.

Die Boyce-Codd-Normalform ist eine Verschärfung der 3NF. Eine Relation ist in 3NF, wenn für jede FD mindestens eine der beiden Abhängigkeiten gilt:

• , d.h. die FD ist trivial
• ist Superschlüssel von .

Man kann mit dem Dekompositionsalgorithmus eine Relation in 3NF in Relationenschemata in BCNF überführen, dies ist nicht immer abhängigkeitserhaltend:

• Mit starten.
• Solange noch ein in nicht in BCNF ist:
  * Eine nicht-triviale FD in finden, die entweder kein Superschlüssel oder ist.  * in und zerlegen und statt in einfügen.