bags vs. sets

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.

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.

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 Tue May 15 2007 - 16:20:37 CDT