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

Re: What is an RDF Query?

From: Pat Hayes <phayes@ai.uwf.edu>
Date: Mon, 17 Sep 2001 13:24:45 -0500
Message-Id: <p05101009b7cbe85e7707@[205.160.76.175]>
To: Sandro Hawke <sandro@w3.org>
Cc: 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.

That idea has already been explored by Stefan Decker. He and some 
colleagues demonstrated a working system at the DAML PI meeting 
(which I think you were also at, Sandro, no?)

>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.)

Right, that is the subset that corresponds to RDF according to the 
model theory.

>
>Using this language for assertions is obvious.  Using it for queries
>nearly obvious: you ask for a proof of the formula.

OK; but be careful, since the existential variables act very 
differently when they occur in a conclusion than when they occur in 
an assertion. (It is valid to bind a value to an existential in a 
conclusion, but not to one in an assertion.) This matters, since its 
the bindings to those variables which produce the answers to the 
queries :-)

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

If you were going to interpret those variables as universally 
quantified then you had better disallow them, yes, since the 
consequent might have universal quantifiers in it, which goes beyond 
RDF.

>
>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.)

Why not go to the usual normal form and say that this is two rules, 
since its conclusion is a conjunction. If you skolemize, the skolem 
function will keep track of the connections for you:

Forall g1, g3 (grandparent(g1,g3) => Parent(g1, GPSkolem(g1,g3)) )

Forall g1, g3 (grandparent(g1,g3) => Parent(GPSkolem(g1,g3), g3) )

>    This may well not be full Horn logic, but I believe it's more
>    expressive than Style 1,

Yes, it is, since it has existentials inside the scope of universals, 
which isn't expressible in RDF.  But we could still use RDF as a 
language for specifying the 'patterns' to be matched, but allow a 
somewhat larger collection of bindings to the variables than just 
ground URIs and literals. Think of a skolem function as a kind of 
link to a place in the rules where a query engine has a licence to 
conclude that something exists which satisfies some RDF, but it has 
to use a special name format to keep track of the mutual dependencies 
of that thing on other things.

(Hmm, I wonder, could a nested function  term be encoded as a URI? If 
so, this *would* be RDF.)

Pat Hayes

>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


-- 
---------------------------------------------------------------------
IHMC					(850)434 8903   home
40 South Alcaniz St.			(850)202 4416   office
Pensacola,  FL 32501			(850)202 4440   fax
phayes@ai.uwf.edu 
http://www.coginst.uwf.edu/~phayes
Received on Monday, 17 September 2001 14:24:44 GMT

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