Functional Dependencies in the Higher-Order Entity-Relationship Model

Die vorliegende Diplomarbeit beschäftigt sich mit der Frage der Axiomatisierbarkeit funktionaler Abhängigkeiten in konzeptionalen Datenbanken. Den Betrachtungen liegt das Higher-Order Entity-Relationship Modell zugrunde. Die Arbeit entstand im Rahmen eines einjährigen Studienaufenthaltes bei Prof. Schewe an der Massey University in Palmerston North in Neuseeland.

Datenbanken wurden entwickelt, um die Verwaltung von Massendaten im Mehrbenutzerbetrieb zu ermöglichen. Bis heute basieren die meisten Datenbanken und deren theoretischen Betrachtungen auf dem von E. F. Codd entwickelten Relationalen Datenmodel (RDM). Die Beschreibungen von Beziehungen zwischen Daten erfolgt im RDM mittels einfacher Relationen. Dies und die Tatsache, dass das RDM für die meisten Anwendungen genügend Struktur bietet haben dazu geführt, dass das RDM das meist verbreitete Datenmodell ist.

Datenbanken modellieren Objekte der realen Welt und ihre Beziehungen untereinander. Abhängigkeiten in Datenbanken definieren dann einfach die Einschränkungen an die {Beziehung}, in der Objekte einer Datenbank zueinander stehen.

Eine wichtige Klasse von Abhängigkeiten sind funktionale Abhängigkeiten. Wenn wir funktionale Abhängigkeiten betrachten, so betrachten wir Abhängigkeiten zwischen Attributmengen eines Relationenschemas. Eine Menge A von Attributen hängt von einer Menge B von Attributen funktional ab, wenn gleiche Einträge in B gleiche Einträge in A implizieren. Daten in Datenbanken sollen möglichst redundanzfrei gespeichert und anomalienfrei verändert werden können. Die Boyce-Codd-Normalform (BCNF) erfüllt diese Forderung für funktionale Abhängigkeiten.

Zur expliziten Bestimmung der BCNF wird für eine Menge vorgegebener Abhängigkeiten die Menge aller folgerbaren Abhängigkeiten benötigt. Ist diese Menge bestimmbar, ohne alle Beziehungen der Datenbank betrachten zu müssen? Unter Verwendung eines korrekten und vollständigen System von syntaktischen Ableitungsregeln, den sogenannten Armstrong-Axiomen, ist es möglich, die Menge aller folgerbaren {Abhängigkeiten} effektiv zu bestimmen. Ableitungsregeln heißen korrekt, wenn jede ableitbare Abhängigkeit auch logisch folgerbar ist. Sie heißen vollständig, wenn jede folgerbare Abhängigkeit auch syntaktisch ableitbar ist. Eine Klasse von Abhängigkeiten, für die ein endliches korrektes und vollständiges Ableitungssystem existiert, heißt axiomatisierbar.

In den letzten zwanzig Jahren wurden Datenbankschemata von der konzeptionellen Seite betrachtet. Ein vielzitiertes Modell ist das Entity-Relationship Modell (ERM), das von P. P.-S. Chen eingeführt wurde. Seitdem hat es viele Erweiterungen dieses Modells gegeben. Eine Erweiterung ist das Higher-Order Entity-Relationship Modell (HERM) von B. Thalheim. Im HERM sind Beziehungen auch zwischen Beziehungen selbst erlaubt. So ermöglicht HERM eine sehr realitätsnahe Modellierung. Zudem ist die zugrundeliegende Theorie wohldefiniert. Um eine Normalform ähnlich der BCNF im RDM formulieren zu können, muss zunächst wieder die Frage der Axiomatisierbarkeit beantwortet werden. Erst die Existenz eines Ableitungssystems zur Axiomatisierung funktionaler Abhängigkeiten ermöglicht die explizite Formulierung einer Normalform. Die Betrachtung der Axiomatisierbarkeit funktionaler Abhängigkeiten im HERM ist Gegenstand der vorliegenden Arbeit.

Durch das Erweitern der Beziehungen hat sich das Aussehen der Attribute verändert. Zur Unterscheidung heißen Attribute im RDM einfache oder flache Attribute. Im HERM besteht ein Attribut aus ineinandergeschachtelten Attributen. Diese Eigenschaft ist namensgebend. Attribute heißen im HERM geschachtelte Attribute. Zu jedem Attribut werden Subattribute definiert. Bevor nun die Axiomatisierbarkeit gezeigt werden kann, muss zunächst die Struktur der Menge dieser Subattribute betrachtet werden. Es stellt sich heraus, dass Subattribute im HERM eine Heyting-Algebra bilden. Hierauf aufbauend können die erweiterten Armstrong-Axiome definiert und anschließend das Hauptresultat dieser Arbeit bewiesen werden.