Hi All --

I was surprised to learn that RDF reasoning appears to be very restricted, as in:

 "...a more complex fact is expressed in RDF using a conjunction (logical-AND) of simple binary relationships. RDF does not provide means to express negation (NOT) or disjunction (OR). The expressive power of RDF corresponds to the existential-conjunctive (EC) subset of first order logic"   [http://www.w3.org/TR/rdf-concepts/]

Surely, for RDF to function as useful service-finding glue in the Semantic Web, it should at least support discovery of resources by being able to walk arbitrary depth first- and second-order hierarchies/ontologies ?

Ah, I hear you say, but the inferencing needed can be undecidable, or at best inefficient.

Not so !   It's been known for a number of years that a form of datalog augmented with negation-as-failure has efficient, terminating, sound and complete inference methods.

There's a rather formal paper about this: Backchain Iteration: Towards a Practical Inference Method that is Simple Enough to be Proved Terminating, Sound and Complete.  Journal of Automated Reasoning, 11:1-22, 1993.  (Yes, these results have been around for a while !)

On the less formal side, here's a little example showing the kind of thing one would expect for really useful Semantic Web inferencing.  The notation is that of the Internet Business Logic system, and the example can be run by pointing Netscape 7 to www.reengineeringllc.com  and selecting DataModelling1 .

Example:


1)  Table heading:

    this-relationship is a specialization of this-higher-relationship
  =================================================================

This is an "X IS-A relation Y" before inserting any tuples.


2) Populate the table

    this-relationship is a specialization of this-higher-relationship
    =================================================================
    sibling                                family
    marriage                               family
    family                                 the class of all relationships


3)   Say that IS-A is transitive

    some-relationship1 is a specialization of some-relationship2
    that-relationship2 is a specialization of some-relationship3
    ------------------------------------------------------------
    that-relationship1 is a specialization of that-relationship3


4)  Say that if two people are related by R1, and R1 IS-A R2, then they are related by R2

    some-person is related through some-relationship to some-other-person
    that-relationship is a specialization of some-higher-relationship
    ---------------------------------------------------------------------------
    that-person is related through that-higher-relationship to that-other-person

 
5)   Provide some facts

    this-person is related through this-relationship to this-other-person
    =====================================================================
    Fred                           marriage              Jane
    Fred                           sibling               John


6)   Ask who is related to whom and by what relationship, and get the answer table

    this-person is related through this-relationship to this-other-person
    =====================================================================
    Fred                           family               Jane
    Fred                           family               John
    Fred                           marriage             Jane
    Fred                           sibling              John
    Fred             the class of all relationships     Jane
    Fred             the class of all relationships     John

7)  Ask for an explanation of the last line of the answer, and get this:

    Fred is related through sibling to John
    sibling is a specialization of  the class of all relationships
    ---------------------------------------------------------------- 
    Fred is related through  the class of all relationships  to John


    sibling is a specialization of family
    family is a specialization of  the class of all relationships
    --------------------------------------------------------------
    sibling is a specialization of  the class of all relationships 

The alert reader will have noted that the example has sneaked in some second-order reasoning, while staying inside datalog.

One of the interesting things one can explore using this notation,  is how to write the English phrasing and logic to avoid traps like John Sowa's famous example  "Clyde is and elephant, and an elephant is a species, therefore Clyde is a species" .   (You can  see that the error crept in through the sloppy phrase in red.) 

So, this also begins to address the capture of English meanings in a form suitable for computation.

Hope this helps.   All comments gratefully received.      -- Adrian

    PS: If your screen does not show monospace fonts, the above tables may be misaligned -- apologies.


Adrian Walker
www.reengineeringllc.com
PO Box 1412
Bristol
CT 06011-1412 USA

adrianw@snet.net

Phone: USA 860 583 9677
Cell:    USA  860 830 2085
Fax:    USA  860 314 1029