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

x wrote:
> Prolog is based on first order logic. What is the difference between
> the Prolog way and the Relational Model way of representing data ?

Hmm according to one website: "The difference between Prolog and a Relational DBMS is that in Prolog the relations are stored in main memory along with the program whereas in a Relational DBMS the relations are stored in files and the program extracts the information from the files." So from this it would seem that logically they are the same.

>> Or upwards to higher-order logic, although I don't know if 
>> incompleteness becomes an issue then. Maybe because we are always 
>> dealing with unbounded but finite systems it doesn't apply or
>> something. I think if you go this route you end up with things like
>> Datalog or Prolog.

OK, I'm not that familiar with Prolog.
But I see a few references to second-order logic in Prolog:

From: http://www.biocheminfo.org/moirai/cs_magenta/prolog.html "Prolog implements a subset of second-order logic (that is, it can deal with sets as well as atomic propositions)"

Also here: http://cs.wwc.edu/~aabyan/LABS/LogicProgramming/2ndorder.html "Pure Prolog is an attempt to implement first-order logic. Only the arguments of predicates may be quantified. Second-order logic permits quantification of predicates." Then it goes on to show some examples of second-order predicates that are in (impure?) Prolog.

http://www.cs.mu.oz.au/~lee/papers/ho/
"This is yet another paper which tells logic programmers what functional programmers have known and practiced for a long time: "higher order" programming is the way to go. How is this paper different from some of the others? First, we point out that call/N is not the way to go, despite its recent popularity as the primitive to use for higher order logic programming. Second, we use standard Prolog rather than a new language. Third, we compare higher order programming with the skeletons and techniques approach."

> And first order logic is "incomplete" also because of the
 > "in all models" stuff.

I don't really understand what your problem is with this.

Here's another statement of Godel's Completeness Theorem: "If T is a set of axioms in a first-order language, and a statement p holds for any structure M satisfying T, then p can be formally deduced from T in some appropriately defined fashion."

They're using the word "structure" for "model" but the same concept. Now surely this is just what you'd intuitively expect?

For example consider our theory T is group theory. One structure that satisfies the group theory axioms is that of abelian (commutative) groups. In this structure every element commutes with every other element. But this is not the case for the general theory of groups. For something to be a universal property of groups, it must be true for *every* possible structure that satisfies the group axioms. And the theorem says that then you can *always* prove the property in the theory T alone (i.e. without reference to any of the structures based on the theory T).

I'm acutally wondering as well whether all this talk of Godel is irrelevant anyway because in databases we are only dealing with finite sets of axioms. Possibly second order logic is complete when you have a finite number of axioms? I'll have to do a bit more Googling.

Paul. Received on Wed Jun 02 2004 - 01:57:57 CEST