Re: Idempotence and "Replication Insensitivity" are equivalent ?

From: Jan Hidders <hidders_at_gmail.com>
Date: 22 Sep 2006 08:00:51 -0700
Message-ID: <1158937250.785041.128020@i42g2000cwa.googlegroups.com>

pamelafluente_at_libero.it wrote:

>

> But the real world objection to this is that, sometimes,
> the user ORDERs the record and would like to compute aggregate
> functions that depends on such order. So does not really make sense
> to restrict to ass/comm functions.

Actually, also in that case it does.

Let's say we use the "free monoid" formalism to define aggregates. That means we define our aggregation function over collections with elements of type T1 and resulting in a aggregate of type T2 by giving (E, S, A):

- E ; a value of type T1 for the result of the empty collection
- S : T1 -> T2 ; a function for the result of the singleton collection
- A : T2 x T2 -> T2 ; the aggregation / combination function

such that the function A is associative and E the unit of A.

If the collections are bags (or sets) then we require A also to be commutative (and idempotent).

Now supose we are talking about sets (and require A to be associative, commutative and idempotent), the it is clear that you can still give a triple (E,S,A) such that it computes for example the top 5 of the set according to some ordering.

Figuring out the exact trio is left to the reader as an exercise. :-)

• Jan Hidders

Received on Fri Sep 22 2006 - 10:00:51 CDT