Existe uma relação entre álgebra relacional / cálculo e teoria de categorias?

17

Estou ciente de pelo menos duas abordagens teóricas diferentes para entender os bancos de dados relacionais: a álgebra / cálculo relacional de Codd e a teoria das categorias.

Existe alguma relação entre essas duas abordagens? Em certo sentido, eles são equivalentes? Existe algum trabalho introdutório explicando como essas duas estruturas explicam bancos de dados relacionais?

Antecedentes: Há algum tempo, li a Teoria das categorias para cientistas de David Spivak, que passou bastante tempo discutindo como a teoria das categorias poderia ser aplicada para entender a teoria dos bancos de dados relacionais. No entanto, tendo pouca experiência pessoal sobre o que são bancos de dados relacionais ou por que são úteis, na época eu não apreciava completamente as profundezas do insight encontradas no livro.

No entanto, recentemente eu tenho aprendido sobre consultas SQL e dois pacotes R para manipulação de dados: dplyr e data.table . Aparentemente, o SQL pode expressar muitas das idéias da álgebra / cálculo / modelo relacional de Codd, mas não todas . Além disso, o autor do dplyr, Hadley Wickham, declarou explicitamente que sua filosofia subjacente ao pacote é baseada no trabalho de Codd em álgebra relacional e os comandos básicos da tabela data.table são muito bem mapeados para comandos no SQL e no dplyr.

Eu também sei que a teoria das categorias influencia muitos programadores que usam linguagens de programação funcional como Haskell. No entanto, não estou realmente ciente de que existe algum uso de programação funcional para manipulação de dados ou ciência de dados, além do pacote purrr de Hadley Wickham para R, o fato de o Apache Spark estar escrito em Scala e as tecnologias relacionadas ao MapReduce .

Tudo isso sugere que deveria haver algum tipo de relação entre a teoria das categorias e a álgebra / cálculo relacional de Codd, mas nunca ouvi falar de alguém que explique essa conexão ou explique como ela está subjacente às decisões de projeto na manipulação de dados popular e tecnologias de banco de dados relacional. Então, eu também suspeito que poderia estar completamente errado.

Edição: Aparentemente, David Spivak trabalhou em uma " linguagem de consulta funcional (FQL) ". Parece que pode ser uma aplicação dessa conexão teórica, desde que exista.

Nota: Não tenho certeza se "estruturas relacionais" é a tag apropriada para discussão de bancos de dados relacionais ou álgebra / cálculo relacional. Este artigo da Wikipedia sugere que eles podem estar conectados, mas, no final das contas, não sei o que a frase "estrutura relacional" significa. Sinta-se livre para re-etiquetar.

Chill2Macht
fonte
2
Você já viu o trabalho de Tannen e Buneman, por exemplo, Uma abordagem estrutural para o design da linguagem de consulta ?
Reinierpost
@reinierpost Eu não tenho, mas vou dar uma olhada.
Chill2Macht

Respostas:

12

Abordagens categóricas para linguagens de consulta são um pouco de interesse de nicho, mas acho que é um nicho muito interessante!

Duas das figuras-chave nesta área são Peter Buneman e Torsten Grust . Obviamente, eles não fizeram todo o trabalho, mas se você começar com os documentos e traçar o gráfico de citações, obterá uma cobertura muito boa da área.

A observação central a partir da qual eles trabalham é que, como uma relação pode ser vista como um conjunto de tuplas, o functor do conjunto de potências pode ser interpretado como tendo um tipo de tupla para o tipo de relações sobre essa tupla. Então, o fato de o functor do conjunto de conjuntos formar uma mônada significa que você pode usar idéias inspiradas na sintaxe de compreensão de mônadas de Philip Wadler para fornecer um cálculo categoricamente inspirado para consultas com uma rica teoria equacional.

De fato, o sistema de consultas de Buneman e cols. Kleisli recebeu esse nome pelo fato de que as mônadas às vezes são chamadas de "triplos Kleisli".

A tese de doutorado de Grust, Comprehending Queries , elabora essas idéias em detalhes, incluindo o uso de morfismos de mônada para modelar operadores de agregação (como sume count). Grust e seu grupo também construíram um sistema, Ferry , que estudava como integrar bancos de dados em linguagens de programação.

():P(X)×P(Y)P(X×Y)μ:P(P(X))P(X)

Esse é provavelmente o principal fluxo de trabalho em abordagens categóricas para linguagens de consulta.

Uma nova idéia (que infelizmente não teve tanta tração quanto eu acho que merece) é o trabalho de David Spivak sobre o uso de conjuntos simples para modelar bancos de dados - consulte Bancos de dados simplificados . A inovação central é que a estrutura simples permite modelar explicitamente todo o esquema do banco de dados, incluindo os relacionamentos entre as tabelas (por exemplo, o sistema de chaves estrangeiras), e isso permite fornecer semântica às operações de atualização do esquema.

Outro desvio das linguagens de consulta padrão são as linguagens de programação lógica restrita, como o Datalog, que podem ser entendidas como álgebra relacional e um operador de ponto fixo. Os pontos fixos permitem expressar coisas como consultas de fechamento transitivas e, portanto, novos bancos de dados como o Datomic apresentam linguagens de consulta baseadas no Datalog. Meu aluno de doutorado, Michael Arntzenius , e eu estudamos a semântica do Datalog, e criamos um análogo funcional que chamamos Datafun , que tem uma interpretação bastante categórica em termos das categorias de posets e semilattices.

Neel Krishnaswami
fonte