property paths & cycles

Hi Andy + others

this is a comment on
http://www.w3.org/TR/2010/WD-sparql11-property-paths-20100126/
from an implementation perspective on the following text:

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

and
[[
Cycles in paths are possible and are handled.
]]

and

[[
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)

Jeremy


[1]
http://en.wikipedia.org/wiki/Path_%28graph_theory%29


(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