# Re: Relational lattice completeness

Date: 10 Apr 2006 01:16:19 -0700

Message-ID: <1144656979.003330.186900_at_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