Para que servem grupos, monóides e anéis nos cálculos de banco de dados?

38

Por que uma empresa como o Twitter estaria interessada em conceitos algébricos como grupos, monóides e anéis? Veja seu repositório no github: twitter / algebird .

Tudo o que pude encontrar é:

Implementações de Monoids para algoritmos de aproximação interessantes, como filtro Bloom , HyperLogLog e CountMinSketch . Isso permite que você pense nessas operações sofisticadas como números e adicione-as no hadoop ou online para produzir estatísticas e análises poderosas.

e em outra parte da página do GitHub:

Ele foi originalmente desenvolvido como parte da API Matrix do Scalding , onde Matrices tinha valores que são elementos de Monoids , Groups ou Rings . Posteriormente, ficou claro que o código tinha uma aplicação mais ampla no Scalding e em outros projetos no Twitter.

O que poderia ser essa aplicação mais ampla? no Twitter e para interesse geral?


Parece que agregações de composição de bancos de dados têm uma estrutura semelhante a monóide.

Mesma pergunta no Quora: Qual é o interesse do Twitter em álgebra abstrata (com algebird)?


Tenho formação em matemática, mas não sou cientista da computação. Seria ótimo ter usos "no mundo real" de monoides e semi-grupos. Essas são normalmente consideradas construções teóricas inúteis e ignoradas em muitos cursos abstratos de álgebra (por falta de algo interessante a dizer).

john mangual
fonte
11
Achei este belo artigo, hon HackerNews news.ycombinator.com/item?id=5196708 "a álgebra de tipos de dados algébricos"
john mangual
concordou, acha surpreendente que o twitter esteja circulando por essas áreas, o que é bastante abstrato. a idéia principal parece ser componentes reutilizáveis ​​para um sistema semelhante ao Mapreduce. o algebird parece ter "desmembrado" da escaldadura. Aqui está uma palestra sobre escaldar . no entanto, não menciona os objetos algébricos. possivelmente, eles podem ser utilizados como primitivas de objectos de dados / tipos de manipulação nos fluxos de dados, que também são mapeadas em estilo de programação funcional ....
vzn
Uma breve troca com o autor de queimaduras em sua algebirdbiblioteca, no Twitter: twitter.com/posco/status/300692719561482240
john mangual
2
Eu contestaria fortemente a afirmação de que monoides e semi-grupos são considerados "construções teóricas inúteis", pois ambos também têm bastante utilidade na própria matemática, tanto na teoria das categorias quanto na modelagem de várias outras estruturas algébricas. De que ramo da matemática você vem que considera os semigrupos 'inúteis'?
Steven Stadnicki
Talvez o monóide sintático de uma linguagem formal seja relevante, embora não seja mencionado nas respostas. Embora eu espere, como muitas respostas, que seja relevante para o cálculo em geral, e não para o banco de dados.
PJTraill

Respostas:

27

A principal resposta é que, ao explorar a estrutura de semi-grupo, podemos construir sistemas que se paralelizam corretamente sem conhecer a operação subjacente (o usuário está prometendo associatividade).

Ao usar o Monoids, podemos tirar proveito da escassez (lidamos com muitas matrizes esparsas, onde quase todos os valores são zero em algum Monóide).

Usando anéis, podemos fazer a multiplicação da matriz sobre outras coisas que não números (o que ocasionalmente fizemos).

O próprio projeto do algebird (assim como o histórico do problema) explica claramente o que está acontecendo aqui: estamos construindo muitos algoritmos para agregação de grandes conjuntos de dados e alavancando a estrutura das operações nos dá uma vitória no lado dos sistemas (que geralmente é o ponto problemático ao tentar produzir algoritmos em milhares de nós).

Resolva os problemas do sistema uma vez para qualquer Semigrupo / Monóide / Grupo / Anel e, em seguida, você pode conectar qualquer algoritmo sem ter que pensar em Memcache, Hadoop, Storm, etc ...

Oscar Boykin
fonte
4
alguém pode expandir o vínculo entre matrizes esparsas e zeros em algum Monoid?
vzn
alguns links para exemplos ou leitura adicional seria muito bom
Erik Allik
11

Os monoides são onipresentes na programação, apenas que a maioria dos programadores não os conhece.

  • Operações numéricas como adição e multiplicação.
  • Multiplicação da matriz.
  • Basicamente, todas as estruturas de dados semelhantes a coleções formam monoides, onde a operação monoidal é concatenação ou união. Isso inclui listas, conjuntos, mapas de chaves para valores, vários tipos de árvores, etc.
  • Para um dado tipo funções em conjunto com a função de identidade sobre forma 's monóide endomorfismo.A A A AAAAAA

Algumas outras operações não formam monoides, mas semi-grupos. Um bom exemplo é procurar o elemento mínimo de uma sequência de elementos: representa o mínimo de e alguma ordem.a babab

Como os monóides são tão gerais, eles permitem escrever funções muito genéricas. Por exemplo, dobrar uma estrutura de dados pode ser expresso como mapeando cada elemento para um monóide e, em seguida, usando a operação monoidal para combiná-los em um único resultado.

Outro exemplo agradável e muito geral é a generalização da exponenciação ao quadrado para monoides (ou semi-grupos). Podemos escrever uma única função que calcula apenas nas operações . Aplicando-o a diferentes monoides, obtemos: O(logn)aantimesO(logn)

  • exponenciação rápida de números;
  • exponenciação rápida de matrizes (pode ser usada para calcular números de Fibonacci em multiplicações de );O(logn)
  • O método rápido para construir árvores de dedos grandes , pois o acréscimo de um elemento leva tempo mas a fusão de duas árvores leva .O(1)O(log(min(n1,n2)))
  • etc.

Para mais exemplos, consulte Exemplos de monoides / semigrupos na programação .

Petr Pudlák
fonte
7

Um problema importante nos sistemas de arquivos distribuídos ( DFS ) é gerar arquivos a partir de blocos distribuídos. A área do código de apagamento da teoria da informação e da álgebra (grupos, anéis, álgebra linear, ...) é usada extensivamente em sistemas de arquivos tolerantes a falhas distribuídos, por exemplo, no HDFS RAID (Hadoop Based File System). As empresas de redes sociais e nuvem são extensivamente baseadas no DFS, portanto, precisam de pessoas que sejam mestres em álgebra e código de eliminação para projetar sistemas melhores e de alto desempenho (como códigos de Reed-Solomon , etc.).

Este também é um bom pôster para sua aplicação (álgebra) no armazenamento em nuvem: Novos códigos para armazenamento em nuvem

Reza
fonte
6

Se sua pergunta for

Quais são os exemplos de grupos, monóides e anéis na computação?

então, um exemplo que posso pensar de imediato é o de algoritmos de localização de caminhos na teoria dos grafos. Se definirmos um semiring com como e como , podemos usar a multiplicação de matrizes com a matriz de adjacência para encontrar o caminho mais curto de todos os pares. Este método é realmente descrito no CLRS.min ++min+

Embora isso possa parecer apenas teórico de uma perspectiva algébrica, permite-nos utilizar bibliotecas de álgebra linear muito otimizadas para problemas gráficos. O BLAS combinatório é uma dessas bibliotecas.

Nicholas Mancuso
fonte
11
Sim, e adicionamos o minplus para fazer exatamente isso: github.com/twitter/algebird/blob/develop/algebird-core/src/main/…
Oscar Boykin
4

O conjunto de todas as palavras sobre algum alfabeto finito, juntamente com a concatenação, forma o monóide livre . Portanto, todo o campo da linguagem formal pode ser visto através da lente algébrica, e às vezes é ensinado assim.(Σ,)

Em troca, considerações sobre linguagens formais produziram o analisador Earley, que pode ser estendido para análise em semirrings . Isso é útil no processamento de linguagem natural e em outras áreas usando modelos estocásticos para linguagens (formais).

Rafael
fonte
3

Tenho formação em matemática, mas não sou cientista da computação. Seria ótimo ter usos "no mundo real" de monoides e semi-grupos. Essas são normalmente consideradas construções teóricas inúteis e ignoradas em muitos cursos abstratos de álgebra (por falta de algo interessante a dizer).

Há muito interessante a dizer. No entanto, é mais um tópico de matemática e combinatória discretas do que de álgebra e análise abstratas, pelo menos para os tópicos menos triviais. Há também a questão de quanto você precisa saber sobre um determinado tópico antes de poder dizer a outra pessoa que seria um tópico matemático interessante relacionado a monoides e semigrupos. Por exemplo, acho os seguintes tópicos (relacionados a semigrupos) interessantes:

  • semigrupos finitos e teoria de Krohn-Rhodes
  • simetrias parciais, semigrupos inversos, grupóides e quasicristais
  • Semirings e geometria tropical
  • ordens parciais e funções de Möbius
  • funções submodulares e decomposições (de Dulmage-Mendelsohn)

Sei muito sobre cada um desses tópicos? Provavelmente não. Também existem muitos tópicos matemáticos relacionados a monoides e semigrupos, alguns deles são mais internos à própria teoria de semigrupos (como as relações de Green), outros são mais gerais e não são específicos para semigrupos (semigrupos universais, teoremas de homomorfismos e isomorfismos, estruturas de quocientes e congruências), mas também importante do ponto de vista matemático. Os tópicos que citei acima têm principalmente aplicativos do "mundo real", mas há outros tópicos relacionados que também têm aplicativos do "mundo real".


O exposto acima não é uma resposta à pergunta real, mas trata apenas da observação "... são normalmente consideradas construções teóricas inúteis ... por falta de algo interessante para dizer ...". Então, listei alguns pontos "interessantes", afirmei que os aplicativos têm "mundo real" e agora a Hi-Angel solicita algumas informações sobre esses aplicativos. Mas porque "há muito interessante a dizer", não espere muito dessa informação: o teorema de Krohn-Rhodes é um teorema de decomposição para semigrupos finitos. Suas aplicações envolvem a interpretação do produto da grinalda como uma espécie de composição (de transdutores) em conexão com a teoria dos autômatos e linguagens regulares,Mark V Lawson: duas palestras tutoriais e material de apoio continham (404 agora) um bom material sobre Semigrupos Inversos . A base para suas aplicações é a conexão com o semigrupo inverso simétrico , ou seja, o conjunto de todas as bijeções parciais em um conjunto. Também se pode começar com caracterizações algébricas básicas de semigrupos inversos, mas essa abordagem corre o risco de negligenciar as conexões com ordens parciais, importantes para muitas aplicações. Algum dia terei que publicar um blog sobre uma aplicação específica de semigrupos inversos como "hierarquia" usada para comprimir layouts de semicondutores. Aplicações de semirrecursos já foram descritas em outras respostas (e a geometria tropical nos levaria longe da ciência da computação). Como monóides e semigrupos também estão relacionados a ordens parciais, tópicos interessantes como Möbius funcionam como descrito em Combinatorics: The Rota Way também estão relacionados. E também os tópicos de Matrizes e Matroids para Análise de Sistemas, como a decomposição de Dulmage-Mendelsohn, tornam - se relacionados, que foram uma das minhas motivações para estudar a teoria da rede (e estruturas hierárquicas ocultas).

Thomas Klimpel
fonte
Não que eu esteja reclamando, mas acho que se você adicionasse um pouco de informação sobre uma aplicação na vida real dos pontos listados, você teria muito mais votos positivos.
Hi-Angel
11
@ Hi-Angel O comentário acima não é uma resposta à pergunta real, mas trata apenas do comentário "... construção teórica inútil ... falta de algo interessante para dizer ...". Isso sugere que talvez eu não seja a pessoa mais qualificada para abordar isso: "Sei muito sobre cada um desses tópicos? Provavelmente não". Meu post mais votado se enquadra na mesma categoria. Benjamin Steinberg chama isso de uma área de "tóxicos" , e ele estaria qualificado para "resposta" ...
Thomas Klimpel