Re: Subgraph results

>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