W3C home > Mailing lists > Public > public-rdf-dawg-comments@w3.org > February 2010

property paths & cycles

From: Jeremy Carroll <jeremy@topquadrant.com>
Date: Wed, 17 Feb 2010 11:05:26 -0800
Message-ID: <4B7C3DF6.3010506@topquadrant.com>
To: public-rdf-dawg-comments@w3.org

Hi Andy + others

this is a comment on
from an implementation perspective on the following text:

/elt{n,m}/ A path between n and m occurrences of /elt/.

Cycles in paths are possible and are handled.


Paths do not need to be anchored at one end or the other,

What I take that to mean is that if my data is

eg:a eg:p eg:a
eg:a eg:p eg:b

then the path [ eg:p {3, 7 } ] links eg:a with both eg:a and eg:b

If that is the intent, I think an example would help.

Practically I wonder if it may be more useful to prohibit cycles, i.e. 
property paths are simple paths in the graph theoretic sense (using 
terminology from Wikipedia [1]), i.e. do not contain the same node 
twice. In this case the only path in [ eg:p {1,} ]  is one from eg:a to 
eg:b. (the zero length path from eg:a to itself is still there in [ eg:p 
{0, } ] .. in fact I would be inclined to require n>0, or at least if 
n=0 then at least one end of the path should be anchored (do we really 
want ?v eg:p {0} _ to select all the nodes in the graph - this concept 
is not even well-defined in RDF, would an implementation be incorrect to 
return a node that did not occur in any triple in the graph?)

The practical value of requiring simple paths is to do with cyclic 
subClassOf structures. I see no value at all in allowing code to go 
round these cycles.
In practice to implement the m=infinity case, you need to implement an 
occurs check (in the somewhat naive approach I am taking) because of the 
danger of loops in the data.

(I am implementing the first quoted line, with simple paths - but not in 
a SPARQL framework, but I referred to this draft to frame the task)



(This is not intended as a formal comment, and can be excluded from W3C 
process requirements)
Received on Wednesday, 17 February 2010 19:06:30 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 20:52:10 UTC