Re: Relational lattice completeness

From: Jan Hidders <hidders_at_gmail.com>
Date: 10 Apr 2006 01:16:19 -0700
Message-ID: <1144656979.003330.186900@g10g2000cwb.googlegroups.com>

vc wrote:
> Jan Hidders wrote:
> > vc wrote:
> > > Jan Hidders wrote:
> > > > vc wrote:
> > > > >
> > > > > What's confusing, to me at least, is that in another thread you said
> > > > > that the question was about complete theories, that is about
> > > > > completeness in the context of the first incompleteness theorem.
> > > >
> > > > It is. Because we talking about a system where we have a semantical
> > > > notion of truth for algebraic identities and a syntactical one
> > > > (derivation from the set of given algebraic identies by applying them
> > > > to each other) and the question is if these two are the same.
> > >
> > > They would be the same for a complete (in the sense of the first
> > > incompletenes theorem) system so finding out whether this is the case
> > > would amount to showing if the system in question is complete or not.
> >
> > Not necessarily because the syntactical notion of truth is not the
> > usual one. It's related but not the same.

>

> I let it slip the first time because I thought you'd used the
> expression metaphorically, but now I am curious as to what exactly you
> meant. The 1st incompleteness theorem talks about provability, not
> truth. The notion of truth is not used in either the formulation or
> proof.

It also doesn't mention completeness, so I thought you meant the notion of completeness that it is usually assumed to say something about. But this is all detracting form the main point. I gave an exact and, I think, very simple definition in:

http://groups.google.be/group/comp.databases.theory/msg/a1c140fbe76681e8?hl=en&

What did you not understand about it?

> Let's assume that by 'syntactical notion of truth; you've meant in fact
> derivation. If so, what did you mean by " because the syntactical
> notion of truth is not the usual one. It's related but not the same" ?

We have different derivation rules.

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

• Jan Hidders

Received on Mon Apr 10 2006 - 03:16:19 CDT