Re: Date's First Great Blunder

Neo wrote:

>> What sort of problem are you talking about where RDM becomes
>> impractical?

I think this requires second-order predicate logic to state the question. Standard Relational Database theory only deals with first-order logic.

So you could say a deficiency of the relational model is that it can't handle questions that can only be expressed in higher order logics.

You can add operators for specific situations, for example "transitive closure". Or add some kind of induction or recursion to the standard theory. But I'm not sure if there is a rigorous way to cover all possible higher-order queries.

I found this on sci.logic:

"First-order logic cannot express notions such as "connectedness" (or, for example, the notion of the transitive closure of a relation) _by itself_. But there are well-known first-order theories (such as ZFC) in which everything we know about connectedness can be expressed. The determined advocate of the proposition that "FOL = logic" will have no trouble at all talking about connectedness; but connectedness will not be a logical notion for him (but, for example, a set-theoretical notion)."

See also the thread on this newsgroup from 2002 titled: "Expressibility question".

And an interesting exchange here:
http://www-ksl.stanford.edu/email-archives/srkb.messages/331.html "The problem, in practice, is mathematical induction. Many truths can only be proved if we have some form of induction principle. Induction principles are naturally second order. First order induction schemes are HARDER to compute with than higher order principles invoked with higher order matching and unification. Higher order unification may be bad, but wait till you try to use a first order induction scheme!"

I'm not sure but I think the "recursive" additions to standard relational database theory you get with some DBMSs are using a first order induction scheme.

See here for a nice description of second order logic: http://en.wikipedia.org/wiki/Second-order_logic

In particular:
"Second-order logic lacks soundness and completeness theorems"

Which is why it isn't used for relational theory perhaps?

Paul. Received on Wed Apr 21 2004 - 13:14:12 CEST