Re: In an RDBMS, what does "Data" mean?

From: Todd B <toddkennethbenson_at_yahoo.com>
Date: 23 May 2004 15:22:43 -0700
Message-ID: <ef8e4d1e.0405231422.11fef65e_at_posting.google.com>


Paul <paul_at_test.com> wrote in message news:<1tsrc.7160$NK4.722786_at_stones.force9.net>...
> Todd B wrote:
> > In a way, however, Godel's theorem is pertinent because it touches on
> > the fact that a database, no matter what its design is or underlaying
> > structure is, will 'definitely' not be able to answer every question
> > we want to ask it.
>
> Are you certain this is true?
>
> As I understand it:
> 1) Godel's Incompleteness theorem only applies to system that are
> powerful enough to model arithmetic.
> 2) It's impossible to model arithmetic using only first-order logic.
> 3) Relational theory (which basically *is* first-order logic) is
> actually both complete and consistent.

To be honest, I don't know. I'll do some reading and certainly revisit this topic in this group (regardless of whether it bothers the other readers or not) after some good research.

> Also, does it actually matter? Because for example suppose I'm right and
> relational theory is complete, there are still questions like the
> transitive closure which can't be answered. That's because these
> questions can't even be written down in first order logic so they are
> meaningless within the system (so the system is still complete). But
> they are meaningful in a "real-world" sense, because we are thinking in
> a larger system which includes second-order logic.

Good point.

> I suppose at least we would know that in theory, every query that it is
> possible to formulate in some given relational query language can be
> answered.

Can you give me an example of where there is proof of first order logic being complete? Keep in mind I'm sticking to the definition of complete as 'things that we prove true within the system are also true in the reality which we use the system to describe'. Is first order logic 'consistent'? Well, of course it is; it's kind of a requirement. Is it 'complete', though? I don't think so, but please prove me wrong or point me to some articles that do.

So, in summary, this last thing you say about every query being answerable is, IMO, 'incompletely' untrue :)

Perhaps there is a query that one could conjure in their head, but would be impossible to write down absolutely? I hate to do this, but I'm going to drop back into a classic example of unproveability because I'm lazy. Prove to me, without brute force methods, that the number 2481997 is prime. (Don't try, because it's not). The point is, for me anyway, is that - okay maybe from a more optimistic perspective - we have the ability to come up with questions, that any logic system will fall short in answering.

Todd Received on Mon May 24 2004 - 00:22:43 CEST

Original text of this message