W3C home > Mailing lists > Public > www-rdf-rules@w3.org > September 2001

Re: What is an RDF Query?

From: Sandro Hawke <sandro@w3.org>
Date: Mon, 17 Sep 2001 10:56:52 -0400
Message-Id: <200109171456.f8HEuqh30559@wadimousa.hawke.org>
To: "Peter F. Patel-Schneider" <pfps@research.bell-labs.com>
cc: G.R.Wagner@tm.tue.nl, www-rdf-rules@w3.org

> > Both with respect to bottom-up and to top-down evaluation it is 
> > natural then to define a derivation rule for a specific KR system 
> > in such a way that its antecedant is a query expression and its 
> > consequent is an input expression.
> 
> Not to me it isn't.  Again, there are lots of things in query languages
> (like SQL) that we may not want in antecedants of rules.  Similarly, there
> may be things in rule consequents (e.g., variables) that we may not want in
> the assertion language.
> > Gerd Wagner
> Peter F. Patel-Schneider

I think we ought to seriously explore the possibility of using an RDF
graph not only as the assertion language, but also as the query, rule-
premise, and rule-conclusion languages.  I'm sure it wont be perfect,
but this seems like an important idea to consider and a strawman
against which to compare alternatives.   From here, I'd be interested
to hear what you (Peter) think is still needed.

Since I have trouble thinking in RDF graphs sometimes, I translate
them to a small subset of FOL for this kind of work.  Specifically, I
use the subset with only constants, existential variables, 2-ary
predicates, and conjunction.  (No universal variables, no negation, no
disjunction, no equality, and no logic functions.)

Using this language for assertions is obvious.  Using it for queries
nearly obvious: you ask for a proof of the formula.  Using it for a
rule-premise or rule-conclusion gets a little more tricky, because we
want to sort-of join the scopes of the existential variables in the
two parts.  I think there are two fairly natural ways to do this: one
seems to give us datalog rules and the other seems to give us Horn
rules.

Style 1:  

  Simply combine the scope of variables in the premise and conclusion.
  So if we have two RDF graphs (in FOL notation [2]):
 
    (1) EXISTS x In(Spot, x) AND In(x, TheYard) AND Material(x, Wood)
    (2) EXISTS x Isa(x, DogHouse)
  
  we can use these in a rule by turning the existential variables into
  universal variables in a scope outside of both formulas:

    FORALL x
       In(Spot, x) AND In(x, TheYard) AND Material(x, Wood)
       => 
       Isa(x, DogHouse)

  I think this is as expressive as datalog.  There is a question as
  to what it means if a variable occurs only in the second clause.  In
  this style, I think we simply disallow that case.

Style 2:

   We say that any variables in the second formula which are not also
   in the first formula remain as local existential variables.

     (1) EXISTS g1,g3 Grandparent(g1,g3)
     (2) EXISTS g1,g2,g3 Parent(g1,g2) AND Parent(g2,g3)

   would become a rule like this:

     FORALL g1,g3
        Grandparent(g1,g3)
	=>
        EXISTS g2 Parent(g1,g2) AND Parent(g2,g3)

      (This rule basically says that if two things have a grandparent
      relationship, there is a third thing and they have a transitive
      parent relationship through that third thing.)

   This may well not be full Horn logic, but I believe it's more
   expressive than Style 1, since I can't figure out how to express
   this example in Style 1.  I also can't think of any Horn examples
   that I can't express in Style 2.  (While Style 2 doesn't have the
   logic functions which normally separate datalog and Horn logic, the
   nested existential corresponds to Skolem functions, and in my
   playing around that seems to be enough.  I don't have the skills
   to approach this formally.)

(I have implemented Style 2, and I've talked about this before [1] but
that discussion went in a somewhat different direction.)

    -- sandro

[1] http://lists.w3.org/Archives/Public/www-rdf-logic/2001Mar/0075.html
[2] I used an FOL ascii syntax found on this simple introduction:
    http://www.sdsc.edu/~tbailey/teaching/cse151/lectures/chap07a.html
Received on Monday, 17 September 2001 11:01:36 GMT

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