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
To: Pat Hayes <phayes@ai.uwf.edu>

```
> >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 UTC

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