W3C home > Mailing lists > Public > www-rdf-rules@w3.org > January 2004

querying higher logic with graph query

From: Eric Prud'hommeaux <eric@w3.org>
Date: Thu, 8 Jan 2004 14:29:01 -0500
To: www-rdf-rules@w3.org
Message-ID: <20040108192901.GG21964@w3.org>

This message discusses using graph matching to query the product of
inference from RDFS or OWL semantics or arbitrary rules with graph
implications. Graph means DLG with the standard RDF node types.

I'm sure someone has discussed this before, but I didn't find it
quickly and I'd like to share ideas here.

The proposed RDF DAWG charter asks the working group to specify
language and protocol for communicating a query graph to a query
service and for returning the matches to the requester.

Let's use two KBs, relationalKB and prologKB. relationalKB holds
some facts:
 holds(dog, subClassOf, animal).
 holds(animal, subClassOf, thing).
 holds(dog, subClassOf, thing).
 holds(rover, instanceOf, dog).
 holds(rover, instanceOf, animal).
 holds(rover, instanceOf, thing).

prologKB holds some (similar) facts:
 holds(A, subClassOf, B) :- holds(A, subClassOf, X), holds(X, subClassOf, B).
 holds(A, instanceOf, B) :- holds(A, instanceOf, X), holds(X, subClassOf, B).
 holds(dog, subClassOf, animal).
 holds(animal, subClassOf, thing).
 holds(rover, instanceOf, dog).

Now let's specify that the KBs only tell you facts in the form of:
 holds(subject1, predicate1, object1).
 holds(subject2, predicate2, object2).
 holds(subjectN, predicateN, objectN).

We can ask either whether rover is a dog:
  query(holds(rover, instanceOf, dog)).
and get back
  holds(rover, instanceOf, dog).
from either KB. The same is true for facts that prologKB infers:
  query(holds(rover, instanceOf, What)).
         ==>
  What=dog; What=animal; What=thing;

We can spruce up the query language to express disjunction:
  query(or(holds(rover, instanceOf, animal), 
           holds(rover, instanceOf, vegetable))).

If we introduce universals, we can kind of test for rules, depending
on how the universal is interpreted. The prologDB could interpret
  query(forall(X, and(holds(X, instanceOf, dog)
                      holds(X, instanceOf, animal))))
as testing for the rules
 holds(A, subClassOf, B) :- holds(A, subClassOf, X), holds(X, subClassOf, B).
 holds(A, instanceOf, B) :- holds(A, instanceOf, X), holds(X, subClassOf, B).
 holds(dog, subClassOf, animal).
while the relationKB would probably interpret this according to relational
calculus and say
 !(forsome(X, and(holds(X, instanceOf, dog), 
                  !holds(X, instanceOf, animal))))
which askes the question:
  Is there anything (in my closed universe) that's a dog but not an 
  animal?

How would this language report back? The response
  "yup"
seems to violate the "use of RDF in some serialization for the
returned results" clause [1]. Perhas the query could be labeled:
  query(7, forall(X, and(holds(X, instanceOf, dog)
                         holds(X, instanceOf, animal))))
so the answer could be:
  holds(7, got, "yup").

So, the constraint that responses be couched in terms of graphs has
some implications, but It doesn't preclude expressivity in the
query. The solutions above may not be palatable, but I just whipped
them up -- it is likely that smarter people with more time will
produce better results.

[1] http://www.w3.org/2003/10/RDF-Query-Charter#expressivity
-- 
-eric

office: +81.466.49.1170 W3C, Keio Research Institute at SFC,
                        Shonan Fujisawa Campus, Keio University,
                        5322 Endo, Fujisawa, Kanagawa 252-8520
                        JAPAN
        +1.617.258.5741 NE43-344, MIT, Cambridge, MA 02144 USA
cell:   +1.857.222.5741 (does not work in Asia)

(eric@w3.org)
Feel free to forward this message to any list for any purpose other than
email address distribution.
Received on Thursday, 8 January 2004 14:29:01 GMT

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