Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: Chris Smith <>
Date: Thu, 21 Sep 2006 10:52:04 -0600
Message-ID: <>

<> 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.)

The only remaining open question that I'm aware of is how to characterize the set of binary functions that yield well-defined aggregate functions under the second definition. I don't know the answer to that.

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

Original text of this message