Re: Action 369 -- Look at property path tests

On 25/01/11 17:56, Matthew Perry wrote:
> 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

Matt,

:p* is defined to be :p{0} UNION :p+

The duplicate comes from the two parts

{ :a :p* ?x }
=
{ :a :p{0} ?x } UNION { :a :p+ ?x }

Data:
:a :p :b .
:b :p :c .
:c :p :a .


So the composition of patterns means that

{ :a :p{0} ?x } => ?x=:a
{ :a :p+ ?x } => ?x = :b, :c, :a

?x=:a occurs because of the two parts.  I don't think it directly 
violates the part you quote.  The algorithm is to put the endpoint of 
triple in the results, as the edge is traversed.

This could be changed in the spec: define an operator specifically for 
:p*, not making it the multi-set-union of other forms.

An effect of this is that same results come from:

:a :p :b .
:b :p :c .

i.e. cycle and a non-cycle with removal of a triple for the last hop, 
are the same.

I have no strong opinion either way - I'd like to see some more use cases.

- - - - - - - -

A separate issue is when there are multiple paths/loops in the graph.
If there are two loops, then :p+ leads to duplicates.

{ :a :p+ ?X }

:a :p :b .
:b :p :c .
:c :p :a .

:a :p :x .
:x :p :y .
:y :p :a .

------
| X  |
======
| :x |
| :y |
| :a |
| :b |
| :c |
| :a |
------

As with the comment from Jorge, we have to be careful about use with 
aggregates and literals.  This is not illustrated by this example unless 
literals can be subjects.  Ideally, I'd like to not design-out 
literals-as-subjects as RDF-MT already allows it, even if the syntaxes 
do not.

	Andy

Received on Saturday, 29 January 2011 17:00:37 UTC