Existe-t-il une relation entre l'algèbre / calcul relationnel et la théorie des catégories?

Je connais au moins deux approches théoriques différentes pour comprendre les bases de données relationnelles: l'algèbre / calcul relationnel de Codd et la théorie des catégories.

Existe-t-il une relation entre ces deux approches? Sont-ils en quelque sorte équivalents? Existe-t-il des travaux d'introduction expliquant comment ces deux cadres expliquent les bases de données relationnelles?

Contexte: Il y a quelque temps, j'ai lu la théorie des catégories pour les scientifiques de David Spivak qui a passé un certain temps à discuter de la façon dont la théorie des catégories pourrait être appliquée pour comprendre la théorie des bases de données relationnelles. Cependant, ayant peu d'expérience personnelle sur ce que sont les bases de données relationnelles ou pourquoi elles sont utiles, à l'époque, je n'appréciais pas pleinement les profondeurs de la perspicacité trouvées dans le livre.

Cependant, récemment, j'ai découvert les requêtes SQL et deux packages R pour la manipulation des données: dplyr et data.table . SQL peut apparemment exprimer une grande partie des idées de l'algèbre / calcul / modèle relationnel de Codd, mais pas toutes . De plus, l'auteur de dplyr, Hadley Wickham, a déclaré explicitement que sa philosophie sous-jacente au package est basée sur les travaux de Codd sur l'algèbre relationnelle et que les commandes de base de data.table correspondent assez bien aux commandes en SQL et en dplyr.

Je sais également que la théorie des catégories influence de nombreux programmeurs utilisant des langages de programmation fonctionnels comme Haskell. Cependant, je ne suis pas vraiment conscient de l'utilisation de la programmation fonctionnelle pour la manipulation de données ou la science des données, en plus du paquet purrr de Hadley Wickham pour R, du fait qu'Apache Spark est écrit en Scala et des technologies liées à MapReduce .

Tout cela me suggère qu'il devrait y avoir une sorte de relation entre la théorie des catégories et l'algèbre / calcul relationnel de Codd, mais je n'ai jamais entendu parler de quelqu'un expliquant une telle connexion ou expliquant comment elle sous-tend les décisions de conception dans la manipulation populaire des données et technologies de bases de données relationnelles. Je pense donc aussi que je peux me tromper complètement.

EDIT: Apparemment, David Spivak a travaillé sur un " langage de requête functorial (FQL) ". Cela peut sembler être une application d'une telle connexion théorique, à condition qu'elle existe.

Remarque: je ne sais pas si "structures relationnelles" est la balise appropriée pour discuter des bases de données relationnelles ou de l'algèbre / calcul relationnel. Cet article de Wikipédia suggère qu'ils pourraient être connectés, mais finalement je ne sais pas ce que signifie l'expression "structure relationnelle". N'hésitez pas à réétiqueter.

Les approches catégoriques des langages de requête sont un peu un créneau, mais je pense que c'est un créneau très intéressant!

Peter Buneman et Torsten Grust sont deux des figures clés dans ce domaine . De toute évidence, ils n'ont pas fait tout le travail, mais si vous commencez avec leurs papiers et tracez le graphique de citation, vous obtiendrez une assez bonne couverture de la zone.

L'observation centrale à partir de laquelle ils fonctionnent est que, puisqu'une relation peut être considérée comme un ensemble de tuples, le foncteur du jeu de puissance peut être interprété comme prenant un type de tuple au type de relations sur ce tuple. Ensuite, le fait que le foncteur du jeu de puissances forme une monade signifie que vous pouvez utiliser des idées inspirées de la syntaxe de compréhension de la monade de Philip Wadler pour donner un calcul d'inspiration catégorique pour les requêtes avec une riche théorie équationnelle.

En effet, le système de requête de Buneman et al. Kleisli tire son nom du fait que les monades sont parfois appelées "triples de Kleisli".

La thèse de doctorat de Grust, Comprehending Queries , résume ces idées en détail, y compris l'utilisation de morphismes monades pour modéliser les opérateurs d'agrégation (comme sumet count). Grust et son groupe ont également construit un système, Ferry , qui a étudié comment intégrer des bases de données dans des langages de programmation.

$(\bullet) : \mathcal{P}(X) \times \mathcal{P}(Y) \to \mathcal{P}(X \times Y)$$\mu : \mathcal{P}(\mathcal{P}(X)) \to \mathcal{P}(X)$

C'est probablement le principal flux de travail sur les approches catégoriques des langages de requête.

Une nouvelle idée (qui n'a malheureusement pas eu autant de succès que je pense qu'elle mérite) est le travail de David Spivak sur l'utilisation d'ensembles simplicial pour modéliser des bases de données - voir Bases de données Simplicial . L'innovation centrale est que la structure simplicial permet de modéliser explicitement l'ensemble du schéma de base de données, y compris les relations entre les tables (par exemple, le système de clés étrangères), ce qui permet de donner une sémantique aux opérations de mise à jour de schéma.

Un autre écart par rapport aux langages de requête standard sont les langages de programmation à logique restreinte tels que Datalog, qui peuvent être compris comme une algèbre relationnelle plus un opérateur à point fixe. Les points fixes permettent d'exprimer des choses comme les requêtes de fermeture transitive, et donc de nouvelles bases de données comme les langages de requête de fonctionnalité Datomic basés sur Datalog. Mon doctorant, Michael Arntzenius , et moi avons étudié la sémantique de Datalog, et nous avons trouvé un analogue fonctionnel que nous appelons Datafun , qui a une interprétation assez catégorique en termes de catégories de posets et de semi-réseaux.