Re: Relational lattice completeness

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

Of course.

> In light of the above, the axiom completenes issue is really a
> non-issue.

That conclusion is far too hasty. If you have a better grasp on what the total optimization-landscape is and looks like you might possibly be able to come up with better heuristics. Moreover, we are looking here at a small subset of the queries that can be expressed with relational algebra, and an algebra that is in some respects more "algebra friendly" so things might be simpeler here. In some sense that is the whole raison d'etre of Vadim's algebra, so such a result would seriously strengthen his case. Until we have actually looked, it is simply too early to tell. Finally, trying to prove completeness is simply a good way of checking if there are no obvious algebraic identities still missing.

• Jan Hidders