Bagaimana agregasi basis data membentuk monoid?

Pada cs.stackexchange saya bertanya tentang perpustakaan scala algebird di github, berspekulasi tentang mengapa mereka mungkin membutuhkan paket aljabar abstrak.

Halaman github memiliki beberapa petunjuk:

Implementasi Monoids untuk algoritme aproksimasi yang menarik, seperti filter Bloom, HyperLogLog, dan CountMinSketch. Ini memungkinkan Anda untuk memikirkan operasi canggih ini seperti jumlah Anda, dan menambahkannya dalam hadoop atau online untuk menghasilkan statistik dan analitik yang kuat.

dan di bagian lain dari halaman GitHub:

Awalnya dikembangkan sebagai bagian dari Matrix API Scalding, di mana Matriks memiliki nilai yang merupakan elemen Monoids, Grup, atau Cincin. Selanjutnya, jelas bahwa kode memiliki aplikasi yang lebih luas dalam Scalding dan proyek-proyek lain di Twitter.

Bahkan Oskar Boykin dari Twitter menimpali:

Jawaban utamanya adalah bahwa dengan mengeksploitasi struktur semi-grup, kita dapat membangun sistem yang paralel dengan benar tanpa mengetahui operasi yang mendasarinya (pengguna menjanjikan asosiatif).

Dengan menggunakan Monoids, kita dapat mengambil keuntungan dari sparsity (kita berurusan dengan banyak matriks yang jarang, di mana hampir semua nilai adalah nol di beberapa Monoid).

Dengan menggunakan Rings, kita bisa melakukan perkalian matriks atas hal-hal selain angka (yang kadang-kadang kita lakukan).

Proyek algebird itu sendiri (serta sejarah masalah) dengan cukup jelas menjelaskan apa yang sedang terjadi di sini: kami sedang membangun banyak algoritma untuk agregasi kumpulan data besar, dan meningkatkan struktur operasi memberi kami kemenangan di sisi sistem (yang biasanya merupakan titik sakit ketika mencoba memproduksikan algoritma pada 1000s node).

Selesaikan masalah sistem satu kali untuk Semigroup / Monoid / Group / Ring, dan kemudian Anda dapat menyambungkan algoritma apa pun tanpa harus memikirkan Memcache, Hadoop, Storm, dll ...

Bagaimana Bloom filters/ hyperloglog/ countminsketchseperti angka?

Bagaimana agregasi database memiliki struktur monoid?
Seperti apa bentuk monoid ini? Apakah mereka pernah memiliki struktur kelompok?

Referensi literatur akan sangat membantu.

Anda bertanya mengapa agregasi basis data memiliki struktur monoid.

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

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

Hampir selalu ada semacam identitas, apakah itu angka 0 atau 1, string kosong, matriks identitas, distribusi seragam, atau set kosong, yang tergantung pada operasi. Jadi sebenarnya data biasanya berbentuk monoid .

Poin praktis tentang berpikir data sebagai bentuk monoid adalah bahwa ia menyediakan cara untuk membahas operasi pada berbagai jenis data menggunakan bahasa aljabar umum. Ini kemudian diterjemahkan ke dalam pustaka kode generik yang dapat menangani monoid apa pun, dengan hanya meneruskan operasi agregasi yang sesuai sebagai argumen.

Perhatikan bahwa banyak jenis data tidak memiliki invers, sehingga struktur grup terlalu banyak untuk diharapkan. Jika Anda memiliki struktur grup maka beberapa cara tambahan untuk memanipulasi data menjadi mungkin, tetapi karena tidak ada matriks dengan perkalian, atau bilangan bulat positif dengan penambahan memiliki invers, data non-grup-terstruktur cukup umum.

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

Model semiring agregasi data telah ada di komunitas kepuasan kendala selama beberapa waktu. Perhatikan bahwa turunan masalah kepuasan kendala adalah kueri konjungtif atas database fakta tertentu, jadi ini cukup umum: sebagian besar pertanyaan praktis atas data bersifat konjungtif.

• Stefano Bistarelli, Ugo Montanari, dan Francesca Rossi, kepuasan dan optimalisasi kendala berbasis Semiring, JACM 44 (2), 1997, 201-236. doi: 10.1145 / 256303.256306

Percepatan saat ini dari analisis teoritis model semiring dari agregasi data dimulai pada tahun 2007, dalam konteks asalnya . Provenance adalah istilah mewah untuk membuat anotasi data. Karena setiap basis data tuple dapat dilihat sebagai anotasi yang diterapkan pada beberapa pengidentifikasi tuple unik, agregasi data dapat dilihat hanya sebagai kombinasi anotasi. Karena itu, pembuktian merupakan generalisasi dari gagasan pengumpulan data, dan secara eksplisit telah diperdebatkan bahwa model teoritis yang tepat untuk menggabungkan anotasi adalah semiring. Semiring yang paling umum, dari polinomial asal, sebenarnya memungkinkan seseorang untuk melacak seluruh sejarah tentang bagaimana sepotong data diperoleh dari bagian-bagian penyusunnya. Sebagai contoh, nilai-pdalam analisis uji klinis dapat melacak bagaimana itu dihitung dari masing-masing hasil uji coba individu. Jika beberapa dari mereka ternyata salah (atau palsu) maka seseorang dapat dengan mudah menghitung ulang tanpa data yang buruk.

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

Ada banyak pekerjaan lebih lanjut menggunakan semiring untuk mengumpulkan data, lihat makalah yang mengutip ini .

Dari perspektif yang lebih praktis yang Anda kutip, lihat misalnya kerangka kerja GDL untuk bagaimana seseorang dapat memparalelkan perhitungan secara efektif dengan mengelompokkan ekspresi semiring yang mendasarinya secara tepat.

• Srinivas M. Aji dan Robert J. McEliece, Hukum distributif umum , Transaksi IEEE tentang Teori Informasi 46 (2), 2000, 325-343. doi: 10.1109 / 18.825794