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

Re: querying higher logic with graph query

From: Ian Horrocks <horrocks@cs.man.ac.uk>
Date: Thu, 22 Jan 2004 10:58:16 +0000
Message-ID: <16399.44232.354896.601495@galahad.cs.man.ac.uk>
To: Martin Duerst <duerst@w3.org>
Cc: "Eric Prud'hommeaux" <eric@w3.org>, www-rdf-rules@w3.org

1. Maybe I am misunderstanding, but it seems that what is being
discussed here is simply a syntax for querying. Is it the intention
that the semantics of query answers would depend on the semantics of
the system being queried, and would not be considered by the proposed
working group?

2. I can imagine important kinds of query that don't fit so easily
into the structure that you are proposing, in particular aggregation
queries such as "how many instances are there of class C?". This
cannot, in general, be answered simply by counting the instances of C
that are returned by a "type" query - in OWL ontologies, for example,
it may be possible to deduce the existence of individuals, and perhaps
even to count them, without being able to name some or all of them
(not to mention the fact that trying to answer the query in this way
could be very costly if the number is large). I'm not saying that one
couldn't imagine an RDF based syntax for such queries, just that it may
need to be more complex than simply finding bindings for graph

3. There are other related issues such as how to answer queries like
"return all the parents of John". We may know that there are two such
individuals, and even have additional information about them such as
their gender, but we may not be able to name them. Simply giving an
empty answer seems to be disingenuous. Some use of bnodes may be
possible, but care is required as e.g. an OWL ontology may entail the
existence of an infinite number of anonymous individuals.


On January 8, Martin Duerst writes:
> 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, 22 January 2004 06:02:24 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 2 March 2016 11:10:15 UTC