[Top] [All Lists]

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

To: "[ontolog-forum]" <ontolog-forum@xxxxxxxxxxxxxxxx>
From: Ed Barkmeyer <edbark@xxxxxxxx>
Date: Wed, 07 Oct 2009 15:54:19 -0400
Message-id: <4ACCF1EB.4040504@xxxxxxxx>

John F. Sowa wrote:
>   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.
>   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.
>   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.
>       (01)

This is a good way to characterize the concepts.    (02)

>   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).
>   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".
> Pronouncements like #5 are the kind of scare tactics that
> politicians and talk-show pundits use to strike fear into
> gullible people.
>       (03)

John, I think this adds more heat than light.  This is not just a "scare 
tactic" to keep the DL folk in business.    (04)

Unfortunately, it has been my experience that reasoners for untrammeled 
languages exhibit a kind of "self-symmetric" behavior.  What appears to 
be a minor addition or modification to an axiom set can suddenly cause 
non-termination on 50 regression tests of the ontology.  It is really 
hard to know which straw will break the camel's back, even when you 
think you know how the reasoner does its searches.    (05)

The problem with the use of an "undecidable language" for interlinked 
Web ontologies is that you may not know when there has been a minor 
addition or modification to one of the ontologies your reasoning engine 
is using to answer your queries, with the consequence that everything 
that worked yesterday doesn't work today.  So there is motive for 
considering the "worst possible case" -- on the Internet, you have a 
million monkeys with typewriters.    (06)

I am a firm believer in expressive power over computational bounding, 
but I am not doing anything that absolutely must work next week.  I am 
only concerned about capturing available knowledge and using it in 
certain well-defined patterns to make judgements.  And we hope that next 
year we will be able to do more with the same knowledge base, using 
better engines or more knowledge about how to steer them.    (07)

The DL approach constrains what you can write, so that it can guarantee 
results.  For some projects, that is much more important than allowing 
the capture of every nuance.  One man's meat is another man's poison.    (08)

> 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.
>       (09)

Indeed.  In most programming languages, however, there are constraints 
on what you can express, so that all syntactically valid programs can be 
supported by certain implementation patterns.  For reasons of that kind 
of tractability, for example, a language like Java doesn't allow a class 
to be defined as a subclass of more than one other class!  In some 
sense, DL is to FOL as Java is to LISP -- they both make the capture of 
intent easier and more reliable, but constrain the expressions to what a 
certain implementation pattern can support.
The difference is that for DL we have a whole set of academic 
mathematics to characterize and justify our choices, while the Java 
limitations were just engineering choices justified solely by experience.    (010)

> 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.
>       (011)

Agreed.  See above.    (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 was EB, not LY.
> 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)

Yes, but now you are talking about the semantics of the relations _you_ 
are defining and using in the FOL language, not the formal semantics of 
the language itself.  The intent of my email was to separate exactly 
these two ideas.  By analogy, it is possible to use Java to formulate 
stress analysis, but 'stress' is not a Java concept.    (015)

-Ed    (016)

Edward J. Barkmeyer                        Email: edbark@xxxxxxxx
National Institute of Standards & Technology
Manufacturing Systems Integration Division
100 Bureau Drive, Stop 8263                Tel: +1 301-975-3528
Gaithersburg, MD 20899-8263                FAX: +1 301-975-4694    (017)

"The opinions expressed above do not reflect consensus of NIST, 
 and have not been reviewed by any Government authority."    (018)

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

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