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

From: Chris Smith <cdsmith_at_twu.net>
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.

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 Smith
```
Received on Thu Sep 21 2006 - 18:52:04 CEST

Original text of this message