Gibt es einen Zusammenhang zwischen relationaler Algebra / Analysis und Kategorietheorie?

Ich kenne mindestens zwei verschiedene theoretische Ansätze zum Verständnis relationaler Datenbanken: Codds relationale Algebra / Kalkül und Kategorietheorie.

Gibt es eine Beziehung zwischen diesen beiden Ansätzen? Sind sie in gewissem Sinne gleichwertig? Gibt es eine einführende Arbeit, die erklärt, wie beide Frameworks relationale Datenbanken erklären?

Hintergrund: Vor einiger Zeit habe ich David Spivaks Kategorietheorie für Wissenschaftler gelesen, in der lange darüber diskutiert wurde, wie Kategorietheorie angewendet werden kann, um die Theorie relationaler Datenbanken zu verstehen. Da ich jedoch wenig persönliche Erfahrung darüber habe, was relationale Datenbanken sind oder warum sie nützlich sind, wusste ich zu diesem Zeitpunkt nicht genau, welche Tiefen von Einsichten in dem Buch enthalten sind.

In letzter Zeit habe ich jedoch etwas über SQL- Abfragen und zwei R- Pakete für die Datenmanipulation gelernt : dplyr und data.table . SQL kann anscheinend viele Ideen der relationalen Algebra / des Kalküls / des Modells von Codd ausdrücken , aber nicht alle . Darüber hinaus hat der Autor von dplyr, Hadley Wickham, ausdrücklich erklärt, dass seine dem Paket zugrunde liegende Philosophie auf Codds Arbeit zur relationalen Algebra beruht und die grundlegenden Befehle von data.table den Befehlen in SQL und dplyr ziemlich gut entsprechen.

Ich weiß auch, dass die Kategorietheorie viele Programmierer beeinflusst, die funktionale Programmiersprachen wie Haskell verwenden. Ich bin mir jedoch nicht wirklich bewusst, dass neben Hadley Wickhams Purrr- Paket für R, der Tatsache, dass Apache Spark in Scala geschrieben ist , und Technologien im Zusammenhang mit MapReduce irgendeine Verwendung von funktionaler Programmierung für Datenmanipulation oder Datenwissenschaft vorhanden ist .

Alle diese Art von sagt mir , dass es sollte zwischen Kategorientheorie und Codds relationale Algebra / Kalkül, aber ich habe noch nie gehört , von jemand machen eine solche Verbindung explizit oder erklären , wie es zu Grunde liegt die Design - Entscheidungen in der populären Datenmanipulation irgendeine Art von Beziehung sein und relationale Datenbanktechnologien. Ich vermute also auch, dass ich völlig falsch liegen könnte.

EDIT: Anscheinend hat David Spivak an einer " functorial query language (FQL) " gearbeitet. Dies scheint eine Anwendung einer solchen theoretischen Verbindung zu sein, sofern sie existiert.

Hinweis: Ich bin mir nicht sicher, ob "relationale Strukturen" das geeignete Tag für die Diskussion relationaler Datenbanken oder relationaler Algebra / Kalkül ist. Dieser Wikipedia-Artikel schlägt vor, dass sie miteinander verbunden sind, aber letztendlich weiß ich nicht, was der Ausdruck "relationale Struktur" bedeutet. Bitte zögern Sie nicht, erneut zu taggen.

Kategoriale Ansätze für Abfragesprachen sind ein bisschen von Nischeninteresse, aber ich denke, es ist eine sehr interessante Nische!

Zwei der Schlüsselfiguren in diesem Bereich sind Peter Buneman und Torsten Grust . Offensichtlich haben sie nicht die ganze Arbeit erledigt, aber wenn Sie mit ihren Papieren beginnen und das Zitationsdiagramm nachzeichnen, erhalten Sie eine ziemlich gute Abdeckung des Gebiets.

Die zentrale Beobachtung, von der sie ausgehen, ist, dass der Powerset-Funktor so interpretiert werden kann, dass er einen Tupeltyp zu dem Typ der Beziehungen über dieses Tupel nimmt, da eine Beziehung als eine Menge von Tupeln betrachtet werden kann. Die Tatsache, dass der Powerset-Funktor eine Monade bildet, bedeutet, dass Sie anhand der von Philip Wadlers Monadenverständnissyntax inspirierten Ideen einen kategorisch inspirierten Kalkül für Abfragen mit einer umfassenden Gleichungstheorie erstellen können.

Tatsächlich hat das Abfragesystem von Buneman et al., Kleisli, seinen Namen von der Tatsache erhalten, dass Monaden manchmal als "Kleisli-Tripel" bezeichnet werden.

Grusts Doktorarbeit, Comprehending Queries , arbeitet diese Ideen im Detail aus, einschließlich der Verwendung von Monadenmorphismen zur Modellierung von Aggregationsoperatoren (wie sumund count). Grust und seine Gruppe bauten auch ein System, Ferry , das die Integration von Datenbanken in Programmiersprachen untersuchte.

Eines der Hauptprobleme in dieser Arbeit (und auch in Kleisli, wenn der Speicher dient) ist, dass monadische Abfragesprachen tendenziell etwas ausdrucksvoller sind als relationale Algebra - sie ermöglichen Abfragen, Mengen von Mengen zu verarbeiten. Das Kompilieren in SQL oder relationale Algebra erfordert einige Sorgfalt (siehe z. B. Cheney et al., Eine praktische Theorie für sprachintegrierte Abfragen ), aber das Grundproblem hat eine sehr schöne kategoriale Formulierung. In der relationalen Algebra wird nur die monoidale Struktur des Powerset-Funktors verwendet, dh die Existenz einer natürlichen Transformation des kartesischen Produkts ; und monadische Abfragesprachen erfordern auch den Join$(\bullet) : \mathcal{P}(X) \times \mathcal{P}(Y) \to \mathcal{P}(X \times Y)$$\mu : \mathcal{P}(\mathcal{P}(X)) \to \mathcal{P}(X)$.

Das ist wahrscheinlich der Hauptarbeitsstrom bei kategorialen Ansätzen für Abfragesprachen.

Eine neue Idee (die leider nicht so viel Anklang gefunden hat, wie ich denke, dass sie es verdient) ist David Spivaks Arbeit, einfache Mengen zum Modellieren von Datenbanken zu verwenden - siehe Simplicial Databases . Die zentrale Neuerung besteht darin, dass die einfache Struktur die explizite Modellierung des gesamten Datenbankschemas einschließlich der Beziehungen zwischen Tabellen (z. B. dem System von Fremdschlüsseln) ermöglicht und somit die Semantik für Schemaaktualisierungsvorgänge ermöglicht.

Eine weitere Abweichung von den Standard-Abfragesprachen sind eingeschränkte logische Programmiersprachen wie Datalog, die als relationale Algebra plus Festkommaoperator verstanden werden können. Feste Punkte ermöglichen das Ausdrücken von Abfragen zum transitiven Schließen, sodass neue Datenbanken wie Datomic Feature-Abfragesprachen auf der Basis von Datalog verwendet werden können. Mein Doktorand Michael Arntzenius und ich haben die Semantik von Datalog studiert und ein funktionales Analogon entwickelt , das wir Datafun nennen und das hinsichtlich der Kategorien von Posets und Semilattices eine ziemlich kategorische Interpretation aufweist.