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@[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 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:19 GMT