Re: Idempotence and "Replication Insensitivity" are equivalent ?

Well,

Now that we've got this far, I have to go back and change the problem. I said that my definition probably contained errors, didn't I? I found a real source to replace my guesswork. I'll translate as much as possible into the variable names and notation I was using, to try to reuse as much as possible.

Same notation: M(A) is the set of all FINITE multisets with members from A. (I think we were already assuming M(A) is finite; otherwise, of course, the aggregate function is undefined.) 0 is the empty multiset.

A primitive aggregate function x = f(P) is defined by an ordered pair
(g, x_0); g: A^2 -> A, and x_0 in A; via h as follows.

h: A x M(A) -> A

    h(a,0) = a
    h(a,P) = h(g(a,b),P-{b}) ; b in P, and |P| > 0

f: M(A) -> A

    f(P) = h(x_0, P)

An aggregate function is any function M(A) -> A that can be defined in terms of the values of some finite set of primitive aggregate functions on its argument, without directly accessing the members of its argument. For example, AVG is an aggregate function because it is defined by SUM(P) / COUNT(P), where SUM and COUNT can be defined as primitive aggregate functions... but there is no function g that generates AVG directly.

(In case it's not obvious,

    SUM: g(a,b) = a+b       x_0 = 0
  COUNT: g(a,b) = a+1       x_0 = 0  )

What does this do to the relationship between idempotence of g and replication-insensitivity of an aggregate function f? I really don't know, except that in the special case where f is a primitive aggregate function and x_0 is the identity of g (obviously assuming g has an identity), then the statements are still equivalent because this becomes a special case of my last definition.

It's late. I'll think more about this tomorrow.

-- 
Chris Smith