Re: On Formal IS-A definition

From: paul c <>
Date: Thu, 06 May 2010 15:32:17 GMT
Message-ID: <5iBEn.3474$Z6.2362_at_edtnps82>

Erwin wrote:
> Another small point is that there is a school of thought which says
> something about a connection between relation algebra and first order
> logic, thereby excluding transitive closure as a possible operator of
> RA because transitive closure requires recursion and recursion is
> excluded by FOL. I don't really understand their point, or why they
> are trying to make that point, because imo (generalized) transitive
> closure is a sine qua non for "expressive completeness". Without
> transitive closure, certain queries are provably unanswerable, and so
> TC is needed. I find that statement about the link with FOL rather
> vacuous for that reason.

Personally, I'd call such a 'connection' beside the point. I would have thought that given enough variable names, FOL can recurse. That might be impractical so if my attitude is on the point, such a 'school' is really talking about implementation. Even apart from transitive closure, I'd have thought that any query involving a relation with more than one tuple effectively involves recursion as far as implementation is concerned.

When looking at one of Codd's "R-tables", schoolchildren of all ages can usually identify all the transitive/derived relations even if they can't visualize the mechanization needed. I'd say this is a patent reason to put paid on the Information Principle as far as transitive closure is concerned.

Regarding another aspect of the Information Principle, I'd like to ask whether an SuppliersParts relation such as:

S# P#
S1 P1
S1 P2
S2 P3

has the same information as one with a domain PS# that is a set of part numbers:

S# PS#
S1 {P1,P2}
S2 {P3}

If they have the same information, does that mean they are equivalent, ie., each implies the other? If so, is there a practical need for a relational equality operator (as opposed to equality between domain values)? Received on Thu May 06 2010 - 17:32:17 CEST

Original text of this message