Bijan, Dmitry, and Enrico, (01)
I deleted all the email lists from cc's, except
for ontolog-forum. (02)
BP> ... some of us must be missing some context. (03)
The context was a discussion about how the notion of
complexity is related to a language. I had pointed out
that the complexity of a language depends entirely on
the kinds of problems that are being formulated in that
language. (04)
I realize that the notion of descriptive complexity
of a language is defined in terms of the worst-case
provability of statements in that language. But for
practical problems, that definition is misleading. (05)
In particular, FOL is used for stating queries and
constraints in relational databases (in SQL or Datalog).
The evaluation of such statements is performed by model
checking, not by theorem proving (i.e., the database is
a set of entities and a set of relations -- a classical
Tarski-style model). (06)
For that purpose, FOL statements of queries and constraints
are not only decidable, but decidable in polynomial time. (07)
DT> Simple idea that comes to my mind immediately: the DB is
> a *closed world*, i.e. if something is not there, this does
> not hold. (08)
Databases are applied to both kinds of worlds. In fact,
Ray Reiter coined those terms in a paper about relational
databases in 1978. (09)
DT> It is different for the DL, which is an *open world*.
> That means if some fact is not known to be true, it can be
> either true or false (in a particular world). This means,
> that the search space is exponentially larger in case of
> description logic comparing to DBs. (010)
The search space is never greater than the amount of available
data. The difference between a closed world and an open world
is not in the search space, but in how the absence of some data
should be interpreted -- e.g., as negation in a closed world or
as unknown in an open world. (011)
Furthermore, commercial relational DBs are designed to handle
terabytes and even petabytes of data. (012)
EF> Well, it seems to me:
> 1) the problem of checking consistency (i.e., finding the existence
> of a model) of an arbitrary FOL formula is not decidable;
> 2) the problem of checking that a FOL formula is true in an
> interpretation (i.e., that a DB is consistent wrt a set of FOL
> constraints) is PSPACE-complete in *combined* complexity (i.e, wrt
> the size of the constraints and the DB), while it is in PTIME in
> *data* complexity (i.e., wrt the size of the DB only);
> 3) according to the above mentioned DL complexity navigator, the
> problem of checking consistency of DL KBs is most of the time
> decidable. (013)
I agree. (014)
The point I was trying to make is that the question of *finding*
a model never arises in database design. The normal heuristic
for database design is to begin with a sample database against
which the constraints are tested. Therefore, testing the
consistency of the constraints is a matter of model checking. (015)
In fact, I would claim that in the *design* stages for ontology,
databases, or knowledge bases, the designer has an intended model
in mind. I can't imagine anybody designing an ontology without
being aware of any examples of the subject domain. (016)
I realize that there are often specific kinds of problems for which
model finding is important. But the task of designing an ontology
is not one of them. (017)
John (018)
_________________________________________________________________
Message Archives: http://ontolog.cim3.net/forum/ontolog-forum/
Subscribe/Config: 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 Post: mailto:ontolog-forum@xxxxxxxxxxxxxxxx (019)
|