Re: Idempotence and "Replication Insensitivity" are equivalent ?

William Hughes <wpihughes_at_hotmail.com> wrote:
> > - h(a, 0) = a
> > - For any other value of the second argument P, choose an arbitrary
> > member b from P, then
> >
> > h(a, P) = h(g(a, b), P - {b})
> >
> > As a technical detail, h remains undefined when its value depends
> > on the choice of b. In practice, g should be chosen so that this
> > never happens.
> >
>
> Quite a "technical detail". It is very clear that not all functions
> A x M(A) -> A can be characterized as above. How does one find
> g? (note if g exists it is unique).

Most of the time, g is obvious. As examples of aggregate functions, consider SUM or MAX. It's not hard to find g in those cases; g is simply the binary version of the desired function. I don't know if there are cases where g is harder to find, but still possible, for some desirable aggregate function.

> > 5. Let f: M(A) -> A be a function defined as follows. To evaluate f(P),
> > choose an arbitrary member a from P.
> >
> > f(P) = h(b, P - {a})
> >
>
> I think you mean f(P) = h(a, P - {a})

Yes, I do.

> f(P) replication insensitive => g(a,b) idempotent is not obvious to
> me. I think it's true, but I can't see a clean proof.

Let P = {a}. Then f({a}) = h(a,0) = a. At the same time, f({a,a}) = h(a,{a}) = h(g(a,a), 0) = g(a,a). By supposition, f(P) is replication insensitive, so f({a,a}) = f({a}). Therefore g(a,a) = a. So g is idempotent.

Anything wrong there?

> Note that the function CountUnique can be M(A)->A but
> does not have a generator g and is replication insensitive.

Yes. There are a number of useful functions that can't be defined as aggregate functions. This is much to the annoyance of database practitioners.

-- 
Chris Smith