Completeness of Relational Algebra via Cylindric Algebra

1. Problemstellung

Der Artikel adressiert das fundamentale Problem der Vollständigkeit der relationalen Algebra in Bezug auf die erste Stufe der Prädikatenlogik (First-Order Logic, FOL).

• Hintergrund: Relationale Algebra (RA) ist eine prozedurale Abfragesprache für Datenbanken, während die Prädikatenlogik eine deklarative Sprache darstellt. Für die praktische Anwendung muss eine deklarative Abfrage in eine äquivalente, effizient ausführbare prozedurale Abfrage (RA-Ausdruck) übersetzt werden.
• Einschränkung: Nicht alle Formeln der Prädikatenlogik lassen sich in die relationale Algebra übersetzen (z. B. Formeln mit negierten Relationen ohne Einschränkung, wie $\neg r(x)$).
• Ziel: Es existiert bereits der Begriff der „erlaubten Formeln" (allowed formulas), für die eine solche Übersetzung möglich ist. Das Ziel des Autors ist es, einen neuen, algebraischen Beweis für die Vollständigkeit dieser erlaubten Formeln zu liefern und einen alternativen Algorithmus zur Umwandlung von Formeln in relationale Ausdrücke vorzustellen.
• Motivation: Der Hauptantrieb ist die Generalisierbarkeit des Beweises auf erweiterte relationale Modelle, die mit unvollständigen oder vagen Informationen umgehen (z. B. unscharfe Daten oder Ähnlichkeitsrelationen).

2. Methodik

Die zentrale Methodik des Papiers basiert auf der Einbettung der relationalen Algebra in die Zylindrische Algebra (Cylindric Algebra, CA), eine algebraische Struktur, die von Tarski zur Algebraisierung der Prädikatenlogik entwickelt wurde.

• Einbettung: Der Autor nutzt die bekannte Abbildung $\epsilon$, die relationale Mengen auf Mengen von Valuationen (Zuordnungen von Variablen zu Domänenwerten) abbildet. Diese Abbildung zeigt, dass die Operationen der relationalen Algebra (Projektion, Selektion, Join, Umbenennung) den Operationen der Zylindrischen Algebra (Zylindrisierung, Diagonale, Schnitt, Vereinigung) entsprechen.
• Strukturelle Analyse: Anstatt Formeln syntaktisch zu manipulieren, werden deren semantische Eigenschaften durch die Analyse von Gleichheits- und Ungleichheitsrelationen zwischen Variablen untersucht. Dafür werden die Konzepte der Equality ($eq(\phi)$) und Coequality ($coeq(\phi)$) eingeführt, die Äquivalenzklassen von Variablen innerhalb einer Formel beschreiben.
• Normalisierung: Ein neuer Algorithmus wird entwickelt, der eine gegebene Formel in eine normalisierte Form überführt. Dieser Prozess nutzt Hilfsfunktionen wie Generator ($gen(\phi)$) und Cogenerator ($cogen(\phi)$), um den Wertebereich der Formel einzuschränken und sicherzustellen, dass die resultierende Formel den strukturellen Anforderungen der relationalen Algebra entspricht.

3. Schlüsselbeiträge

Der Artikel liefert mehrere wesentliche theoretische und algorithmische Beiträge:

1. Alternativer Vollständigkeitsbeweis:
   Der Autor beweist, dass jede erlaubte Formel semantisch äquivalent zu einem relationalen Ausdruck ist. Im Gegensatz zu früheren Beweisen (z. B. VGT91) erfolgt dies rein algebraisch innerhalb der Zylindrischen Algebra. Dies ermöglicht es, die Beweistechnik leichter auf verallgemeinerte Modelle (z. B. mit unvollständigen Informationen) zu übertragen.

2. Definition und Behandlung von „Erlaubten Formeln":
   Der Begriff der erlaubten Formeln wird präzise definiert. Eine Formel ist erlaubt, wenn ihre freien Variablen mit den Variablen des Generators übereinstimmen und jede existenzielle Quantifizierung $(\exists x)\psi$ die Bedingung erfüllt, dass $x$ im Generator von $\psi$ enthalten ist. Dies stellt sicher, dass die Formel domänenunabhängig ist.

3. Algorithmus zur Normalisierung:
   Es wird ein detaillierter Algorithmus vorgestellt, der eine erlaubte Formel $\phi$ in eine normalisierte Form $norm(\phi, \psi)$ überführt.

   • Der Algorithmus nutzt rekursive Regeln für logische Operatoren (Negation, Konjunktion, Existenzquantor).
   • Er behandelt die Ausrichtung (Alignment) von freien Variablen, um die Struktur für die Übersetzung in die relationale Algebra vorzubereiten.
   • Ein besonderer Vorteil ist, dass die Negation als vollwertiger logischer Operator behandelt wird, was die Definition erlaubter Formeln klarer macht als in früheren Ansätzen.

4. Übersetzungsregel:
   Basierend auf der normalisierten Form wird eine direkte Übersetzungsfunktion $expr(\phi)$ definiert, die die Formel in einen relationalen Ausdruck (mit Operationen wie $\cup, -, \bowtie, \pi, \sigma, \rho$) umwandelt.

4. Ergebnisse

• Theorem 6.8: Jede erlaubte Formel ist semantisch äquivalent zu ihrer Normalisierung.
• Theorem 6.9: Alle erlaubten Formeln sind domänenunabhängig (domain independent).
• Korrektheit: Der vorgestellte Algorithmus garantiert, dass der erzeugte relationale Ausdruck für jede Datenbankstruktur das gleiche Ergebnis liefert wie die ursprüngliche logische Formel.
• Beispiel: Der Autor demonstriert den Algorithmus an einem komplexen Beispiel (relationale Division), zeigt, wie die Normalisierung durchgeführt wird und wie der finale relationale Ausdruck (Subtraktion von Joins) entsteht.

5. Bedeutung und Ausblick

Die Bedeutung dieses Werkes liegt vor allem in seiner Methodik und Generalisierbarkeit:

• Algebraischer Ansatz: Durch die Verlagerung des Beweises in den Kontext der Zylindrischen Algebra wird die Verbindung zwischen logischen Formeln und algebraischen Strukturen gestärkt. Dies bietet einen robusteren Rahmen für theoretische Untersuchungen als rein syntaktische Beweise.
• Erweiterbarkeit: Der Autor argumentiert, dass dieser Ansatz ideal geeignet ist, um Vollständigkeitsresultate für erweiterte Datenmodelle zu beweisen. Da Zylindrische Algebren verallgemeinert werden können (z. B. für unscharfe Mengen oder Modelle mit unvollständigen Informationen), kann die hier vorgestellte Beweistechnik genutzt werden, um zu zeigen, dass auch in diesen komplexeren Szenarien bestimmte logische Formeln effizient in relationale Ausdrücke übersetzbar sind.
• Praktische Relevanz: Obwohl der Fokus auf der Theorie liegt, bietet der vorgestellte Normalisierungs-Algorithmus eine klare Anleitung für die Implementierung von Query-Optimierern, die deklarative Abfragen in effiziente Ausführungspläne umwandeln müssen.

Zusammenfassend bietet der Artikel einen eleganten, algebraisch fundierten Beweis für die Vollständigkeit der relationalen Algebra und legt den Grundstein für die Anwendung dieser Prinzipien auf fortschrittlichere Datenmodelle jenseits der klassischen relationalen Datenbanken.