W3C home > Mailing lists > Public > www-rdf-logic@w3.org > July 2001

Re: Why must the web be monotonic ?

From: pat hayes <phayes@ai.uwf.edu>
Date: Tue, 24 Jul 2001 12:36:22 -0700
Message-Id: <v04210103b783782ed3ca@[]>
To: "Seth Russell" <seth@robustai.net>
Cc: "Tim Berners-Lee" <timbl@w3.org>, "www-rdf-logic" <www-rdf-logic@w3.org>
>From: "Ian Horrocks" <horrocks@cs.man.ac.uk>
> > condition for being a WhiteWine. Moreover, adding further axioms (or
> > even RDF triples) to the ontology can never change this (otherwise we
> > would be non-monotonic).
>I think I've heard it said that the web must be monotonic.  Have I misheard?
>If not, then why must the web be monotonic?

Good question. The answer is controversial, but seems to me to be 
clear. First, its not the Web that is monotonic (whatever that would 
mean) but the reasoning from Web resources that must be monotonic. 
And the reason is that it - the reasoning - needs to always take 
place in a potentially open-ended situation: there is always the 
possibility that new information might arise from some other source, 
so one is never justified in assuming that one has 'all' the facts 
about some topic (unless you have been explicitly told that you 
have.)  Nonmonotonic reasoning is therefore inherently unsafe on the 
Web. In fact, nonmonotonic reasoning is inherently unsafe anywhere, 
which is why all classical reasoning is monotonic; this isn't 
anything particuarly new. But the open-ended assumption that seems to 
underlie much thinking about reasoning on the semantic web makes the 
issue a little more acute than it often is in many of the situations 
where logic has been put to use in computer science.

For example, if you are reasoning with a particular database of 
information, it is often assumed that the dbase is complete, in the 
sense that if some item is missing, then it is assumed to be false: 
if a hospital's databanks do not contain any record of a certain 
patient, you can conclude that they weren't a patient at the hospital 
(because if they had been, their record would be there.) Nonmonotonic 
inference modes such as this (often called negation-as-failure, ie if 
you fail to find P in the database, assume P is false) are widely 
used because they are efficient and because closed worlds are so 
common. It is used in Prolog, where it is often exactly what one 
wants because the domains being described are recursively enumerable 
and failure to prove amounts to knowing that no proof can exist. But 
open-ended domains are not like this, and it is very dangerous to 
rely on this kind of reasoning when one has no licence to assume that 
the world is closed in the appropriate way. If there were ever an 
open-ended domain it is surely the semantic web.

There is a way to combine the global security of monotonic reasoning 
with the local advantages of nonmonotonic reasoning (eg when working 
with hospital records on a website, say), which is to provide a way 
to state the closed world assumptions explicitly. Take the 
hospital-records example again, where you fail to find any record of 
a patient and conclude that the person never was a patient.  That is 
a non-monotonic inference from just the patient records, but it is 
monotonic from the patient records PLUS an explict statement of the 
closed-world assumption, ie the statement that the set of records is 
exhaustive. So if we have a way to refer to a set of assertions - 
say, all those at a certain URL, or all those which use a certain 
namespace, or by some other means - and a way to state the 
closed-world assumptions that are being made about this set of 
assertions - say, they they are exhaustive with respect to all 
queries of a certain form - then the overall reasoning can be 
considered monotonic, even though it proceeds locally by using 
efficient nonmonotonic methods.

Right now, DAML+OIL and RDF have not entered into this area, but 
'rules' languages need to consider it seriously, in my view. The 
global advantages of monotonicity should not be casually tossed 
aside, but at the same time the computational advantages of 
nonmonotonic reasoning modes is hard to deny, and they are widely 
used in the current state of the art. We need ways for them to 
co-exist smoothly.

Pat Hayes

(650)859 6569 w
(650)494 3973 h (until September)
Received on Tuesday, 24 July 2001 15:36:22 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 2 March 2016 11:10:36 UTC