Re: querying higher logic with graph query

At 14:29 04/01/08 -0500, Eric Prud'hommeaux wrote:

>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?

Which is not, for relationKB, a correct transformation of your original
forall query, because we also have to test for animals that are not dogs.
[We wouldn't find any in this example, but plenty in the general case :-]

But this also points to another way to convert the query into one that
replies with a (set of) graphs. The query is simply
     holds(X, instanceOf, dog), !holds(X, instanceOf, animal)
     !holds(X, instanceOf, dog), holds(X, instanceOf, animal)
(i.e. give me all the X that are dogs but not animals, and all the X
that are animals but not dogs). The language can report back all
the triples with X that it found (e.g. holds(kerberos, instanceOf, dog),
[assuming that the legendary Greek dog doesn't count as an animal]
holds(garfield, instanceOf, animal) [garfield is a cat, not a dog].
The equivalent of your "yup" answer would be given by the empty
reply, the empty graph.

Similar to Eric, I just wiped this up, sorry.

Regards,    Martin.

>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 16:10:24 UTC