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

On Sun, 18 Jul 2004 19:26:14 +0000, Marshall Spight wrote:

> Lately we've been discussing 1NF and "a question for Mr. Celko."
> 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? Is there a middle ground, above FOL but
> below fully-recursive definitions, that is more expressing
> than FOL but still consistent?

Sure. Just limit yourself to finite sets and introduce a strict typing regime that does not allow recursion. That pretty much takes care of all the theoretical problems and there has in fact already been research on allowing recursive sets. For an example, see how Chris Date et al do that in the Third Manifesto. But then still a lot practical problems remain like doing for example query optimization. It's not enough that the problems become computable, they have to be computable in an efficient and scalable way.

• Jan Hidders