Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: William Hughes <wpihughes_at_hotmail.com>
Date: 18 Sep 2006 21:21:43 -0700
Message-ID: <1158639703.825366.78740@m7g2000cwm.googlegroups.com>

Chris Smith wrote:
> 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?

No. Very nice. (I started with h(a,{a}) which leads to a similar but not quite final result)

                                 -William Hughes

Received on Mon Sep 18 2006 - 23:21:43 CDT