Datalog With Only Binary Relations Is Too Weak

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

In Prolog (but not Datalog) you can say:
     parent(X, parent_of(X)) :- grandparent(X, Y).

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?

And thus my hypothesis: datalog with only binary predicates is too
weak to talk about transitive relations. 

   -- sandro

Received on Friday, 16 March 2001 07:30:39 UTC