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

Alfredo Novoa wrote:

>>>>>There are many reasons that make that theorem irrelevant in the
>>>>>database context.
>>>>
>>>>Such as...?
>>>
>>>It simply shows that we can prove if a relational formula is valid or not.
>>
>>Are you sure? I thought that Godel's completeness theorem is basically 
>>linking syntax with semantics; showing that the two different approaches 
>>to logic will give the same result?

I think the problem is how do we apply this theorem to relational databases. The way I see it, it fits with what I said. :)

When you say "if a relational formula is valid or not" do you mean valid as in well-formed or valid as in true? If you mean true, then maybe we are just saying the same thing in different ways. But I'm seeing the result as profound and you're seeing it as trivial.

I see T as for example:
{ q('Alan',20), q('Bill',20) } where q is a predicate. (syntax)

Then one possible structure M satisfying T is: { 'Alan is 20 years old', 'Bill is 20 years old' } (semantics)

The statement p could be (in terms of T): (forall x) q(x,20)

In terms of M:
p = 'Everyone is aged 20'

Another possible structure M could be:
{ 'Alan is in dept 20', 'Bill is in dept 20' } but whatever structure we choose, the semantics of the statement in M that corresponds to '(forall x) q(x,20)' always has a 'true' value.

Thus I see Godel's completeness theorem as saying we can therefore prove the statement '(forall x) q(x,20)' purely syntactically i.e. without considering semantics at all. The DBMS only knows syntax, not semantics. Thus the DBMS can prove the statement on its own.

Where I can see a problem is that usually when writing a query we are creating a totally new predicate (as opposed to my example which was a true/false statement).

For example:
 From 'Alan is in dept 20' and 'dept 20 is on the second floor' we can use semantics to deduce 'Alan works on the second floor', which is a totally new predicate. I suppose we are implicitly defining a view or new predicate like
r(name,floor) :- p(name,dept) and q(dept,floor) Now it's meaningless to ask whether our new predicate is true or not. But we could ask yes/no questions like 'Is there a person called Alan who works on the second floor?'

What we want to know is whether any question we ask in semantic terms can be answered syntactically. For example the question 'Does Alan like rice pudding?'. We have to know first how (if possible) to translate our question from semantics to syntax. Sometimes (e.g for hierarchies) it won't be possible to do this, even if the semantics make sense. But I think that all first-order questions that can be answered semantically will translate to a syntactic question. Which can definitely be answered (by Godel's completeness theorem?)

Paul. Received on Sat Jun 19 2004 - 10:27:18 CEST