# more on labeled graphs

From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
Date: Fri, 28 Sep 2001 10:57:36 -0400

Message-Id: <20010928105736E.pfps@research.bell-labs.com>
```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.