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

RE: Rules are *not* Horn clauses!

From: Wagner, G.R. <G.R.Wagner@tm.tue.nl>
Date: Fri, 21 Sep 2001 11:44:57 +0200
Message-ID: <511BB18E82E9D11188230008C724064602D9DDCF@tmex1.tm.tue.nl>
To: "'Pat Hayes'" <phayes@ai.uwf.edu>
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. 

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

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.

> >But one may view SQL queries (without aggregates) as FOL formulas.
> >E.g., "SELECT x,y,z FROM p WHERE x=y" corresponds to the formula
> >"p(x,x,z)" which is answered by returning all bindings to x and z
> >such that the corresponding instantiations are entailed by the
> >current database state.
> 
> Thanks, that is a view of SQL with which I was not familiar. Is there 
> is any kind of guarantee that an SQL processor will be able to 
> perform all the inferences that this translation would suggest? 

That would have to be proved for each RDBMS by means of formal
verification methods (I don't think Oracle or IBM have done it).
 
> >For each logic (even if it does not have an implication)
> >we can define the notion of a sequent F => G, where both F and G
> >may be composite and have free variables, and using the logic's
> >model theory, we can define when such a sequent is satisfied by
> >a model. This seems to provide a generic concept of a rule.
> 
> [...] I agree that sequents are a more powerful and more general tool. 
> [...] Sequent logic typically operates in what might called 'sideways' 
> mode rather than top-down or bottom-up, where inference rules (sorry) 
> manipulate both antecedent and consequents together. In any case, 
> we have a perfectly good, precise terminology already for sequents, 
> so why introduce an imprecise, confused one to replace it?

I do not propose to use sequent logic, but just want to point out 
that we can view a rule with antecedent and consequent as a basic 
expression (like a sequent) that does not need to be related to Horn 
clauses and can be used in all kinds of formalisms/logics.

-Gerd
Received on Friday, 21 September 2001 05:45:01 GMT

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