Re: Relational lattice completeness
Date: 10 Apr 2006 08:05:35 -0700
Message-ID: <1144681535.134838.71730_at_z34g2000cwc.googlegroups.com>
Jan Hidders wrote:
[...]
> > > Having a full and simple axiomatization makes it possible to write
> > > query optimizers that do a more thorough search of the "optimization
> > > space", and if you know you are complete then you are sure that you
> > > need not look further for any other rules.
> >
> > If you have a bunch of axioms/derivation rules, you can transform an
> > expression to your heart content regardless of whether the theory is
> > complete or not.
>
> But you are not sure that you can find all possible query evaluation
> plans, so you migh miss an optimization opportunity.
The set of transformation rules ('algebraic identities') defines the optimization space also called 'algebraic space' which is enormous in a general case even with reltive simple queries. None of the existing relational database optimizers traverses the entire algebraic space because of the combinatorial explosion and therefore none is capable of producing an otimal query, only a good enough one. Various heuristics are used in order to prune the algebraic space and manual query rewriting and tuning is a fact of life.
In light of the above, the axiom completenes issue is really a
non-issue.
>
> -- Jan Hidders
Received on Mon Apr 10 2006 - 17:05:35 CEST