W3C home > Mailing lists > Public > w3c-rdfcore-wg@w3.org > October 2002

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>
CC: w3c-rdfcore-wg@w3.org

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."

It's this business about representing multiple relations in the same 
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.
> Readers get consistent terminolog.
> 
> Version 2, less work overall, readers get exposure to the variety of 
> terminology used in RDF community to describe the same thing.
> 
> 
> Comments?
> 
> 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 EDT

This archive was generated by hypermail pre-2.1.9 : Wednesday, 3 September 2003 09:52:25 EDT