W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > January to March 2011

Re: Review of Property Path Sections in Query Doc

From: Andy Seaborne <andy.seaborne@epimorphics.com>
Date: Mon, 28 Feb 2011 11:21:47 +0000
Message-ID: <4D6B854B.2000304@epimorphics.com>
To: Matthew Perry <matthew.perry@oracle.com>
CC: W3C SPARQL Working Group <public-rdf-dawg@w3.org>


On 21/02/11 19:41, Matthew Perry wrote:
> Hi Andy,
>
> I went through the property path sections of the query doc. Overall, the
> textual descriptions of each property path operator sound good. Some
> more detailed comments are below.
>
> Section 9.3
>
> Evaluation of [a property path expressions => property path expressions]
> can lead to duplicates in the results.
>
> Where the query matches on arbitrary length paths, each cycle is
> considered at most once by stopping if [a triple => an RDF term] in the
> data would be a matched again in the evaluation of the + property path
> operator.

Done thanks.

>
> Section 18.4
>
> The arbitrary length path operators are described in Section 18.4 as
> allowing the start node of a path to also be the end node of the path
> (i.e. a cycle back to the starting point is allowed). From my
> understanding of the evaluation semantics in Section 18.5, the ALP
> Function will not allow this loop back to the starting point because the
> starting node is added to V in the first step, so ALP will return
> without adding the starting point when it is encountered at the end of a
> loop.

For the case of "*" (ZeroOrMorePath), the initial point is added 
immediately in the first call of ALP because V = empty set.

For the case of "+" (OneOrMorePath), one step of ALP is done with no 
adding of the node to the vertex set, and so if it loops back, it's in 
once only.

A loop back to the starting point is allowed (i.e. matched) because ALP 
only follows possibilities.  It does not backtrack on negative 
possibilities although the underlying path might.

ZeroOrMorePath(:x, :p, :x) =>
   ZeroOrMore(:x, path, var) =>
   ALP(:x, path) =>
   ALP(:x, path, {}, {}) =>
     includes :x immediately.

OneOrMorePath(:x, :p, :x) =>
   OneOrMorePath(:x, path, var) =>
     Do path once to get X = :n1, :n2, etc.
     ALP(:n1, path) =>
     ALP(:n2, path, {}, {}) =>
       includes :n2 if loops back.

> I don't understand the (term, path, term) definitions:
> { { } } if (v,y:var) in eval(D(G), ZeroOrMore(x, path, y); card[{ }] = 1

Multisets are defined as a set of elements and a cardinality of the 
elements.

{ { } } is a set of one element, which is itself the empty set of 
bindings (no columns).   Nothing to do with SPARQL patterns.

The result of "SELECT * {}" - the two uses of "{}" for SPARQL patterns 
and sets/mulitsets does make this confusing.  I hope they are never 
mixed in the same expression.  If there is a way to make this clearer, 
please suggest it.


> Thanks,
> Matt

	Andy
Received on Monday, 28 February 2011 11:22:23 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:45 GMT