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

From: Jan Hidders <>
Date: 14 Feb 2003 11:06:28 -0800
Message-ID: <>

Lauri Pietarinen <> wrote in message news:<>...
> >
> >>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?


> 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
> 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
Received on Fri Feb 14 2003 - 20:06:28 CET

Original text of this message