Re: Action 369 -- Look at property path tests

Hi Andy,

Thanks for the explanation. I completely understand and agree with the cycles in fixed-length property paths.

My concern is with the arbitrary-length paths. I would strongly prefer to have a purely node-marking algorithm instead of triple marking. The pure node marking seems to better match the resolution we passed back in June: http://www.w3.org/2009/sparql/meeting/2010-06-01#resolution_5. (The two solutions with cycles both repeat nodes).

PROPOSED: The cardinality of solutions to fixed-length paths
is the same as the cardinality of solutions to the path expanded into
triple patterns (with all variables projected);*the cardinality of
solutions to variable-length paths is the cardinality of solutions
via paths that do not repeat nodes;*  the cardinality of solutions to
paths combining fixed and variable length (elt{n,} ) is a combination
of the fixed definition plus the variable definition for paths longer
than the fixed length.

Thanks,
Matt

On 1/25/2011 12:02 PM, Andy Seaborne wrote:
>
>
> On 25/01/11 14:41, Matthew Perry wrote:
>> For pp16 and pp25, these paths repeat a node (i.e. contain a cycle). I
>> thought we were using a node marking algorithm to prevent cycles.
>
> We currently have a triple marking algorithm which puts in the end node which means you can get a duplicate from a cycle.
>
> We could change ArbitraryLengthPath to also record node passed through.
>
> For me, a consistent view is more important.  Also, with cycles
>
> Data: (DAG, not cycle).
>
> :a :p :b .
> :b :p :z .
>
> :a :p :c .
> :c :p :z .
>
> and
>
> { :a :p/:p ?X }
> { :a :p ?v .?v :p ?X } # SPARQL 1.0
>
> have the endpoint twice.
>
> { :a :p* ?X } has :z twice.
>
> { :a :p/:p ?X }
>
> Data: cycle:
>
> :a :q :b .
> :b :q :c .
> :c :q :a .
>
> and { :a :q+ ?X }
> does not have a duplicate but :q* does because it includes the starting point and :q* = :q{0} UNION :q+
>
>
> > 2) pp16 -- I don't understand why the path d --> e --> f --> e is included.
>
> pp16 is a bit unnatural if read with interpretation of the meaning of the property: find me everyone ?X knows, recursively is "+", not "*"
>
> Data contains:
>
> :d foaf:knows :e .
> :e foaf:knows :f .
> :f foaf:knows :e .
>
> { ?X foaf:knows* ?Y } =
>    { ?X foaf:knows{0} ?Y } UNION { ?X foaf:knows+ ?Y }
>
> { ?X foaf:knows{0} ?Y } ==> ?X=:d, ?Y=:d
> { ?X foaf:knows+ ?Y }   ==> ?X=:d, ?Y = :e, ?f then :e again as
> the triple ":f foaf:knows :e" is travered, the endpoint included and the cycle stops.
>
> Any loop where ArbitraryLengthPath is not starting in the cycle is going to give a duplicate and it differenates from the same without the final step (no cycle).
>
> > 3) pp25 -- I don't understand why the path a --> c --> c is included.
>
> :a :p :c .
> :c :p :c .
>
> so :c goes to :c (a cycle of one triple).
>
>     Andy