# Re: Idempotence and "Replication Insensitivity" are equivalent ?

Date: Thu, 21 Sep 2006 10:52:04 -0600

Message-ID: <MPG.1f7c711f4bc1293898972b_at_news.altopia.net>

<pamelafluente_at_libero.it> wrote:

> We still have a good argument for the case associ/comm are

*> missing.
*

I don't know what you mean. You proposed a definition for aggregate functions that's basically equivalent to my first definition. Specifically you said (I'm changing your aggregate to ff, since there are two different functions here and you called them the same thing):

ff: M(A) -> A, f: A^2 -> A

ff({|a,b,...,z|}) = f(a,f(b,...f(y,z)...)

In that case, if the binary function is not associative and commutative, then the aggregate function doesn't exist. It is not well-defined. There is nothing else interesting to say about it.

There was another definition, which is essentially

ff: M(A) -> B, f: A x B -> B

ff({|a,b,...,z|}) = f(a,f(b,...f(y,f(z,initial)...)

where initial is some arbitrary value. With that definition, the set of functions definable as aggregates becomes equivalent to the entire set of functions on multisets (though some can be defined "better" than others), and it becomes possible to find some non-associative and noncommutative binary functions that nevertheless yield well-defined aggregate functions. In that case, the equivalence of binary idempotence for f and duplication insensitivity for ff is not true in general (though it is true for the special case where A = B and initial is an identity for f.)

-- Chris SmithReceived on Thu Sep 21 2006 - 18:52:04 CEST