How do database aggregations form a monoid?

Question

On cs.stackexchange I asked about the algebird scala library on github, speculating on why they might need an abstract algebra package.

The github page has some clues:

Implementations of Monoids for interesting approximation algorithms, such as Bloom filter, HyperLogLog and CountMinSketch. These allow you to think of these sophisticated operations like you might numbers, and add them up in hadoop or online to produce powerful statistics and analytics.

and in another part of the GitHub page:

It was originally developed as part of Scalding's Matrix API, where Matrices had values which are elements of Monoids, Groups, or Rings. Subsequently, it was clear that the code had broader application within Scalding and on other projects within Twitter.

Even Oskar Boykin of Twitter chimed in:

The main answer is that by exploiting semi-group structure, we can build systems that parallelize correctly without knowing the underlying operation (the user is promising associativity).

By using Monoids, we can take advantage of sparsity (we deal with a lot of sparse matrices, where almost all values are a zero in some Monoid).

By using Rings, we can do matrix multiplication over things other than numbers (which on occasion we have done).

The algebird project itself (as well as the issue history) pretty clearly explains what is going on here: we are building a lot of algorithms for aggregation of large data sets, and leveraging the structure of the operations gives us a win on the systems side (which is usually the pain point when trying to productionize algorithms on 1000s of nodes).

Solve the systems problems once for any Semigroup/Monoid/Group/Ring, and then you can plug in any algorithm without having to think about Memcache, Hadoop, Storm, etc...

How are Bloom filters / hyperloglog / countminsketch like numbers?

How is it that database aggregations have a monoidal structure?
What does this monoid look like? Do they ever have group structure?

Literature references would be helpful.

Answer 1

You ask why database aggregations have monoidal structure.

Say we want to combine data values $a$ and $b$, but want to keep things general -- these may be integers, strings, floating point numbers, vectors, matrices, probability distributions, sets, or anything else we want to store and manipulate. So we denote the "aggregation" of $a$ and $b$ by $a.b$.

The operation $.$ is usually associative, since we don't want the order in which it is applied to affect the result: we want $(a.b).c = a.(b.c)$. So we have a semigroup.

Almost always there is some kind of identity, whether it is the number 0 or 1, the empty string, an identity matrix, a uniform distribution, or the empty set, which depends on the operation. So in fact data usually forms a monoid.

The practical point about thinking of data as forming a monoid is that it provides a way to discuss operations on different kinds of data using a common algebraic language. This then translates into generic code libraries that can deal with any monoids, by simply passing an appropriate aggregation operation as an argument.

Note that many kinds of data do not have inverses, so a group structure is too much to hope for. If you have group structure then some additional ways of manipulating the data become possible, but since neither matrices with multiplication, nor the positive integers with addition have inverses, non-group-structured data is quite common.

We don't usually want to just store data, but to run queries over the database. So we need some notion of what to do when a query generates many answers. Often this requires a combining operation $+$ (which may be the same as $.$), and which should be compatible with $.$ in the way they interact. So some kind of distributivity is needed. Commutativity of $+$ and sometimes also of $.$ is also often natural. We then have a semiring or a commutative semiring. Again inverses are usually too much to hope for, so semirings are a better fit than rings.

A semiring model of data aggregation has been around in the constraint satisfaction community for some time. Note that a constraint satisfaction problem instance is a conjunctive query over a particular database of facts, so this is pretty general: most practical queries over data are conjunctive.

• Stefano Bistarelli, Ugo Montanari, and Francesca Rossi, Semiring-based constraint satisfaction and optimization, JACM 44(2), 1997, 201–236. doi:10.1145/256303.256306

The current spurt of theoretical analysis of the semiring model of data aggregation was kick-started in 2007, in the context of provenance. Provenance is a fancy term for annotating data. Since any database tuple can be seen as annotations applied to some unique tuple identifier, aggregation of data can be seen as just combination of annotations. Provenance is therefore a generalization of the idea of aggregating data, and it has explicitly been argued that the right theoretical model of combining annotations is a semiring. The most general semiring, of provenance polynomials, actually allows one to keep track of the entire history of how a piece of data was obtained from constituent parts. As an example, a p-value in the analysis of a clinical trial can keep track of how it was calculated from each of the individual trial results. If some of them turn out to be wrong (or fake) then one can simply recalculate without the bad data.

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

There has been a lot of further work using semirings to aggregate data, see the papers citing this one.

From the more immediately practical perspective that you cite, see for instance the GDL framework for how one can effectively parallelise a computation by grouping the underlying semiring expression appropriately.

• Srinivas M. Aji and Robert J. McEliece, The generalized distributive law, IEEE Transactions on Information Theory 46(2), 2000, 325–343. doi:10.1109/18.825794