[Top] [All Lists]

Re: [ontolog-forum] Ontology-based database integration

To: "[ontolog-forum]" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: "John F. Sowa" <sowa@xxxxxxxxxxx>
Date: Wed, 07 Oct 2009 13:22:09 -0400
Message-id: <4ACCCE41.3060109@xxxxxxxxxxx>
Len and Chris,    (01)

I basically agree with Chris Menzel's comments on Len Yabloko's
note, but I'd like to add a few more comments.    (02)

CM> OWL is an attempt to provide a standardized ontology language
 > built upon a logical framework in which questions of consistency,
 > validity, etc are decidable.  In general, such questions are not
 > decidable, and that is certainly a limitation, but it predates
 > the Semantic Web by several decades.    (03)

Computational complexity and decidability are two related subjects
that all programmers should study in their formative years.  But
it's important to note the following points:    (04)

  1. Computational complexity is a property of an algorithm.  It
     is not directly a property of a problem and certainly not
     a property of a language for writing algorithms.    (05)

  2. It is true that for a given problem, one can talk about the
     computational complexity of the *best known* algorithm for
     solving that problem.  However, this a "squishy" property,
     because new algorithms may be discovered and slight changes
     to the problem can frequently be solved by algorithms that
     are many orders of magnitude more efficient.    (06)

  3. Decidability is a property of a question.  It is not directly
     a property of a proposition and certainly not a property of
     a language for stating propositions.    (07)

  4. For example, the same proposition p might be converted
     to the question "Is p true in terms of the database D?"
     For propositions stated in first-order logic and any
     relational DB, questions of that form can be translated
     to SQL and be answered in at worst polynomial time.
     But the question "Is p true in terms of every possible
     database D?" requires a theorem prover that may answer
     very quickly or it may loop forever (undecidable).    (08)

  5. Those people who attribute decidability to languages are
     usually looking at the worst possible case of the worst
     possible question for the most complicated possible
     proposition.  Then they make a blanket pronouncement
     that language L is bad because it is "undecidable".    (09)

Pronouncements like #5 are the kind of scare tactics that
politicians and talk-show pundits use to strike fear into
gullible people.    (010)

The answer to such politicians is that *every* major
programming language is sufficiently expressive to allow
programmers to write intractable or undecidable programs.
And no programmer would *ever* ask for their pet language
to be made less expressive.    (011)

The same point is true of knowledge engineers who use
declarative logics.  Those who use expressive languages
know how to use them effectively, and nobody who uses
such languages would prefer them to be less expressive.    (012)

LY> ... classical formal logic offers only two possible
 > interpretations:  it is either true or it is false,
 > and it cannot be both.    (013)

That is true, but it is possible to use classical FOL to
make statements about probabilities and to reason about
the probabilities of other statements in FOL.  In that
sense, FOL is being used as a metalanguage to reason
about subjects with a variable degree of probability.    (014)

John Sowa    (015)

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    (016)

<Prev in Thread] Current Thread [Next in Thread>