# Re: Subgraph results

From: Pat Hayes <phayes@ihmc.us>
Date: Wed, 12 May 2004 17:34:30 -0500
Message-Id: <p06001f13bcc84a2bb68b@[10.0.100.76]>
To: "Rob Shearer" <Rob.Shearer@networkinference.com>
Cc: RDF Data Access Working Group <public-rdf-dawg@w3.org>
```>Is the term "subgraph" (used in requirement 3.4) formally defined
>anywhere?

Yes.

Here's a summary of the RDF terminology from
http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/#section-graph-equality

and
http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#graphdefs.

URIrefs, literals and blank nodes are mutually disjoint; in other
words, whatever blank nodes are, they aren't urirefs or literals.

A triple is a 3-tuple of the form (uriref or blank node) + uriref +
(uriref or blank node or literal)

An RDF graph is a set of triples. (It is not a graph in the sense
used in graph theory. I once checked it out and I think it is
technically a labelled multi-pseudo-digraph with a unique node
labelling. Or something close to that, anyway. Whatever.) (So why did
we call them 'graphs'? Because they look like that when you draw a
picture, OK ?? Why do you ask so many questions??? )

Subgraph means subset of a set of triples.

(The terms 'edge', 'label' and 'vertex' are not used.  'Path' could
be defined but doesn't seem to be a useful notion.)

An instance of a graph is any graph obtained from it by substituting
urirefs, blank nodes or literals for blank nodes in a systematic way.
If the substitution replaces blank nodes by blank nodes in a 1:1
fashion, so the substitution is invertible and the instance is also a
generalization, then the graph and the instance are equivalent, i.e.
isomorphic, cf.
http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/#section-graph-equality
Equivalent graphs are often treated as the same graph (using what in
mathematics is called a 'familiar abuse of terminology'.)

Generalization is the inverse of instance.

Merging is taking a union of two graphs after replacing one of them
by an equivalent graph so as to avoid any accidental collisions of
blank nodes.

There is a result about basic RDF inference: A graph G implies
another graph H just when H is a generalization of a subgraph of G.

(Strictly speaking, RDF inference also requires that literals typed
with rdf:XMLLiteral are appropriately recognized and that urirefs
used as properties are of the right rdf:type: see
http://www.w3.org/TR/2004/REC-rdf-mt-20040210/#RDFRules for gory
details.)

Hope this is some help.

Pat

--
---------------------------------------------------------------------
IHMC	(850)434 8903 or (650)494 3973   home
40 South Alcaniz St.	(850)202 4416   office
Pensacola			(850)202 4440   fax
FL 32501			(850)291 0667    cell
phayes@ihmc.us       http://www.ihmc.us/users/phayes
```
Received on Wednesday, 12 May 2004 18:34:35 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 15:00:43 UTC