# Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: <pamelafluente_at_libero.it>
Date: 21 Sep 2006 09:09:15 -0700

Chris Smith ha scritto:

> <pamelafluente_at_libero.it> wrote:
> > for an idempotent / assoc / comm function we have
> >
> > f( 4 3 3 3 3) = f( 4 f(3 3 3 3) ) = f(4 3)
> >
> > but adding another 4 and using the above result
> >
> > f( 4 4 3 3 3 3) = f( 4 f( 4 3 3 3 3) ) = f ( 4 f(4 3) )
> >
> > In general, f(4 3) and f ( 4 f(4 3) ) can be different.
> >
> > For a duplication insensitive function this cannot happen.
> >
> > Therefore I meant
> >
> > f( 4 3 3 3 3) = f( 4 4 3 3 3 3) holds for duplication insensitive
> > f( 4 3 3 3 3) = f( 4 4 3 3 3 3) may not hold for idempotence
> >
> > Therefore
> >
> > duplication insensitivity does not imply idempotent (n>3)
> >
> > Make sense?
>
> No. There is an additional requirement that the aggregate function be
> well-defined. We are not considering binary functions that do not yield
> well-defined aggregate functions. If f(4 f(4 3)) is not equal to f(4
> 3), then the aggregate function is not well-defined.
>
> (It turns out that, for your definition, being associative and
> commutative *is* a necessary and sufficient condition for the aggregate
> function being well-defined. So the fact that f(4 f(4 3)) must be equal
> to f(4 3) for the aggregate function to be well defined manifests itself
> in that if the function is associative and commutative *and* idempotent,
> then f(4 f(4 3)) = f(f(4 4) 3) [associative property] = f(4 3) [due to
> idempotence].)

Ok. Very good!

At last we should be writing an article on this stuff :)

>
> See elsethread for the proofs. If I have time, I'll write them for a
> consistent notation and set of definitions.
>
> --
> Chris Smith
Received on Thu Sep 21 2006 - 18:09:15 CEST

Original text of this message