# RE: Datalog With Only Binary Relations Is Too Weak

From: Stefan Decker <stefan@db.stanford.edu>
Date: Fri, 16 Mar 2001 09:44:59 -0800
Message-Id: <5.0.2.1.2.20010316090532.02daa958@db.stanford.edu>
To: "Cayzer, Steve" <Steve_Cayzer@hplb.hpl.hp.com>, "'jos.deroo.jd@belgium.agfa.com'" <jos.deroo.jd@belgium.agfa.com>, sandro@w3.org

```Steve, Sandro,

since you don't know the individual who is the parent of of the grandchild
you indeed  need a skolem function  to define the rule that there is a
parent.
The skolem function basically replaces the existential quantifier.
So given the fact that:

grandparent(gregorian, bret).

you need to define a rule, that a grandparent relation indeed
implies, that there is a parent. Since you don't know the identifier
of the parent, one has to use a skolem function  (e.g. existsParentOf) :

parent(X, existsParentOf(Y)) <- grandparent(X,Y).

So
parent(gregorian, existsParentOf(bret))

can be deduced.
Together with:

isLoved(?x) <---- parent(?x, ?y)

this indeed leads to sLoved(gregorian) .

To avoid looping in XSB:
use tabling, eg. a declaration like
:-table(parent/2).
at the beginning of your rules/facts..

See http://www.cs.sunysb.edu/~sbprolog/manual1/node52.html

Have fun,

Stefan

At 04:41 PM 3/16/2001 +0000, Cayzer, Steve wrote:
>Forgive the obvious point, but surely
>         grandparent(?a, ?c) <--- parent(?a, ?b) and parent(?b, ?c)

>only works one way?
>So you'd actually want some sort of definition (or implication the other
>way) as Jos said
>         {{:X :grandparent :Z} log:implies {:X :parent :Y}} log:forAll :X,
>:Y, :Z.
>
>I tried something similar in XSB
>         parent(X,Y) :- grandparent(X,Z).
>before I realised that because Y isn't quantified, of course this means that
>XSB will happily infer that grandparents are parents of anybody you choose
>to name.
>Oh, and also XSB started cycling having the 2 rules there.
>
>Surely all we want is Y as a skolem constant?
>Perhaps there's some simple way to do that in datalog? (he asks hopefully)
>
>
>__________________________________________________________
>Steve Cayzer                           Steve_Cayzer@hp.com
>Hewlett Packard Laboratories, Bristol
>
>-----Original Message-----
>From: jos.deroo.jd@belgium.agfa.com
>[mailto:jos.deroo.jd@belgium.agfa.com]
>Sent: 16 March 2001 14:54
>To: sandro@w3.org
>Cc: bgrosof@MIT.EDU; www-rdf-logic@w3.org
>Subject: Re: Datalog With Only Binary Relations Is Too Weak
>
>
>
>
> > [Sandro]
> > [ rdf-logic: This e-mail is continuing a face-to-face conversation
> > Benjamin Grosof and I were having yesterday.  I'm trying to understand
> > how KR language expressiveness theory applies to RDF.  Others are
> > welcome to join, of course. ]
> >
> > Okay, this morning my brain is properly in gear.
> >
> > Let's say we want to capture the grandparent relation.  Intuitively we
> > know grandparent(a,c) means something like parent(a,b) and
> > parent(b,c).  But how do we write this?
> >
> > One direction is easy:
> >     grandparent(?a, ?c) <--- parent(?a, ?b) and parent(?b, ?c)
> >     parent(gregorian, sandro)
> >     parent(sandro, bret)
> > we can now infer: grandparent(gregorian, bret).
> >
> > But what if we're given
> >     grandparent(gregorian, bret)
> >     isLoved(?x) <---- parent(?x, ?y)
> > and we'd like to prove isLoved(gregorian)?
> >
> > In FOL you can say
> >     forall a
> >       forall c
> >         grandparent(a,c) implies
> >            exists b suchthat
> >               parent(a, b) and
> >               parent(b, c)
> >
> > In NILE you say
> >      rule "" (\$a grandparent \$c ==> \$a parent !b; !b parent \$c)
>
>I have to learn NILE asap, any pointer Sandro?
>
> > In Prolog (but not Datalog) you can say:
> >      parent(X, parent_of(X)) :- grandparent(X, Y).
>
>Well, I must have forgotten about _of, how is Y unified?
>
> > In Prolog or Datalog you can rephrase in terms of a 3-ary relation:
> >     gen3(X,Y,Z) :- parent(X,Y), parent(Y,Z).
> >     parent(X,Y) :- gen3(X,Y,Z).
> >     parent(Y,Z) :- gen3(X,Y,Z).
> > which lets us rephrase our test case:
> >     gen3(gregorian, whatever, bret).
> >     isLoved(X) :- parent(X, Y).
> > and then infer isLoved(gregorian) as we want.   (In practice, this
> > set of rules puts prolog into a loop, although XSB should handle it
> > with tabling.)
> >
> > But how else?
>
>... what can we say here?
>
>{{:X :grandparent :Z} log:implies {:X :parent :Y}} log:forAll :X, :Y, :Z.
>{{:X :parent :Y} log:implies {:X a :isLoved}} log:forAll :X, :Y.
>:gregorian :grandparent :bret.
>
>this is expressed in n3 (and definite but not complete)
>
>{:X a :isLoved} log:forAll :X.
>
>we get (using euler proof mechanism)
>
>  {{:gregorian :grandparent :bret} log:implies
>   {:gregorian :parent :Y}} log:implies
>{:gregorian a :isLoved}.
>
>(have to think about quantifying that :Y ...)
>
> > And thus my hypothesis: datalog with only binary predicates is too
> > weak to talk about transitive relations.
>
>Maybe, maybe not ... I just don't know it for the moment (missing some gear
>:-)
>There is no problem if we add
>{{:X :parent :Y. :Y :parent :Z} log:implies {:X :grandparent :Z}} log:forAll
>:X, :Y, :Z.
>or some other kind of redundancy (whis is a good thing to have ...)
>
> >    -- sandro
>
>-- Jos De Roo, AGFA http://www.agfa.com/w3c/jdroo/
```
Received on Friday, 16 March 2001 12:48:47 GMT

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