W3C home > Mailing lists > Public > www-archive@w3.org > April 2012

Re: SPARQL WG action on property paths

From: Marcelo Arenas <marcelo.arenas1@gmail.com>
Date: Thu, 5 Apr 2012 08:16:48 -0400
Message-ID: <CA+7aXj5cWqtMUg-B1amNQdZWKkvTwRXRyTRmnoafjk59moWgZg@mail.gmail.com>
To: Lee Feigenbaum <lee@thefigtrees.net>
Cc: W Martens <martens.wim@gmail.com>, jorge.perez.rojas@gmail.com, jeen.broekstra@gmail.com, Sebastián Conca <sconca87@gmail.com>, www-archive@w3.org, Axel Polleres <axel@polleres.net>
Hi Lee,

2012/4/5 Lee Feigenbaum <lee@thefigtrees.net>:
> 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
> http://lists.w3.org/Archives/Public/public-rdf-dawg-comments/2012Feb/0029.html
> .

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
unnatural.

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).

Cheers,

Marcelo



>
>
> 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<lee@thefigtrees.net>
>>  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:
>>>
>>> http://lists.w3.org/Archives/Public/public-rdf-dawg/2012JanMar/0285.html
>>> http://lists.w3.org/Archives/Public/public-rdf-dawg/2012JanMar/0286.html
>>>
>>> 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

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 14:44:03 UTC