W3C home > Mailing lists > Public > www-rdf-rules@w3.org > September 2001

RE: Rules are *not* Horn clauses!

From: Pat Hayes <phayes@ai.uwf.edu>
Date: Fri, 21 Sep 2001 09:35:49 -0500
Message-Id: <p05101011b7d0f4282b63@[]>
To: "Wagner, G.R." <G.R.Wagner@tm.tue.nl>
Cc: www-rdf-rules@w3.org
>  > >A negation operator is essential for
>>  >expressing queries that arise in practical applications. For
>>  >being practically (and not just academically) relevant, rules
>>  >for the SemanticWeb need negation!
>>  OK, you mean negation by failure. I thought maybe you did. This is a
>>  controversial issue in the semantic web context. I actually strongly
>>  disagree: I think that negation by failure, like any other
>>  non-monotonic construction, is not a viable mechanism for the
>>  semantic web; [...]
>>  The inference from (nothing in this KB matches A)
>>  to (A is false) is the non-monotonic step that I think must be
>>  avoided, or at any rate somehow controlled and isolated, in order to
>>  make the semantic web useable. For example, it may be necessary to
>>  understand all such 'negations' as containing an indication of what
>>  KB they are relative to,
>I think that in many cases this may be necessary anyway. The scope
>of rules need not be the entire web, but it may be restricted to a
>subset (e.g. by specifying a domain or a specific set of documents) or
>to a certain SQL database specified by means of an URL. Then, whenever
>someone has complete information about a certain type of facts (as is
>often the case with administrative information, such as, for instance,
>the classification of corporate documents) that are expressed on the
>Web, and in addition uses rules referring to these facts, then negation-
>as-failure is as viable for such a SemanticWeb application as it is in
>a relational (or deductive) database application.

For one particular application, yes, if everyone else is able to 
check the crucial assumption that the information which was used is 
in fact complete. But look: if this 'closure' assumption is made 
explicit and included into the logic, then the whole system is 
monotonic. To infer, from a failure to find A in S, that A is not in 
S (or from a failure to prove A from S, that A does not follow from 
S), is a monotonic inference and requires no special logical 
negation.  All the logical complexity arises from making the invalid 
step from A not being in S, to A being false.

I would also note that such complete information is often harder to 
obtain than is commonly supposed. For example, many information 
sources which contain records of every member of a certain set - 
employee records, patient records, document archives, etc. - are in 
fact temporally sensitive; at any time they are complete for 
information at that time, but they are not complete into the future. 
This means that any nonmonotonic conclusion reached using such a 
resource must be considered potentially unreliable as soon as it is 
generated, unless it is explicitly time-stamped and the state of the 
database also time-linked; but if that is done, then the inference is 
made monotonic again.

>Another usage of negation-as-failure would be to express default rules
>for heuristic reasoning. This may be interesting for SW applications
>as well.

Maybe, but that is not the basic logical framework for information interchange.

>Notice that for Open-World reasoning, we may, in addition, introduce
>a negation that has been called "strong" in some logics (viz in partial
>logic and in Nelson's "constructive logic with strong negation"). We
>then obtain a formalism with two kinds of negation, which may be
>logically justified be referring to partial logics with two negations
>and to Nelson's logic, and which may be computationally justified
>by referring to extendend logic programs (more recently also called
>"A-Prolog"). So, I would like to claim that the Semantic Web needs
>two kinds of negation. But maybe this should better be discussed in
>a new thread.

Maybe. Right now, the semantic web most needs a simple, robust, 
expressive, monotonic logic which supports efficient proof-checking. 
It would be hard to do better than classical first-order relational 
logic, in my view; though one can make a case for type theory. We can 
get to fancier stuff later; I see no pressing need for Nelsonian 
negation, or intuitionistic logic or any of these exotica.  Prolog is 
a subset of classical logic together with some implicit closure 
assumptions (embodied in stable model semantics) which need to be 
made explicit for Web use since they cannot be assumed globally. 
Similarly for the closed-world assumptions that underlie the common 
uses of negation by failure. We need to dig these ideas out: 
currently they are buried in the semantics, but we need to be able to 
*say* them in our formalisms. The logic that is left in the semantic 
foundations once all this has been uncovered will, I am confident, be 
some kind of classical logic. (Sorry if this seems a very a boring 
conclusion for a logician, but I really think the world needs us to 
put aside the interesting stuff, and get the basics into a useable 
form. )

Pat Hayes

IHMC					(850)434 8903   home
40 South Alcaniz St.			(850)202 4416   office
Pensacola,  FL 32501			(850)202 4440   fax
Received on Friday, 21 September 2001 10:35:57 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:53:09 GMT