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