# Re: Extending my question. Was: The relational model and relational algebra - why did SQL become the industry standard?

Date: 24 Feb 2003 22:31:16 +0100

Message-ID: <3e5a8f24.0_at_news.ruca.ua.ac.be>

Costin Cozianu wrote:

*>>
**>> No. In fact, in theory, all optimizations that can be done in a set-based
**>> algebra can also be done in a bag-based algebra but not the other way
**>> around.
**>
**>Hi Jan,
*

Always nice to see a reaction that actually talks about theory. :-)

*>I followed this discussion, interesting as always. But I'm puzzled by this
**>conjecture. Has somebody studied it ?
*

http://citeseer.nj.nec.com/libkin93some.html (on bag algebras) http://citeseer.nj.nec.com/grumbach96query.html (more on bag algebras) http://citeseer.nj.nec.com/181093.html (on pom-sets)

*>Here's my take on it:
**>
**>- I don't see in any useful sense how can bag algebra be a superset of set
**>algebra. The obvious inclusion mapping from sets to bags is not a morphism
**>: Bag(a \/ b) = Bag(a) \/ Bag(b) doesn't hold
*

However, what is relevant in the context of query optimization and for my remarks above is that for every expression in the set-based algebra there is a corresponding expression in most reasonable bag-based algebras, and that is more or less how I would interpret the statement that the set-based algebra is a subset of the bag-based algebra.

*>- Bag on the other hand are a special kind of sets. Aren't you defining
**>bags as a function from a universe of elements to Natural numbers ? But
**>also bag operations are not a straight mapping of corresponding set
**>operation
*

Bags can be defined as a special kind of set, and sets can be seen as a special case of bags. For every set operation it is easy to think of one (or more) corresponding bag operation that is the same up to duplicates.

*>- therefore my suspicion is that neither algebraic structures are
**>isomoprhic to a substructure of the other.
*

*>- it is the rule rather than the exception, that the stringer algebraic
**>properties a structure has , the better suited for optimization it is.
**>Sets have the well known algebraic properties of lattices. Bag algebra
**>is a ... (bag algebra I presume) ? All my algebraic books just don't
**>study the algebra of bags. On the contrary, lattices are widely studied,
**>presumably this situation
*

Try (free) monoids:

http://citeseer.nj.nec.com/fegaras94uniform.html

*>You recurred at some point to a proof by authority (Ullman, Molina vs.
**>Date), but I'm curious if you have a stated opinion of Molina et all
**>vis-a-vis bag algebra being more optimizable than set alegbra, or is it
**>just a conjecture of yours.
*

- Jan Hidders