- From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
- Date: Fri, 28 Sep 2001 10:57:36 -0400
- To: phayes@ai.uwf.edu
- Cc: www-rdf-logic@w3.org

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