# Re: Abstract syntax - graph or triples

From: Frank Manola <fmanola@mitre.org>
Date: Mon, 14 Oct 2002 20:59:22 -0400
Message-ID: <3DAB686A.3010208@mitre.org>
To: Jeremy Carroll <jjc@hplb.hpl.hp.com>

```
Jeremy--

I seem to recall this "graph vs. triples" business being mentioned
during the last teleconference, but maybe I'm wrong, and in any case I
don't remember what happened. Speaking as Primer editor, consider this a
vote for option 2.  I'd hate to have to rewrite all the text that
describes the drawn graphs.  Besides, I think the graph model is
helpful, and having multiple ways of looking at the same thing is often
useful in tutorial material.

At a more fundamental level, I think part of our problem in trying to
match up graph concepts and triple (or relation) concepts is that we
didn't go far enough in any of our material in describing the connection
between a graph-theoretic type of model and a relational type of model
(we're using triples to represent the tuples in a binary relation, where
we name the relation in each tuple).  It might be helpful to look at
John Sowa's mathematical background article at
http://users.bestweb.net/~sowa/misc/mathw.htm, in particular section 6
on "representing relations by graphs".

In particular, he starts off by saying "Graphs and dyadic relations are
mathematical structures that look different, but they can represent the
same information in logically equivalent ways. Historically, graphs are
more closely associated with geometric properties that can be seen from
diagrams, and relations are associated with more abstract mathematics
and logic. But every dyadic relation can be represented as a graph, and
every graph defines a dyadic relation."  So far this is more-or-less
conventional graph theory (where a graph is defined by a set of vertices
and a relation defined on the set of vertices).

The particularly important part follows, namely:

"Although every dyadic relation can be represented by a graph, some
extensions are necessary to represent multiple relations in the same
graph. A common technique is to label the arcs of a graph with the names
of the relations they represent. Informally, a labeled graph can be
viewed as a set of graphs * one for each relation * overlaid on top of
one another with the labels showing which relation each arc has been
derived from."

graph (which is what we're trying to do), that's been somewhat missing
from a lot of our graph-theoretic discussions.  I think something like
this could help clarify the relationship between a graph-theoretic
approach (which conventionally deals only with *one* relation), a model
that consists of multiple relations having sets of pairs as extensions
[that's if you don't discuss classes as being 1-ary "relations"], and
the triple model (which is another way of writing the relational model).

--Frank

Jeremy Carroll wrote:

>
>
> I have slowly been having a conversation with Pat about the mismatch
> between the abstract syntax document's use of labelled nodes within a
> graph, and the model theory which uses literals and uris directly within
> triples.
>
> Pat seems to have argued me round to his position (I am not quite sure
> how :) ).
>
> I had wanted to know from the other editors (Dave (syntax and ntriples),
> Frank (primer) and DanBri (vocab)) as to what difficulties two possible
> versions of the abstract syntax would cause. I would also appreciate the
> series editor's input here since it seems to be about the global style
> of our recommendation.
>
> Version 1 - labels out, triples as way forward.
>
> this would follow recent model theory documents in describing the RDF
> data model as a set of triples; an extreme version would not even use
> the graph language at all, or would define an "RDF graph" as a set of
> triples.
> With this language other docs should not refer to the "label on the
> subject node" or the "URI label" or similar; we may choose to revisit
> use of words like arc or edge and replace them all with triple.
>
> Version 2 - mix and match
>
> This would have the version 1 text, to connect with the model theory,
> and sketch the isomorphism to directed graphs with labelled nodes and
> labelled edges. This would allow a promiscuous use of any graph
> theoretic or triple oriented language in all the other documents.
>
> Pros and Cons:
>
> Version 1, clearer, less work for me, more work for other editors.
>
> Version 2, less work overall, readers get exposure to the variety of
> terminology used in RDF community to describe the same thing.
>
>
>
> Jeremy
>
>
>
>

--
Frank Manola                   The MITRE Corporation
202 Burlington Road, MS A345   Bedford, MA 01730-1420
mailto:fmanola@mitre.org       voice: 781-271-8147   FAX: 781-271-875
```
Received on Monday, 14 October 2002 20:43:31 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 14:54:01 UTC