Path: news.easynews.com!newsfeed1.easynews.com!easynews.com!easynews!newsfeed-east.nntpserver.com!newsfeed-west.nntpserver.com!hub1.meganetnews.com!nntpserver.com!headwall.stanford.edu!newsfeed.stanford.edu!postnews1.google.com!not-for-mail
From: jan.hidders@pandora.be (Jan Hidders)
Newsgroups: comp.databases.theory
Subject: 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
Organization: http://groups.google.com/
Lines: 44
Message-ID: <3c8cab4c.0302141106.19a6c527@posting.google.com>
References: <3E4B8137.2080204@atbusiness.com> <3e4b9af8.0@news.ruca.ua.ac.be> <3E4B9D4E.3070703@atbusiness.com> <3e4bca2b.0@news.ruca.ua.ac.be> <3E4BD7B1.3030900@atbusiness.com>
NNTP-Posting-Host: 213.224.83.150
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-Trace: posting.google.com 1045249589 16425 127.0.0.1 (14 Feb 2003 19:06:29 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: 14 Feb 2003 19:06:29 GMT
Xref: newsfeed1.easynews.com comp.databases.theory:24784
X-Received-Date: Fri, 14 Feb 2003 12:06:28 MST (news.easynews.com)
Lauri Pietarinen wrote in message news:<3E4BD7B1.3030900@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:
>
>
> 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