¿Existe una relación entre álgebra relacional / cálculo y teoría de categorías?

17

Conozco al menos dos enfoques teóricos diferentes para comprender las bases de datos relacionales: álgebra / cálculo relacional de Codd y teoría de categorías.

¿Hay alguna relación entre estos dos enfoques? ¿Son en algún sentido equivalentes? ¿Existe algún trabajo introductorio que explique cómo ambos marcos explican las bases de datos relacionales?

Antecedentes: Hace un tiempo leí la teoría de la categoría de David Spivak para científicos, que pasó bastante tiempo discutiendo cómo la teoría de la categoría podría aplicarse para comprender la teoría de las bases de datos relacionales. Sin embargo, al tener poca experiencia personal sobre qué son las bases de datos relacionales o por qué son útiles, en ese momento no aprecié completamente la profundidad de la información que se encuentra en el libro.

Sin embargo, recientemente he estado aprendiendo sobre consultas SQL y dos paquetes R para la manipulación de datos: dplyr y data.table . SQL aparentemente puede expresar muchas de las ideas del álgebra / cálculo / modelo relacional de Codd, pero no todas . Además, el autor de dplyr, Hadley Wickham, ha declarado explícitamente que su filosofía subyacente al paquete se basa en el trabajo de Codd sobre álgebra relacional, y los comandos básicos de data.table se correlacionan bastante bien con los comandos en SQL y dplyr.

También sé que la teoría de categorías influye en muchos programadores que usan lenguajes de programación funcionales como Haskell. Sin embargo, no estoy al tanto de que haya algún uso de la programación funcional para la manipulación de datos o la ciencia de datos, además del paquete de ronroneo de Hadley Wickham para R, el hecho de que Apache Spark está escrito en Scala y las tecnologías relacionadas con MapReduce .

Todo esto me sugiere que debería haber algún tipo de relación entre la teoría de categorías y el álgebra / cálculo relacional de Codd, pero nunca he oído hablar de alguien que explique tal conexión o explique cómo subyace a las decisiones de diseño en la manipulación de datos populares. y tecnologías de bases de datos relacionales. Entonces también sospecho que podría estar completamente equivocado.

EDITAR: Aparentemente, David Spivak ha trabajado en un " lenguaje de consulta funcional (FQL) ". Parece que podría ser una aplicación de una conexión tan teórica, siempre que exista.

Nota: No estoy seguro de si "estructuras relacionales" es la etiqueta apropiada para la discusión de bases de datos relacionales o álgebra / cálculo relacional. Este artículo de Wikipedia sugiere que podrían estar conectados, pero finalmente no sé qué significa la frase "estructura relacional". No dude en volver a etiquetar.

Chill2Macht
fuente
2
¿Has visto trabajos de Tannen y Buneman, por ejemplo, un enfoque estructural para el diseño del lenguaje de consulta ?
reinierpost
@reinierpost No lo he hecho, pero lo miraré.
Chill2Macht

Respuestas:

12

Los enfoques categóricos para los lenguajes de consulta son un poco interesantes, pero creo que es un nicho muy interesante.

Dos de las figuras clave en esta área son Peter Buneman y Torsten Grust . Obviamente, no hicieron todo el trabajo, pero si comienzas con sus documentos y trazas el gráfico de citas, obtendrás una cobertura bastante buena del área.

La observación central de la que trabajan es que, dado que una relación puede verse como un conjunto de tuplas, el functor del conjunto de potencia puede interpretarse como tomar un tipo de tupla al tipo de relaciones sobre esa tupla. Entonces, el hecho de que el funset de powerset forme una mónada significa que puede usar ideas inspiradas en la sintaxis de comprensión de mónada de Philip Wadler para dar un cálculo inspirado categóricamente para consultas con una rica teoría de ecuaciones.

De hecho, el sistema de consulta de Buneman et al. Kleisli obtuvo su nombre del hecho de que las mónadas a veces se llaman "Kleisli triples".

La tesis doctoral de Grust, Comprehending Queries , resuelve estas ideas en detalle, incluido el uso de morfismos de mónada para modelar operadores de agregación (como sumy count). Grust y su grupo también construyeron un sistema, Ferry , que estudió cómo integrar bases de datos en lenguajes de programación.

():PAG(X)×PAG(Y)PAG(X×Y)μ:PAG(PAG(X))PAG(X)

Esa es probablemente la secuencia principal de trabajo sobre enfoques categóricos para los lenguajes de consulta.

Una nueva idea (que desafortunadamente no ha tenido tanta tracción como creo que merece) es el trabajo de David Spivak en el uso de conjuntos simpliciales para modelar bases de datos: consulte Bases de datos simples . La innovación central es que la estructura simplicial permite modelar explícitamente todo el esquema de la base de datos, incluidas las relaciones entre las tablas (por ejemplo, el sistema de claves foráneas), y esto permite dar semántica a las operaciones de actualización del esquema.

Otra desviación de los lenguajes de consulta estándar son los lenguajes de programación de lógica restringida como Datalog, que puede entenderse como álgebra relacional más un operador de punto fijo. Los puntos fijos permiten expresar cosas como consultas de cierre transitivas y, por lo tanto, nuevas bases de datos como Datomic ofrecen lenguajes de consulta basados ​​en Datalog. Mi estudiante de doctorado, Michael Arntzenius , y yo hemos estudiado la semántica de Datalog, y encontramos un análogo funcional que llamamos Datafun , que tiene una interpretación bastante categórica en términos de las categorías de posets y semilattices.

Neel Krishnaswami
fuente