Re: SPARQL WG action on property paths

Hi Lee,

2012/4/5 Lee Feigenbaum <>:
> Hi Wim,
> Unfortunately, I'm not in a position to represent the entire group in
> discussing the various motivations behind this particular design decision.
> As I told Marcelo, if the group proceeds with this design, you will of
> course have every opportunity to share comments on it with the group and to
> object to the specification proceeding should you wish.
> For now, I'm simply seeking to understand if the design that the group has
> agreed on addresses your concern about property paths being "hard to
> evaluate" as you expressed in
> .

Under this semantics, property paths can be evaluated more efficiently
(in fact, a property path expression of the form p* can be evaluated
over an RDF graph G in time O(|G|x|p*|) by using the usual algorithm
based on the cross product of automata). However, I don't think that
this is a good solution as the semantics is, in my opinion, rather

If I understand correctly the rationale between this new semantics,
only a limited form of counting is kept to generate a language that
can be evaluated more efficiently and that can handle some specific
use cases. But then I don't understand why counting is kept when
evaluating operators /, |, !, as these use cases can be easily handled
by using a pure existential semantics for property paths, and why {n},
{n,m}, {n,}, {,m} are removed, as they can be evaluated efficiently
(as pointed out by Wim).



> On 4/5/2012 3:51 AM, W Martens wrote:
>> Dear Lee,
>> thank you very much for keeping us up to date. This is really appreciated.
>> I have read the proposal and I also already read Marcelo's answer.
>> I would like to make two remarks:
>> (1) My first remark is an agreement to what Marcelo says. I also think
>> that it is unnatural to say that one needs to count for some operators
>> and one does not need to for others. In his example, Marcelo really
>> hits the nail on the head by showing how the use cases can be easily
>> addressed by pure existential semantics.
>> (2) Furthermore, I think that it would be a pity to implement 6.D.,
>> that is, to remove the {} forms: {n}, {n,m}, {n,}, {,m}. The reason is
>> that these operators make property paths quite a bit more powerful and
>> can be implemented at virtually no extra cost, by a very simple
>> algorithm (which is presented in the PODS 2012 paper).
>> Best regards,
>> Wim
>> On Tue, Apr 3, 2012 at 5:19 PM, Lee Feigenbaum<>
>>  wrote:
>>> Hi Wim, Jorge, Jeen, Marcelo, and Sebastian,
>>> (Please note that this is not an official working group response to your
>>> respective comments on property paths in the current SPARQL 1.1 Query
>>> last
>>> call working draft.)
>>> I want to thank you all again for your research, experiences,
>>> suggestions,
>>> and comments on SPARQL 1.1 property paths. They've been very valuable to
>>> the
>>> working group.
>>> The group has spent some time in the past few weeks considering various
>>> options in an attempt to address the implementation and evaluation
>>> challenges that you have all raised while still respecting our group's
>>> schedule, implementers' burdens, and the use cases we've identified for
>>> property paths.
>>> Today, we reached consensus within the group on an approach that we feel
>>> addresses your concerns while still leaving room for implementation
>>> experience going forward to inform additional design decisions in the
>>> future.
>>> We haven't yet worked this design into the query document, which is why
>>> this
>>> isn't an official WG response to your comments. Yet before we go ahead
>>> and
>>> publish a new Last call, we'd like to know if you support this new design
>>> and if you believe that it does indeed address your comments.
>>> The design is summarized in these two emails by Andy Seaborne:
>>> I'd very much appreciate it if you can take a look at this and let me
>>> know
>>> what you think.
>>> thanks,
>>> Lee

Received on Thursday, 5 April 2012 12:17:17 UTC