# Datalog With Only Binary Relations Is Too Weak

From: Sandro Hawke <sandro@w3.org>
Date: Fri, 16 Mar 2001 07:30:00 -0500
Message-Id: <200103161230.HAA02439@hawke.org>

[ 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

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 22:45:36 UTC