# Re: On Formal IS-A definition

From: Tegiri Nenashi <tegirinenashi_at_gmail.com>
Date: Thu, 6 May 2010 13:02:44 -0700 (PDT)

On May 6, 1:39 am, Erwin <e.sm..._at_myonline.be> wrote:
> On 5 mei, 22:56, Tegiri Nenashi <tegirinena..._at_gmail.com> wrote:
>
> > On May 5, 12:41 pm, Erwin <e.sm..._at_myonline.be> wrote:
>
> > > ... Not in the same sense that relation algebra prevents
> > > graph databases because relation algebra does not understand graphs.
>
> > This is very imprecise statement. I'll embark upon your typo and
> > suggest that relation algebra (http://en.wikipedia.org/wiki/
> > Relation_algebra) does exactly that. It manipulates binary relations
> > that are essentially adjacency matrices representing direct acyclic
> > graphs.
>
> Yes.  And I know about transitive closure and the concept of
> generalized transitive closure too, thank you.

I was referring to deMorgan/Peirce/Tarski relation algebra, which has nothing to do with relational algebra. Kleene star is a natural operation for the former, while its reincarnation in relational model in the form of Transitive Closure looks like an afterthought. It is not even total.

>... the IP is the single one principle that "proves" (note
> the quotes) (a) that the relational model can be used to represent
> _ANY_ information, iow that the relational model has a certain quality
> of "completeness", and (b) that it allows a simpler form of
> manipulation than would be possible in any model that is based on some
> type of "graph algebra".

> Another small point is that there is a school of thought which says
> something about a connection between relation algebra and first order

Here this terminology slip again: do you mean relation algebra or relational algebra? Relation algebra can express any (and up to logical equivalence, exactly the) first-order logic (FOL) formulas containing no more than three variables. This may be the reason why it never enjoyed wide adoption, and eventually lost to more successful Frege's predicate calculus.

> 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.

Again, my impression is that transitive closure doesn't fit into relational model. Kleene star, on the other hand, is natural operation, because it is converse's "long lost fraternal twin" (Vaughan Pratt).

Original text of this message