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_at_m7g2000cwm.googlegroups.com>
> 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.
> > 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?
Date: 18 Sep 2006 21:21:43 -0700
Message-ID: <1158639703.825366.78740_at_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 Tue Sep 19 2006 - 06:21:43 CEST