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

Date: 14 Feb 2003 11:06:28 -0800

Message-ID: <3c8cab4c.0302141106.19a6c527_at_posting.google.com>

Lauri Pietarinen <lauri.pietarinen_at_atbusiness.com> wrote in message news:<3E4BD7B1.3030900_at_atbusiness.com>...

*> >
*

> >>and better optimisations would be obtained without duplicates"

*> >
**> >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.
**>
**> So you in fact disagree with Date on that one?
*

Well, let's say that in his "war on duplicates" he sometimes IMO tends to oversimplify things.

> Is not optimisation (at least partly) a question of query transformations?

Yes.

> I understand that more transformations are available when we operate with

*> sets that if we operate with bags. Even the excerpt from the book
**> seems to suggest this:
**>
**> <quote>
**> For instance, you may have learned set-theoretic laws such as A
**> INTERSECT (B UNION C) = (A INTERSECT B) UNION (A INTERSECT C), which is
**> formally the "distributive law of intersection over union." This law
**> holds for sets, but not for bags.
**> <quote/>
*

As Paul Vernon correctly remarked a bag algebra will always be a superset of a set algebra in the sense that for all expressions in the set algebra there is an equivalent expression the bag algebra. As a consequence every algebraic rule in the set algebra has a corresponding rule in the bag algebra. For example, for the rule above you would have in the bag algebra (here SET is the unary operation that removes duplicates):

** SET(SET(A) INTERSECT(SET(B UNION C))) =
**
** SET(SET((A) INTERSECT SET(B)) UNION (SET(A) INTERSECT SET(C)))
**
So, although things get a bit more complicated, there is absolutely no
reason why a query optimizer that is based on a bag algebra would
perform worse than one that is based on a set algebra.

- Jan Hidders