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

From: Jan Hidders <jan.hidders_at_REMOVE.THIS.ua.ac.be>
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

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

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

>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
Received on Mon Feb 24 2003 - 22:31:16 CET

Original text of this message