bags vs. sets
Date: 15 May 2007 14:20:37 -0700
Message-ID: <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.
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 - 23:20:37 CEST