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 relationships3)   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-relationship34) 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               John6)   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     John7) 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