Jak agregacje bazy danych tworzą monoid?

Na cs.stackexchange zapytałem o bibliotekę algebird scala na githubie, spekulując, dlaczego mogą potrzebować abstrakcyjnego pakietu algebry.

Strona github zawiera kilka wskazówek:

Implementacje Monoidów dla interesujących algorytmów aproksymacyjnych, takich jak filtr Bloom, HyperLogLog i CountMinSketch. Pozwalają ci myśleć o tych wyrafinowanych operacjach, takich jak liczby, i dodawać je w hadoopie lub Internecie, aby tworzyć potężne statystyki i analizy.

oraz w innej części strony GitHub:

Został pierwotnie opracowany jako część API Matrix Scaldinga, gdzie Matryce miały wartości, które są elementami Monoidów, Grup lub Pierścieni. Następnie stało się jasne, że kod ma szersze zastosowanie w Scaldingu i innych projektach na Twitterze.

Nawet Oskar Boykin z Twittera zagrał:

Główną odpowiedzią jest to, że wykorzystując strukturę półgrupową, możemy budować systemy, które poprawnie działają równolegle, nie znając operacji leżącej u podstaw (użytkownik obiecuje skojarzenie).

Używając Monoidów, możemy skorzystać z rzadkości (mamy do czynienia z wieloma rzadkimi macierzami, w których prawie wszystkie wartości są zerowe w niektórych Monoidach).

Korzystając z pierścieni, możemy dokonywać mnożenia macierzy na rzeczach innych niż liczby (co czasami zrobiliśmy).

Sam projekt algebird (a także historia problemów) dość jasno wyjaśnia, co się tutaj dzieje: budujemy wiele algorytmów do agregacji dużych zestawów danych, a wykorzystanie struktury operacji daje nam zwycięstwo po stronie systemowej (co zwykle stanowi problem przy próbie produkcji algorytmów na tysiącach węzłów).

Rozwiąż problemy systemowe jeden raz dla dowolnej półgrupy / monoida / grupy / pierścienia, a następnie możesz podłączyć dowolny algorytm bez konieczności myślenia o Memcache, Hadoop, Storm itp.

Jakie są Bloom filters/ hyperloglog/ countminsketchjak liczby?

Jak to się dzieje, że agregacje baz danych mają strukturę monoidalną?
Jak wygląda ta monoida? Czy kiedykolwiek mają strukturę grupową?

Przydałyby się odniesienia do literatury.

Pytasz, dlaczego agregacje baz danych mają strukturę monoidalną.

$a$$b$$a$$b$$a.b$

$.$$(a.b).c = a.(b.c)$

Prawie zawsze istnieje pewien rodzaj tożsamości, niezależnie od tego, czy jest to liczba 0, czy 1, pusty ciąg znaków, macierz tożsamości, jednolity rozkład lub pusty zbiór, które zależą od operacji. W rzeczywistości dane zwykle tworzą monoid .

Praktyczny aspekt myślenia o danych jako o formowaniu monoidu polega na tym, że zapewnia on sposób omawiania operacji na różnych rodzajach danych za pomocą wspólnego języka algebraicznego. To następnie przekłada się na ogólne biblioteki kodów, które mogą obsługiwać dowolne monoidy, po prostu przekazując odpowiednią operację agregacji jako argument.

Zauważ, że wiele rodzajów danych nie ma odwrotności, więc struktura grupy jest zbyt wielka, by się spodziewać. Jeśli masz strukturę grupową, możliwe są dodatkowe sposoby manipulowania danymi, ale ponieważ ani macierze z mnożeniem, ani dodatnie liczby całkowite z dodawaniem nie mają odwrotności, dane nieuporządkowane grupowo są dość powszechne.

$+$$.$$.$$+$$.$

Pośredni model agregacji danych istnieje już od pewnego czasu w społeczności zajmującej się ograniczeniami. Zauważ, że wystąpienie problemu satysfakcji z ograniczenia jest łączącym zapytaniem dotyczącym konkretnej bazy danych faktów, więc jest to dość ogólne: większość praktycznych zapytań dotyczących danych jest łączna.

• Stefano Bistarelli, Ugo Montanari i Francesca Rossi, Satysfakcja i optymalizacja ograniczeń , JACM 44 (2), 1997, 201–236. doi: 10.1145 / 256303.256306

Obecny przypływ teoretycznej analizy semierycznego modelu agregacji danych rozpoczął się w 2007 r. W kontekście pochodzenia . Pochodzenie to fantazyjny termin na adnotowanie danych. Ponieważ każdą krotkę bazy danych można postrzegać jako adnotacje zastosowane do jakiegoś unikalnego identyfikatora krotki, agregację danych można postrzegać jako zwykłą kombinację adnotacji. Proweniencja jest zatem uogólnieniem idei agregowania danych i wyraźnie argumentowano, że właściwy model teoretyczny łączenia adnotacji jest na pół wieku. Najogólniejszy semiring, czyli wielomiany proweniencji, pozwala śledzić całą historię tego, w jaki sposób kawałek danych uzyskano z części składowych. Na przykład wartość pw analizie badania klinicznego może śledzić, w jaki sposób został on obliczony na podstawie poszczególnych wyników badania. Jeśli niektóre z nich okażą się błędne (lub fałszywe), można po prostu przeliczyć bez złych danych.

• Todd J. Green, Grigoris Karvounarakis i Val Tannen, Semirings Provenance , PODS 2007, 31–40. doi: 10.1145 / 1265530.1265535

Było wiele dalszych prac przy użyciu semirings do agregowania danych, patrz cytowane artykuły .

Z bardziej bezpośrednio praktycznej perspektywy, którą przytaczasz, zobacz na przykład strukturę GDL, w jaki sposób można skutecznie zrównoleglić obliczenia, odpowiednio pogrupowując leżące u podstaw wyrażenie semiring.

• Srinivas M. Aji i Robert J. McEliece, Uogólnione prawo dystrybucyjne , IEEE Transactions on Information Theory 46 (2), 2000, 325–343. doi: 10.1109 / 18.825794