Schema-Verfeinerung und Dekomposition

Schema-Verfeinerung ist der Prozess der Dekomposition einer Relation in kleinere Relationen, um eine gewünschte Normalform zu erreichen, unter der Voraussetzung, dass die Dekomposition verlustfrei ist und idealerweise die ursprünglichen Abhängigkeiten bewahrt.

Definition

Dekomposition ersetzt ein Relationsschema R durch eine Menge von Schemata, deren Attribute zusammen R abdecken, sodass die ursprüngliche Relation durch das Verknüpfen der Teile wiederhergestellt werden kann (verlustfreier Join) und, wenn möglich, jede ursprüngliche funktionale Abhängigkeit auf den Teilen durchgesetzt werden kann (Abhängigkeitserhaltung).

Scope

Dieses Thema behandelt die Algorithmen und Kriterien für die Dekomposition relationaler Schemata: die verlustfreie Join-Eigenschaft und wie sie getestet wird, die Abhängigkeitserhaltung und ihre Spannung mit höheren Normalformen sowie die Standard-Synthese- und Dekompositionsalgorithmen, die ein 3NF- (abhängigkeitserhaltend und verlustfrei) oder BCNF- (verlustfrei) Design aus einer Menge funktionaler Abhängigkeiten erzeugen. Es schließt die Definitionen der Normalformen selbst und der Abhängigkeiten, die die Dekomposition steuern, aus.

Core questions

• Was macht eine Dekomposition verlustfrei, und wie wird diese Eigenschaft getestet?
• Was bedeutet es, wenn eine Dekomposition Abhängigkeiten bewahrt?
• Warum kann die BCNF-Dekomposition die Abhängigkeitserhaltung nicht gewährleisten, während die 3NF-Synthese dies tut?
• Wie funktionieren die Standard-BCNF-Dekompositions- und 3NF-Synthesealgorithmen?
• Wie wird die Wahl zwischen BCNF und 3NF in der Praxis getroffen?

Key concepts

• Dekomposition eines Schemas
• verlustfreie Join-Eigenschaft
• Abhängigkeitserhaltung
• spurious tuples (Scheintupel)
• BCNF-Dekompositionsalgorithmus
• 3NF-Synthesealgorithmus
• minimale Überdeckung
• Kompromiss zwischen BCNF und 3NF

Key theories

Verlustfreie Join-Dekomposition

Eine binäre Dekomposition ist verlustfrei, wenn die gemeinsamen Attribute der beiden Teile einen Schlüssel von mindestens einem von ihnen bilden; Verlustfreiheit garantiert, dass das Verknüpfen der Teile genau die ursprüngliche Relation ohne spurious tuples (Scheintupel) rekonstruiert.

Abhängigkeitserhaltung

Eine Dekomposition bewahrt Abhängigkeiten, wenn die Vereinigung der auf den einzelnen Teilen durchsetzbaren Abhängigkeiten alle ursprünglichen Abhängigkeiten impliziert, sodass die Konsistenz ohne erneutes Berechnen von Joins überprüft werden kann.

BCNF-Dekomposition versus 3NF-Synthese

Der BCNF-Dekompositionsalgorithmus garantiert Verlustfreiheit, kann aber die Abhängigkeitserhaltung opfern, während der 3NF-Synthesealgorithmus aus einer minimalen Überdeckung sowohl einen verlustfreien Join als auch die Abhängigkeitserhaltung garantiert, auf Kosten eines möglichen Stopps bei 3NF.

Clinical relevance

Dekompositionsalgorithmen sind der Weg, wie die Normalisierungstheorie zu einem umsetzbaren Entwurfsverfahren wird: Ihre Anwendung führt zu Schemata, die Redundanz vermeiden und dennoch effizient rekonstruiert und validiert werden können, was sich direkt auf die Korrektheit und Wartbarkeit von Produktionsdatenbanken auswirkt.

History

Die Theorie der verlustfreien Join- und abhängigkeitserhaltenden Dekomposition wurde in den 1970er Jahren entwickelt, als Forscher formalisierten, wann das Aufteilen einer Relation sicher ist. Synthesealgorithmen, die abhängigkeitserhaltende 3NF-Designs erzeugen, und die Erkenntnis, dass BCNF mit der Abhängigkeitserhaltung in Konflikt geraten kann, wurden zu Standardmaterial in Datenbanktexten und bleiben zentral für das Schema-Design.

Key figures

• Edgar F. Codd
• Jeffrey D. Ullman
• Philip Bernstein

Seminal works

• silberschatz2019
• ramakrishnan2003
• garciamolina2008

Frequently asked questions

Was ist ein spurious tuple (Scheintupel) und warum ist es wichtig?

Ein spurious tuple (Scheintupel) ist eine Zeile, die erscheint, wenn man die Teile einer schlecht gewählten Dekomposition verknüpft, aber keiner realen Zeile der ursprünglichen Relation entspricht. Eine verlustfreie Join-Dekomposition ist genau eine solche, die keine spurious tuples (Scheintupel) erzeugt, weshalb Verlustfreiheit eine nicht verhandelbare Anforderung ist.

Warum sollte ich 3NF gegenüber BCNF wählen?

Die Dekomposition in BCNF bewahrt immer die verlustfreie Join-Eigenschaft, kann aber die Abhängigkeitserhaltung aufheben, was bedeutet, dass einige Einschränkungen nur durch das Verknüpfen von Tabellen überprüft werden könnten. Der 3NF-Synthesealgorithmus garantiert sowohl Verlustfreiheit als auch Abhängigkeitserhaltung, sodass Designer 3NF akzeptieren, wenn ein abhängigkeitserhaltendes BCNF-Design nicht existiert.