From: SB
To: Editor
I have been reading Introduction to Database Systems (7th
edition) and The Third Manifesto (2nd edition), in both of which you advocate
relation-valued attributes, and relation-valued components of possible
representations of scalars. At first, I had a hunch that this might be odd.
Then, I had this informal idea:
If the system includes relation-valued attributes, it
includes predicates over sets, and set variables (the Relational Model already
included Relation Variables, which are set variables, in the sense of
Programming Language variables; however, this also introduces set variables in
the sense of Logic variables). The underlying logic, therefore, is no longer
First-Order Predicate Logic. Now, every DBMS is essentially a proof system; If
indeed it is higher order, it is in all probability possible to reconstruct
Goedel's argument within the Relational framework, and thereby prove the
following conjecture:
For every DBMS dbms which embodies the Relational Model as
presented in Introduction to Database Systems (7th edition), there exist a
database db and a query q such that:
- q is a syntactically and semantically valid query for db
- dbms will give the wrong answer for q
By "syntactically and semantically valid" I mean a
query which is syntactically well-formed and has a well-defined answer in the
database (if there is a better definition in one of these books, I must have
missed it or not have reached it, and I apologize).
While pondering this issue further, I came up another idea.
Consider the next fragment of Tutorial D, assuming Type Inheritance and the
scalar "top" type Alpha as discussed in The Third Manifesto:
TYPE SSET POSSREP {SET RELATION {SCALAR ALPHA}};
Intuitively, SSET is a type of sets treated as scalars. Now
assume there is an infix operator IN which tests for the membership of a tuple
in a relation, and define
OPERATOR MEMBER (ELEMENT RELATION{SCALAR ALPHA},CONTAINER
RELATION{SCALAR ALPHA}) RETURNS BOOLEAN
RETURN TUPLE{SCALAR SSET(ELEMENT)} IN CONTAINER;
That is, MEMBER tests whether one set is a member of another.
Now,
TYPE RUSSELL IS SSET
CONSTRAINT NOT MEMBER(SET,SET);
Try as I might, I have not been able to convince myself
whether or not the type RUSSELL indeed embodies Russell's paradox; obviously,
by intention, it is a non-well-defined set, and so should not be a type. But
are types and relations enough of "different kinds" of sets to save
the model from this attack?
I think a similar construction can be made with relations
alone, and no inheritance, replacing the type ALPHA with something along the
lines of
TYPE FAKE_ALPHA POSSREP {
IS_SET BOOLEAN,
S (any scalar type, say,)
INTEGER,
SET RELATION {SCALAR
FAKE_ALPHA},
CONSTRAINT (IS_SET AND S=0) OR ((NOT IS_SET)
AND IS_EMPTY_RELATION(SET))}
Where IS_EMPTY_RELATION has the obvious meaning. It would
take a little more elaboration, but I think I give you enough here to show that
the concept of relations as elements of possible representations of scalars is
problematic; and that similar arguments can be made for relation-valued
attributes (because constraints, obviously, can apply to relations as much as
they apply to types).
Do you see any glaring mistakes on my part (other than,
probably, Tutorial D syntax, and perhaps, lack of formality)? Do you care to
comment?
Chris Date Responds: Many thanks for your questions
(this kind of stuff is fun, isn't it).
What follows is my attempt to answer those questions--but I must
immediately make it clear that I'm not a logician, and my answers might
therefore be completely off base.
Anyway, here goes.
You raise two general questions, one to do with Gödel's
Theorem and one to do with Russell's Paradox.
I'll take them one at a time.
Gödel's Theorem
As I understand it, Gödel's Theorem states that any formal
system F that's at least as powerful as ordinary arithmetic must be
either inconsistent or incomplete.
Assuming for the sake of discussion that arithmetic is consistent, it
follows that the formal system F must be incomplete, meaning it's
possible to find some statement of F that's true but can't be proved
(within F) to be true. And since computer systems in general are formal systems that are at least as powerful as ordinary arithmetic (!), it follows that such systems must be incomplete.* There's no need to invoke the relational model, or DBMSs, or second-order logic, in order for this depressing result to
apply!
* I'm assuming an idealized computer here--it's not my
intent to invoke arguments having to do with the finiteness of real machines.
By the way, I have a small problem with the way you state
your conjecture. You say:
For every DBMS [that] embodies the Relational Model ... there
exist a database db and a query q [on db] such that ...
[the DBMS] will give the wrong answer for q.
Isn't it the case, rather, that the DBMS will give NO
answer for q? In essence, q
is noncomputable--and surely that's exactly what the DBMS should say. (In practice I suppose it's more likely to
time out, or blow up, or go into an infinite loop, or something. Whatever.
Whatever it does, however, it surely mustn't give the WRONG answer.)
Russell's Paradox
As I understand it, Russell's Paradox states that the set X
defined as {x:x e/ X}--i.e., the set of all sets that
aren't members of themselves--is paradoxical, because if it's a member of
itself then it isn't, and conversely if it isn't a member of itself then it
is.
Now, the (or at least one) formal problem with the foregoing
set X is that it's defined in terms of itself. Russell therefore proposed machinery--his theory of
types--according to which sets could be defined only in terms of previously
defined constructs. So the question
becomes: Does THE THIRD MANIFESTO
permit Russell's type machinery to be circumvented? I don't know the answer to this question, but I don't think your
MEMBER example demonstrates any such circumvention. Let's consider that MEMBER operator. It takes two parameters, CONTAINER and ELEMENT, where:
·
CONTAINER is a relation whose tuples contain just one
component: namely, a scalar value (i.e., a value of type alpha).
·
ELEMENT is a relation and thus certainly not a scalar
value (i.e., not a value of type alpha).
·
Hence, there's no way CONTAINER can contain a tuple
whose single component has a value equal to ELEMENT.
·
Hence, there's no way MEMBER (even corrected as below)
can ever return TRUE.
Now let me elaborate on your definition of the MEMBER
operator. In line 3, you have the
expression:
SSET (ELEMENT)
I don't know what you mean by this expression; it's not
syntactically well formed. Here's your
own definition of type SSET:
TYPE SSET POSSREP {SET RELATION{SCALAR alpha}};
Actually I see no need to invoke type SSET in the MEMBER
definition anyway. I think what you
might have meant is the following:
OPERATOR MEMBER
(ELEMENT
RELATION{SCALAR alpha},
CONTAINER
RELATION{SCALARalpha})
RETURNS BOOLEAN;
RETURN (TUPLE {SCALAR
ELEMENT} IN CONTAINER);
END OPERATOR;
However, line 5 here will fail on a type error (ELEMENT is
not of type alpha).
While I'm beating you up on syntax matters, incidentally, I
think your RUSSELL definition should read as follows:
TYPE RUSSELL IS SSET
CONSTRAINT NOT
(MEMBER(THE_SET(SSET),THE_SET(SSET)));
However, this definition is still not valid, because as we've
already seen MEMBER isn't well defined.
As for your FAKE_ALPHA example: Here I observe that, pace Russell, you're defining a type
in terms of itself (loosely speaking; more precisely, you're defining a type
with a possrep that involves itself).
In THE THIRD MANIFESTO, 2nd edition, we said this (page
122):
It is an open question as to whether any scalar type T
can have a declared possible representation that is defined, directly or
indirectly, in terms of T itself.
More precisely, let T be a scalar type. Let S1, S2, ... be a sequence of sets defined as
follows:
S1 = the
set of declared types for all components of all
declared
possible representations for T
Si = the
set of declared types for all components of all
declared
possible representations for all types in S(i-1)
(i
> 1)
Then the question is whether there must exist some value n
(n > 0) such that every type in the set Sn is
system-defined.
I can't pretend to have fully understood all of the
implications of your FAKE_ALPHA example, but it might well constitute evidence
to suggest that a cautious answer to our "open question" had better
be NO.
One last point (and here I'm going back to your question
regarding Gödel's Theorem). You're not
the first person to point out that our embrace of relation-valued
attributes--and maybe relation-valued possrep components, I suppose, though I'm
less sure about that one--means we're getting into the realm of second-order
logic. However, none of our critics in
this regard has ever succeeded in demonstrating to us just what problems are
caused by our straying into that realm!
(And it's not for want of asking on our part, I can assure you.) So:
What exactly are the negative implications here? Can you enlighten us?
Further to the foregoing:
In fact, don't we rely on second-order logic anyway when we require the
equality or identity operator "=" to be defined for every
type? Likewise for all other operators
that we require to be defined for every type?
I'll send you this response right away in the interests of
timeliness. I'd prefer to discuss it with Hugh Darwen first, but unfortunately
our schedules are such that I'm unlikely to be able to do so until Christmas,
possibly not till the New Year. So you
might get a further follow-up response from both of us on these matters in the
fullness of time ... Meanwhile, thanks again for your very interesting
questions.
Posted
2/6/04
