On Dec 18, 2009, at 8:10 AM, John F. Sowa wrote:
> ...
>>> JFS>> For database queries and constraints, SQL supports full FOL, but even
>the worst case examples can be evaluated in polynomial time...
>
>> CM> I am probably not understanding the claim, but how is this possible if
>SQL supports full FOL, in which we can easily express problems that can be
>solved, if at all, in at best exponential time?
>
> SQL evaluates the truth value of a given FOL statement in terms of a fixed
>model (i.e., the current state of the database). That takes polynomial time.
>SQL never evaluates a statement in terms of all possible models, which might
>require exponential time or even be undecidable. (01)
Oh, of course. But then it's perhaps a *bit* misleading to tout SQL's use of
FOL in response to general concerns about FOL's general undecidability since it
has the advantage of reasoning with respect to a fixed finite model. (02)
> The paternalistic approach assumes that all users are trying to prove a
>theorem that is valid for all possible models. But most people who ask a
>question are only interested in a specific model, such as the current DB. (03)
This isn't clear to me at all. If I'm just trying to describe a certain
conceptual domain like, say, human physiology, it doesn't seem to me that any
inferencing is done vis-á-vis any sort of fixed finite model. It's just done
on the basis of the axioms of the ontology which, if expressed in full FOL,
raises the possibility of intractability. I'm not saying it can't be managed
-- obviously, it can, if only by putting temporal bounds on searches for proofs
and countermodels. But that there might be a need to do so if one uses full
FOL does need to be expressed. (04)
-chris (05)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Config Subscr: http://ontolog.cim3.net/mailman/listinfo/ontolog-forum/
Unsubscribe: mailto:ontolog-forum-leave@xxxxxxxxxxxxxxxx
Shared Files: http://ontolog.cim3.net/file/
Community Wiki: http://ontolog.cim3.net/wiki/
To join: http://ontolog.cim3.net/cgi-bin/wiki.pl?WikiHomePage#nid1J
To Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (06)
|