- From: John F. Sowa <sowa@bestweb.net>
- Date: Mon, 05 Mar 2007 16:31:11 -0500
- To: Ontology Summit 2007 Forum <ontology-summit@ontolog.cim3.net>, lobrst@mitre.org
- CC: ezolin@cs.man.ac.uk, public-owl-dev@w3.org, matthew.williams@cancer.org.uk, semantic-web@w3.org

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: > http://www.cs.man.ac.uk/~ezolin/logic/complexity.html 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

Received on Monday, 5 March 2007 21:33:49 UTC