On 5 Mar 2007, at 22:31, John F. Sowa wrote:
Leo,
To continue my point that efficiency *always* depends
on what you're trying to do, I would like to address the
problem of finding a consistent set of constraints:
I, as usual, recommend the
description logic complexity navigator:
Given a set of arbitrary first-order constraints, the problem
of proving consistency is NP complete. Yet every SQL database
permits arbitrary first-order constraints.
Q: How is possible to prove that the constraints are consistent?
A: Trivially.
The point is that no database designer *ever* begins with
an arbitrary set of constraints. They *always* begin with
some actual data -- a sample DB that shows what kind of data
they expect to work with.
That sample DB consists of a set of entities and a set of
relations that are assumed to be true of those entities.
In other words, the starting point is a Tarski-style model.
Although *finding* a model is NP complete, the task of
*checking* constraints is trivial, if a model is given.
Given a proposed set of first-order constraints that do not
depend on any recursive definitions -- i.e., anything expressible
in SQL WHERE clauses -- the evaluation time in terms of a sample
model takes, in the worst case -- polynomial time.
If all the constraints turn out to be true of the model, then
they are consistent. If any of them turn out to be false,
either throw them away or revise them to make them true.
Bottom line: If you're trying to define axioms or definitions
for an ontology, a database, or a knowledge base, it's a good
idea to start with at least one illustrative example.
John
_________________________________________________________________