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

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

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

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
• I don't find it true that all optimizations available for set algebras are available for bag algebra. There are semantic constraints to keep the operation on bags operation on bags and not operations on sets. SQL optimizers, for example, are constrained to keep track of the number of rows by some very uninteresting (and irrelevant to end users, me thinks) rules.

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. Maybe we should consider that in their position they have to teach students that will be hired in the DBMS industry.

I guess, what I want to say that quite a few conjectures flew around in this discussion, but is there some theoretical substance to such conjectures? Can you provide some references.

best regards,
Costin Cozianu Received on Mon Feb 17 2003 - 18:53:53 CET