Re: bags vs. sets

x \/ x = x

Does asserting something more than once make it any more true?

"Marshall" <marshall.spight_at_gmail.com> wrote in message news:1179264037.020520.50770_at_p77g2000hsh.googlegroups.com...
> We regularly deride SQL for using bags rather than sets.
> Now, I get many of the reasons we point and laugh at SQL,
> but I'm not so clear on this one.
>
> We could have a language that covered sets, bags, and lists.
> We could have a language that used bags as the basic
> collection type and built lists and relations out of that.
> It's not hard: a relation is a bag with a uniqueness constraint.
> A list is a bag with a uniqueness constraint on a column
> that belongs to the natural numbers. (Details glossed over.)
>
> OTOH, I'm less clear how to model a bag with relations.
>

I always thought that a bag was a set of ordered pairs,

(x, n) or {{x}, {x, n}}.

Doesn't that mean that a bag already *is* a relation?

But I think what you're talking about is not so much generalized collection of values, but rather a more specific collection of tuples. Isn't a relation a set of ordered n-tuples? For example,

(x, y, z) or {{x}, {x, {{y}, {y, z}}}}

So, wouldn't this work to model a bag of tuples?

(x, y, z, n) or {{x}, {x, {{y}, {y, {{z}, {z, n}}}}}

> Bags also show up in things like aggregation. The
> sum of a column of a relation is the fold of + over
> the bag-projection over that column.

The bag projection over a column a is the set,

{(x, n) | for each x in r(a) n = |{t | for each t in r t.a = x }|}

and the aggregate sum is the fold of + over the *set* of products x * n.

Or am I all wet?

>
> Vadim has pointed out that there is a clear progression
> in algebraic properties from set -> bag -> list. But in
> set -> bag, you only give up idempotence. Is that a
> big deal?
>
> I'm not disagreeing necessarily, but I'm not as clear
> on the advantages of sets over bags as I thought I
> was. I have some ideas, but I'd really like to hear
> what y'all have to say.
>
> Discussion welcome.
>
>
> Marshall
>
Received on Wed May 16 2007 - 08:38:34 CEST