Is there any math foundation for map/reduce?

For a while I was thinking that you just need a map to a monoid, and then reduce would do reduction according to monoid's multiplication.

First, this is not exactly how monoids work, and second, this is not exactly how map/reduce works in practice.

Namely, take the ubiquitous "count" example. If there's nothing to count, any map/reduce engine will return an empty dataset, not a neutral element. Bummer.

Besides, in a monoid, an operation is defined for two elements. We can easily extend it to finite sequences, or, due to associativity, to finite ordered sets. But there's no way to extend it to arbitrary "collections" unless we actually have a sigma-algebra.

So, what's the theory? I tried to figure it out, but I could not; and I tried to go google it but found nothing.

-
What do you mean by map/reduce? – Benjamin Steinberg Dec 17 '11 at 23:02
Asking on the stackexchange CS site will work much better than here, where you'll have to explain whatmap/reduce is :) – Mariano Suárez-Alvarez Dec 17 '11 at 23:18
Even though I have heard of map/reduce several times and even seen some examples, I'd like to see the closest thing the OP knows to a definition of map/reduce. Certainly it won't be an exact definition, since this is what the OP is searching for, but at least it will probably be more formal and less handwaving than what I know about it. – darij grinberg Dec 17 '11 at 23:24
Lookup monad instead of monoid. – François G. Dorais Dec 18 '11 at 0:11
(reduction need not be associative though...) – Mariano Suárez-Alvarez Dec 18 '11 at 0:15