Existe-t-il un isomorphisme entre la théorie de la catégorie (sous-ensemble de) et l'algèbre relationnelle?

cs.stackexchange https://cs.stackexchange.com/questions/68211

Question

Cela vient du point de vue du Big Data. Fondamentalement, de nombreux frameworks (comme Apache Spark) "compensent" le manque d'opérations relationnelles en fournissant des interfaces de fonctor / monade et il y a un mouvement similaire vers les conversions de chats à SQL (lisse dans Scala). Par exemple, nous avons besoin de jointure naturelle (en supposant aucune répétition sur les index) pour la multiplication par élément des vecteurs de la perspective SQL, qui pourrait être considéré comme zip + map(multiply) (Mlib de Spark, cependant, a déjà ElementwiseProduct) dans les applications de la théorie des catégories.

Dire simplement (les exemples suivants se trouvent à Scala):

  • Le sous-cas référencé de la jointure peut être considéré comme un fonctor applicatif (sur trié collection), ce qui nous donne à son tour zip: List(1,2,3).ap(List(2,4,8).map(a => (b: Int) => a * b)) --> (List(1,2,3) zip List(2,4,8)).map(x => x._1 * x._2). De plus, nous pouvons l'induire à d'autres joints, en supposant un prétraitement (groupBy opérateur ou simplement surjection, ou généralement - un épimorphisme).

  • D'autres joints et sélection peuvent être considérés comme Monad. Par exemple, WHERE est juste: List(1,2,2,4).flatMap(x => if (x < 3) List(x) else List.empty) --> List(1,2,2,4).filter(_ < 3)

  • Les données elle-même sont juste ADT (Gadt aussi?), Qui à son tour ressemble à une simple catégorie de set (ou plus d'une manière générale - fermée cartésienne), il devrait donc (je suppose) des opérations basées sur le set (dû au curry- Howard-Lambek lui-même) et aussi des opérations comme RENAME (du moins dans la pratique).

  • l'agrégation correspond à fold/reduce (catamorphisme)

Donc, ce que je demande, c'est que pouvons-nous construire un isomorphisme entre (peut-être le sous-ensemble de) la théorie de la catégorie et (l'ensemble) de l'algèbre relationnelle ou y a-t-il quelque chose à découvert? Si cela fonctionne, quel «sous-ensemble» exact de catégories est isomorphe à Relalgebra?

Vous pouvez voir que mes propres hypothèses sont assez larges tandis que des solutions formelles comme Correspondance Curry-Howard-Lambek pour Logic-Cats-Lambda sont plus précis - donc en fait, je demande une référence à une étude accomplie (qui montre une relation directe) avec plus d'exemples dans Scala / Haskell.

Éditer: La réponse acceptée m'a fait penser que je suis allé trop loin en représentant les jointures et les conditions en tant que monade (en particulier en utilisant une valeur vide qui instancie efficacement), je pense que les retraits devraient suffire au moins pour le sous-ensemble de SQL de Relalgebra. Les monades sont meilleures pour des trucs d'ordre supérieur (nidification) comme Group By, qui ne fait pas partie de Relalgebra.

Pas de solution correcte

Licencié sous: CC-BY-SA avec attribution
Non affilié à cs.stackexchange
scroll top