Re: deductive databases
From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Thu, 12 May 2005 22:45:23 GMT
Message-ID: <70Rge.89352$4_1.5246075_at_phobos.telenet-ops.be>
Date: Thu, 12 May 2005 22:45:23 GMT
Message-ID: <70Rge.89352$4_1.5246075_at_phobos.telenet-ops.be>
Mikito Harakiri wrote:
>
> Well, "connect by" is [admittedly not especially elegant] way to
> express transitive closure. Now, are there any queries that can be
> expressed with "Recursive With" but not with transitive closure?
I think there are. It is known that on an ordered domain FO(TC) (first order logic plus transitive closure) can express exactly all NSPACE[log n] queries and FO(LFP) (first order logic plus a least fixpoint operator) exactly all PTIME queries. The latter class is known to be strictly greater than the first.
- Jan Hidders