RE: Subgraph results

Rob,

When I have been using the term I mean a subset of the edges of the RDF
graph.  As RDF Graphs are restricted in what they can be (not the complete
defintion in a graph theory book), the subgraph = subset of edges is
similarly restricted.  I personally don't imply "connected" in the term
"subgraph" but I know this does arise in discussions elsewhere.

The other thing is that what matters is not "being a subgraph of" but being
"isomorphic to a subgraph of" because of bNodes but the language gets a
little heavy to say that everytime.

Googling ... getting sidetracked ...

http://www.colorado.edu/education/DMP/def.html#s
DMP - Discrete Mathematics Project
===> (fixing the typo)
"""
Subgraph 
A subgraph of a graph is itself a graph in which all of the edges and
vertices are contained within the original graph.
"""

As RDF does not allow nodes (vertices) without edges (triples, statements),
this seems to say that the usage is the same here.

http://www2.parc.com/istl/groups/hdi/sensemaking/glossary.htm
===>
"""A connected subset of a graph."""

And then goes on to talk about graphs for sensemaking.

More inline.

	Andy

-------- Original Message --------
> From: public-rdf-dawg-request@w3.org <>
> Date: 11 May 2004 18:47
> 
> Is the term "subgraph" (used in requirement 3.4) formally defined
> anywhere? 
> 
> I'm trying to find a way to get around my objections to this
> requirement; perhaps making it clear that the requirement is
> about result formatting and not underlying structure would help:
> 
> "It must be possible for query results to be formatted as a
> subgraph of the original queried graph."

Is this touching on the fact that it is only useful to worry isomorphism and
not equality?  It seems to me that "structure" is important so that
subgraphs can be passed on to other systems.

Some of this goes back to:
http://www.w3.org/TandS/QL/QL98/pp/enabling.html
And also descirptions like t"graphs with holes"  meaning named variables for
slots in the triples.

> 
> This changes "returned" to "formatted", uses "a subgraph"
> instead of "the subgraph",

Talking about "a subgraph" is better.  I won't want to imply the necessity
to find "the subgraph" for some virtual triples cases, like when that's
infinite.

In a query on an RDF graph (just the RDF graph), there is one particular
subgraph of interest - the one that the query triple patterns match.  Its
the same as (isomorphic to) the merge of each of the matching subgraphs.
Moving to virtual triples is not trivial and there are choices, based on,
amongst other things, whether the predicates/classes in the query are
returned or the ones on the graph, and this is only at the RDFS level.  The
intention is returning the information the query needed to match - we have
to find a away to express that but maybe not in the requiremtn and leave it
for further work in the WG.

> and drops "that the query
> matches". The original way the requirement was worded it
> seemed that the query processor would need to somehow figure
> out all the pieces of the original graph which had any
> relevence to the "matching" process, and that whole process
> is only meaningful for completely trivial query languages.
> 
> I feel very strongly that we should keep deciding on the
> answers separate from the result format.
> 
> 
> (All that said, I'm still not comfortable supporting even my
> reworded requirement without a real definition for "subgraph".)

Received on Tuesday, 11 May 2004 15:58:49 UTC