Re: FOL/HOL: is there a middle ground?

"Ralph Becket" <rafe_at_cs.mu.oz.au> wrote in message news:3638acfd.0407182031.584a46fa_at_posting.google.com...
> "Marshall Spight" <mspight_at_dnai.com> wrote in message news:<q9AKc.114259$IQ4.31025@attbi_s02>...
> > There are clear incompleteness problems associated with allowing
> > the definition of set A to references the definition of set A. What
> > are some of the other problems with using HOL as a basis for
> > a relational algebra?
>
> To put it succinctly:
> (a) the relational model fundamentally depends upon the notion of
> equality, but
> (b) deciding whether two relations are equivalent is undecidable
> in general.

Um, not if the relations are specified extensionally, which is usually what we're talking about with relational databases. Certainly intensional equivalence is undecidable.

> Note that trying to answer (b) by just using name equivalence
> doesn't work:
> if p(X) <=> X mod 2 = 0
> and q(X) <=> 2 in {Y | Y is a factor of X}
> then p and q are certainly equivalent. But deciding this sort
> of thing in general would mean solving the halting problem.
>
> > Is there a middle ground, above FOL but
> > below fully-recursive definitions, that is more expressing
> > than FOL but still consistent?
>
> Welllll, you could restrict yourself to purely finite relations,
> but that puts a serious crimp in the utility of the idea.

Again, when we're talking extensional sets in actual computers, we're always talking about finite relations.

> > What are the various pitfalls one runs into with recursively
> > defined relations? Can we enumerate the "holes" and plug
> > them all with restrictions on our fractal order logic?
>
> 'Fraid not. You can't even begin such a task.
>
> Can you explain why you would want this level of expressive
> power?

Actually, all I want is relation-valued attributes and list-valued attributes.

Marshall Received on Mon Jul 19 2004 - 06:51:05 CEST