Re: RDF and Logic Programming (and Hypergraphs)

Hi Jos,

> If we can't meet in Berlin, we can do it here!

Not attending ECAI 2000 in Berlin, you also missed Stefan's tutorial part
on RDF, but everything is online now (http://www.dfki.uni-kl.de/km/knowmark/).

> We see reification as a precise way to make associations between things.
> (Dis)joint parts of a graph could be reified (to things) to associate
> them with other things. It's a bit like (1 + 2) * 3 which is not the
> same as 1 + (2 * 3) or 1 + 2 * 3 (which is ambiguous).

Well, in general bracketing is needed for such binary operator uses, but what
about an n-ary, here ternary, form of (1 + (2 + 3))? For associative functions
people often prefer calls like (1 + 2 + 3) or -- without any 'grouping/reifying'
parentheses -- like +(1, 2, 3). Similarly, for relations, (1 < 2) & (2 < 3) may
be shortened to (1 < 2 < 3) or <(1, 2, 3).

One reason for binaries plus reifications, even in high-level languages, has
been their ease of visualization as graphs. Hence, in order to permit the direct
visualization of n-ary functions or relations, I suggest to look at hypergraphs,
where a hyperarc 'connects' n nodes (with n=2 being the special case of an arc)
and may carry a function/relation label. This could lead to an "N-ary RDF" much
like there are now "N-ary Description Logics" such as SHIQ/DLR (see third page of
http://sunsite.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-29/04-franconi.ps
from the ECAI KRDB 2000 Workshop, defining syntax and semantics of DLR).

In the "<" example, the binary-arc visualization of (1 < 2) & (2 < 3), i.e.

 ---     ---     ---
|   |   |   |   |   |
|   |   |   |   |   |
| 1 | < | 2 | < | 3 |
|   |-->|   |-->|   |
|   |   |   |   |   |
 ---     ---     ---

becomes the ternary-hyperarc visualization of <(1, 2, 3), i.e.
(hyperarcs 'cut' intermediate nodes)

 ---     ---     ---
|   |   |   |   |   |
|   |   |   |   |   |
| 1 | < | 2 |   | 3 |
|   |---------->|   |
|   |   |   |   |   |
 ---     ---     ---

In general, n-ary functions or relations cannot be so naturally aligned with
binary ones; e.g., replace +(A1, A2, A3) by voxel(X, Y, Z) or <(A1, A2, A3)
by between(Lower, Middle, Upper).

To visualize a general ternary Horn relationship like

between(mexico, usa, canada).   % The USA is between Mexico and Canada.

you can reify it into an auxiliary between1 node (below the reified between
relation) with auxiliary binary argI relations leading to the three argument
nodes:

                   ----------
                  |          |
                  |          |
                  | between  |
                  |          |
                  |          |
                   ---------- 
                       |
               relship |
                       V
                   ----------
                  |          |
                  |          |
      ------------| between1 |------------
     |            |          |            |
     | arg1       |          |            | arg3
     |             ----------             |
     |                 | arg2             |
     V                 V                  V
 --------           --------           --------
|        |         |        |         |        |
|        |         |        |         |        |
| mexico |         |   usa  |         | canada |
|        |         |        |         |        |
|        |         |        |         |        |
 --------           --------           --------

Or, you can just use a hyperarc:

 --------           --------           --------
|        |         |        |         |        |
|        |         |        |         |        |
| mexico | between |   usa  |         | canada |
|        |--------------------------->|        |
|        |         |        |         |        |
 --------           --------           --------

For diagrams contrasting TWO reified relationships with TWO hyperarcs
-- over the same nodes but in different orders -- see the second page
of my hypergraph paper (http://www.dfki.uni-kl.de/~boley/drlhops.ps)
in Fritz Lehmann's book "Semantic Networks in Artificial Intelligence".

> Also look to the power of a World Wide Web associative memory!

Yes, associations are usually binary -- and often unlabeled. But they
are not the same as logical relations, which can and should be directly
introduced in an n-ary manner (with n=2 always there as a special case).

> From an implementation point of view, reification is a reasonable thing.

I agree, and the binary case IS very important, and sometimes you MAY
want to use reification -- even in a generalized RDF giving you more
freedom on how to represent things logically.

Hoping you make further rapid progress with your Euler system,
Harold

Received on Wednesday, 13 September 2000 10:05:52 UTC