more on labeled graphs

From: Pat Hayes <phayes@ai.uwf.edu>
Subject: Re: model theory for RDF/S
Date: Thu, 27 Sep 2001 19:42:28 -0500

> But why bother with all this? The concept of a labelled graph is 
> standard and uncontroversial, so this is one place where we can say 
> some mathematics in a reasonably intuitive way without sacrificing 
> either precision or readability by non-mathematicians.

I am aware of at least four versions of labeled directed graphs.  (This
ignores hypergraphs.)  These different versions of labeled graphs differ on
how they treat edges, and have different implications for the RDF model
theory.


Version 1:  Take a directed graph and attach labels to the nodes and/or edges.

I think of this version of labeled directed graphs as the standard version.
This version doesn't work for RDF, as it does not allow multiple edges
between nodes.  


Version 2: Take a directed multigraph and attach labels to the nodes and/or
	edges.  

This version works for RDF.  It corresponds to the reading of RDF where a
collection of triples is treated as a bag.  However, it does not work in
the model theory, as the subgraph lemma is not valid. 


Version 3: Take a directed graph and attach sets of labels to the nodes
	and/or edges.

This version would more-or-less work for RDF.  However, it is not what is
used in the model theory.


Version 4: Take a directed graph and modify the definition of edges from
	pairs to triples by adding the label.  Also add a label function to
	nodes.

This is (almost) the version used in the model theory.  I think that it has
all the appropriate characteristics.  

The definition of labeled graph used in the model theory has the extra
requirement that all nodes participate in at least one edge.  I don't think
that this matters for RDF.


One reason that I am being so picky about this is that I found some talks
on the W3C web site that simply state that the RDF data model is a directed
labeled graph, without any further qualification.

Peter F. Patel-Schneider

Received on Friday, 28 September 2001 10:55:53 UTC