<p>You ask why database aggregations have monoidal structure.</p>

<p>Say we want to combine data values <span class="math-container">$a$</span> and <span class="math-container">$b$</span>, 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 <span class="math-container">$a$</span> and <span class="math-container">$b$</span> by <span class="math-container">$a.b$</span>.</p>

<p>The operation <span class="math-container">$.$</span> is usually associative, since we don't want the order in which it is applied to affect the result: we want <span class="math-container">$(a.b).c = a.(b.c)$</span>.  So we have a <a href="https://en.wikipedia.org/wiki/Semigroup" rel="nofollow noreferrer">semigroup</a>.</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Monoid" rel="nofollow noreferrer">monoid</a>.</p>

<p>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.</p>

<p>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.</p>

<p>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 <span class="math-container">$+$</span> (which may be the same as <span class="math-container">$.$</span>), and which should be compatible with <span class="math-container">$.$</span> in the way they interact.  So some kind of distributivity is needed.  Commutativity of <span class="math-container">$+$</span> and sometimes also of <span class="math-container">$.$</span> is also often natural.  We then have a <a href="https://en.wikipedia.org/wiki/Semiring" rel="nofollow noreferrer">semiring</a> or a commutative semiring.  Again inverses are usually too much to hope for, so semirings are a better fit than rings.</p>

<p>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.</p>

<ul>
<li>Stefano Bistarelli, Ugo Montanari, and Francesca Rossi,
<em>Semiring-based constraint satisfaction and optimization</em>,
JACM
<strong>44</strong>(2),
1997,
201–236.
doi:<a href="http://dx.doi.org/10.1145/256303.256306" rel="nofollow noreferrer">10.1145/256303.256306</a></li>
</ul>

<p>The current spurt of theoretical analysis of the semiring model of data aggregation was kick-started in 2007, in the context of <em>provenance</em>.  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 <a href="https://en.wikipedia.org/wiki/P-value" rel="nofollow noreferrer">p-value</a> 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.</p>

<ul>
<li>Todd J. Green, Grigoris Karvounarakis, and Val Tannen, <em>Provenance semirings</em>, PODS 2007, 31–40.
doi:<a href="http://dx.doi.org/10.1145/1265530.1265535" rel="nofollow noreferrer">10.1145/1265530.1265535</a></li>
</ul>

<p>There has been a lot of further work using semirings to aggregate data, see the <a href="http://scholar.google.com/scholar?cites=3053659234252222861" rel="nofollow noreferrer">papers citing this one</a>.</p>

<p>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.</p>

<ul>
<li>Srinivas M. Aji and Robert J. McEliece,
<em>The generalized distributive law</em>,
IEEE Transactions on Information Theory
<strong>46</strong>(2),
2000,
325–343.
doi:<a href="http://dx.doi.org/10.1109/18.825794" rel="nofollow noreferrer">10.1109/18.825794</a></li>
</ul>

CC BY-SA 4.0
2013-02-14T16:58:09.803Z
2018-10-09T20:47:59.633Z
2018-10-09T20:47:59.633Z
András Salamon
<p>On <a href="https://cs.stackexchange.com/questions/9648/what-use-are-groups-monoids-and-rings-in-database-computations">cs.stackexchange</a> I asked about the <a href="https://github.com/twitter/algebird" rel="nofollow noreferrer">algebird</a> scala library on github, speculating on why they might need an abstract algebra package.</p>

<p>The github page has some clues:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>and in another part of the GitHub page:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>Even Oskar Boykin of Twitter chimed in:</p>

<blockquote>
  <p>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).</p>
  
  <p>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).</p>
  
  <p>By using Rings, we can do matrix multiplication over things other than
  numbers (which on occasion we have done).</p>
  
  <p>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).</p>
  
  <p>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...</p>
</blockquote>

<p><strong>How are <code>Bloom filters</code> / <code>hyperloglog</code> / <code>countminsketch</code> like numbers?</strong></p>

<p><strong>How is it that database aggregations have a monoidal structure?<br>
What does this monoid look like?  Do they ever have group structure?</strong></p>

<p>Literature references would be helpful.</p>

CC BY-SA 3.0
2013-02-14T17:29:43.027Z
also can someone sketch out the connection "sparse matrices where almost all values are zero in a monoid"?
vzn
CC BY-SA 3.0
2013-02-14T17:52:40.417Z
@vzn. 0 is the identity. This saves you the trouble from having to compute anything whenever some element $e$ and 0 show up together ($e \cdot 0 = e$). If your matrices are sparse, this means you can get a speedup since you can just "skip" much of the computation.
Nicholas Mancuso
CC BY-SA 3.0
2013-02-14T18:00:53.177Z
@nicholas in other words sparse matrices that can be represented as monoids? (which is not all matrices...) from wikipedia [monoid def](http://en.wikipedia.org/wiki/Monoid), apparently monoids in the form: "The set of all $n \times n$ matrices over a given ring, with matrix addition or matrix multiplication as the operation."
vzn
CC BY-SA 3.0
2013-02-14T18:22:09.223Z
@vzn, no the elements inside the matrix.
Nicholas Mancuso
<soft-question><machine-learning><linear-algebra><db.databases>
How do database aggregations form a monoid?
john mangual
# How do database aggregations form a monoid?

(Asked by: username_0 on 2013-02-12)

On [cs.stackexchange](https://cs.stackexchange.com/questions/9648/what-use-are-groups-monoids-and-rings-in-database-computations) I asked about the [algebird](https://github.com/twitter/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.

**Tags:** soft-question, machine-learning, linear-algebra, db.databases

> **Comments:**
> **username_1**: also can someone sketch out the connection "sparse matrices where almost all values are zero in a monoid"?  
> **username_2**: @username_1. 0 is the identity. This saves you the trouble from having to compute anything whenever some element $e$ and 0 show up together ($e \cdot 0 = e$). If your matrices are sparse, this means you can get a speedup since you can just "skip" much of the computation.  
> **username_1**: @nicholas in other words sparse matrices that can be represented as monoids? (which is not all matrices...) from wikipedia [monoid def](http://en.wikipedia.org/wiki/Monoid), apparently monoids in the form: "The set of all $n \times n$ matrices over a given ring, with matrix addition or matrix multiplication as the operation."  
> **username_2**: @username_1, no the elements inside the matrix.  

---

## 1 answers

### Answer by username_3 on 2013-02-14. Score: 14 | Accepted answer

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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](https://en.wikipedia.org/wiki/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](http://dx.doi.org/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](https://en.wikipedia.org/wiki/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](http://dx.doi.org/10.1145/1265530.1265535)

There has been a lot of further work using semirings to aggregate data, see the [papers citing this one](http://scholar.google.com/scholar?cites=3053659234252222861).

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](http://dx.doi.org/10.1109/18.825794)


---

