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

Expressiveness of RDF as Rule Conclusion Language (was Re: What is an RDF Query? )

From: Sandro Hawke <sandro@w3.org>
Date: Mon, 17 Sep 2001 15:06:44 -0400
Message-Id: <200109171906.f8HJ6iE31716@wadimousa.hawke.org>
To: Pat Hayes <phayes@ai.uwf.edu>
cc: www-rdf-rules@w3.org

> >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,
> 
> Yes, it is, since it has existentials inside the scope of universals, 
> which isn't expressible in RDF. 

You didn't directly address whether this is as expressive as Horn
rules.   My argument goes something like this:

(1) We can rewrite any conjunction which uses n-ary relations as a
    conjunction using just 2-ary relations, if we have local
    existential variables.
    
       ... AND p(a,b,c) AND ...
===>
       ... AND (EXISTS c1 p1(c1,a) AND p2(c1,b) AND p3(c1,c)) AND ...

(2) We can rewrite any function term in a conjunction without
    functions terms, if we have local existential variables.

       ... AND p(f(g(a))) AND ...
===>   
       ... AND (EXISTS fval,gval p(gval) AND 
                val(f,fval,gval) AND 
		val(g,gval,a)) AND ...

    where "val" is some arbitrary otherwise-unused relation (which
    will actually have to get split like in step 1 to be 2-ary).

I believe using existential variables this way makes this rewriting be
semantically correct with either an assertion or query attitude.  If
we didn't care about the later, we could just use Skolem constants.

   -- sandro
Received on Monday, 17 September 2001 15:10:38 GMT

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