Property Paths Update

On 16/03/2010 4:50 AM, Lee Feigenbaum wrote:
> Chime and Andy, I'd like to focus on HTTP Update and Property Paths
> today. I of course understand if the late notice makes it difficult for
> you to lead a discussion, but we'll do the best we can.

http://www.w3.org/2009/sparql/docs/property-paths/Overview.xml

Technical issues outstanding:



Summary of Proposals:
   Duplicates: allow them.
   Cycles: no duplicates of endpoints of operators
           whole path duplicates works out as composition of operators.

== Duplicates

Should, when there are acylic components, duplicates be supressed in 
simple property paths? (A simple property path being one that can be 
written with triple patterns only, give or take the duplicates)

Example:

:a foaf:knows :b .
:a foaf:knows :c .
:b foaf:knows :d .
:c foaf:knows :d .

   {?x foaf:knows{2} ?y}

be the same as

   { ?x foaf:knows ?z . ?z foaf:knows ?y }

or should the {2} form not contain duplicates.

{ ?x foaf:knows ?z . ?z foaf:knows ?y }
evaluates to:
----------------
| x  | z  | y  |
================
| :a | :c | :d |
| :a | :b | :d |
----------------

but
   {?x foaf:knows{2} ?y}
can be thought of as projecting away the ?z column making it:

-----------
| x  | y  |
===========
| :a | :d |
| :a | :d |
-----------
or applying a no duplicates rule:

-----------
| x  | y  |
===========
| :a | :d |
-----------

that is SELECT DISTINCT ?x ?y

** Proposal: allow duplicates.

The two forms are exactly the same answers.

== Paths I

What about

:a foaf:knows :b .
:b foaf:knows :a . # creates a loop

and the pattern:

?x foaf:knows{2} ?y

does the loop match? How many times?

Proposal: It does match

  :a  --foaf:knows--> :b --foaf:knows--> :a

and the same for
  :b  --foaf:knows--> :a --foaf:knows--> :b

leading to:

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

(starting at either :a or :b)

So the triple pattern and the property path versions are exactly the same.

* Proposal: duplicates

Follows from the two forms being exactly the same.

== Paths II

Now consider:

?x foaf:knows* ?y
?x foaf:knows{2,} ?y # 2,3,....

A "simple path" is in graph theory (usually) no repeated edges.

:a foaf:knows :b .
:b foaf:knows :a .

What happens here?

We don't want it to match infinitely many times but that is the naive 
extension from the ?x foaf:knows{2} ?y case.


** Proposal:
Need to treat the unbounded operators (*,+, {2,}) specially.
An unbounded operators only yields it's endpoints once.

This then makes Steve's example of

:x :p (1 2 2 3) .
and
    { :x rdf:rest*/rdf:first ?y }

work to give ?y = 1,2,2,3
because rdf:rest* is yielding endpoints once, not the whole pattern.

Warning: This leads to possible oddities:

Both
   :a foaf:knows{2,} ?y
   :a foaf:knows* ?y

then match with ?y=:a once (there are other matches)
but
   :a foaf:knows{2} ?y
gives ?y/:a matching twice.

If I read {2,} as
   "* but at least 2"
then personally I don't find that too strange and I prefer that simple 
property paths are exactly their triple pattern equivalence.

I want the case of { :x rdf:rest*/rdf:first ?y } to work.

http://en.wikipedia.org/wiki/Graph_(mathematics)
http://en.wikipedia.org/wiki/Path_(graph_theory)

This needs checking that it works out.


== To do:

Check the "simple graph paths" option for unbounded operators.

Integrate with the query doc
   Redo examples
     - don't differentiate simple and complex to much in examples
       (WG advice)
   Section on property paths
   Integrate with the SPARQL grammar
   Algebra for paths.
   Evaluation for paths

Received on Tuesday, 16 March 2010 09:39:32 UTC