Re: bags vs. sets

Marshall wrote:

> 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.

A bag depends on physical location for identifying elements. Because elements in relations have no particular physical location, the very idea seems a little absurd.

Relations are ideal for creating physical independence, while bags are ideal for requiring physical dependence.

> 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.

At the internal physical level, physical location is perfectly acceptable for identifying elements. It's just not such a good thing at the external logical level.

> 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.

Internally, dbmses have to deal with streams and blocks and arrays and all sorts of physical structures. I don't see what the problem is. As long as the dbms manages the physical aspects without burdening the user, what's the problem? Received on Wed May 16 2007 - 00:38:17 CEST