[TF-PP] Worked examples of cardinality for :p{2} and :p+

This message is to make sure we are all aware about cardinality that 
:p{2} and :p+ can encounter.

Test cases attached (what are we doing about test cases?)

The diamond shape of diagram 1 [*] is the triples:

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

Pattern: { :a :p{2} ?z }

has solutions
?z=:z
?z=:z

and it's the same as

{ :a :p _:v . _:v :p ?z }

or SELECT ?z { :a :p ?v . ?y :p ?z }

In terms of cardinality for 2-step paths, it's not the same as:

Patterns: { :a :p+ ?z }
which has solutions

?z=:b
?z=:c
?z=:z

the point being you get ?z=:z only once in the { :a :p+ ?z } case.

but is the same as:
{ :a :p/:p+ ?z }

?z=:z
?z=:z

by combination of the first ":p" (two places: :b, and :c) then steps of :p+

This is related to loop avoidance in :p+.  If it's a breadth first 
search, it avoids visiting a node if it's already seen it.

This makes it consistent with:

:a :p :b .
:b :p :z .
:a :p :c .
:c :p :z .
:z :p :X .

which is the diamond with an extra arc from :z,

Pattern: { :a :p+ ?z }

?z=:c
?z=:z
?z=:X
?z=:b

only one ?z=:X, despite there being 2 routes there
while { :a :p{3} ?z } gets:

?z=:X
?z=:X

because it is the same as the BGP expansion of the path expression.

This makes sense with loops as well: diagram 2 adds a loop to :c

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

Pattern: { :a :p+ ?z }
?z=:b
?z=:c
?z=:z

whereas on the diamond+loop:
Pattern: { :a :p{2} ?z }
?z=:c
?z=:z
?z=:z

It seems much better to make :p+ treat DAGs (directed acyclic graphs) 
and cycles in graphs the same and get the cardinalities above. 
Implementing "+" only requires keeping a track of the nodes visited, not 
the path used to get to the node (and I'm not convinced it would work 
out either because of pathe with acyclic paths and cycles in together).

 Andy

[*] http://lists.w3.org/Archives/Public/public-rdf-dawg/2010AprJun/0275.html