W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > April to June 2004

Re: Subgraph results

From: Pat Hayes <phayes@ihmc.us>
Date: Wed, 12 May 2004 17:34:30 -0500
Message-Id: <p06001f13bcc84a2bb68b@[]>
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


Here's a summary of the RDF terminology from 


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

Hope this is some help.


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