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

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,

Hello Costin,

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 ?

No, because it is actually quite trivial. I'll try to explain by answering your questions. There is, by the way, quite some literature on bag algebras, list algebras, and even the more general pom-set (partially ordered multi-set) algebras, although these may not study the questions you have in mind. For examples see:

  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

That depends on how you define the operations in the bag algebra. It is quite possible to define them such that there actually *is* a morphism, for example, by the defining the bag-union such that the element x appears max(a,b) times in the bag union A \/ B if it appears a times in A and b times in B. So it all depends on which bag algebra you are talking about.

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.

They don't have to be. All that is needed is that for every algebraic equality that we had in the set-based algebra there is a corresponding algebraic equality in the bag-based algebra. This is trivially true if for every set operation there is a bag operation (or an expression that simulates it) up to duplicates.

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

I hope you understand now that this "conjecture" is rather trivial to prove once you exactly define what is meant by "subset of" for such algebras.

• Jan Hidders