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

From: Paul <paul_at_test.com>
Date: Mon, 24 May 2004 19:02:57 +0100
Message-ID: <ENqsc.6849$wI4.807629_at_wards.force9.net>


Bill H wrote:
> Does this pass the "reasonableness" test? The thought that: ...there are
> questions that can't be answered so they're meaningless and, thus, ignored
> (so the system is still complete) doesn't say much for consistency (i.e.
> anything that shows inconsistency is ignored so we still have consistency).

The point is that these questions can't even be *asked* in the system.

The system can still be internally complete and consistent though.

To talk about statements in a language we always need a meta-language. It can be that questions can be posed in the meta-language that can't in the language itself.

Suppose you have a "theory", e.g. field theory, with its various axioms. Then you can have various "models" that are kind of examples of this theory, for example the real numbers, complex numbers, etc.

Now what the Completeness Theorem says is that is something is true in every model of a given theory, it will be possible to prove it in the theory itself (using first order logic). So in other words if you start from your axioms and apply first order logic to them, it's possible for you to extract every possible true statement of your theory.

So I guess the applicability of databases here is that your relations are the axioms of your "theory". Your real-world interpretations of those relations are your "models" of the theory. And the Completeness Theorem assures you that everything you expect to be true in the real world will in fact be provable by the DBMS.

For example suppose I have a database containing the tuple: (1, 2, 'blue')

There could be many interpretations of what this means: for example "customer #1 bought 2 blue widgets"
"on day 1 of the study we saw 2 blue cars"

But in any of these models if I look for distinct values of the third argument of my predicate (i.e. project on the "third" column) I expect to get the answer ('blue').

So my query language (which is really just first order logic) is guaranteed to give the right answer when I do: "SELECT DISTINCT colour FROM r"

And this same argument holds even for more complicated queries.

The interesting thing is that if you go up into second-order logic, there is no corresponding completeness theorem. So you may either have things that are true in all interpretations of a theory but you can't prove them in the theory itself, or you'd have things you can prove in the theory but which aren't true in some model of the theory.

So maybe Codd was wise to stick with first-order logic!

Paul. Received on Mon May 24 2004 - 20:02:57 CEST

Original text of this message