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

Re: property paths three more test cases pp13, pp14, pp15

From: Andy Seaborne <andy.seaborne@epimorphics.com>
Date: Sun, 16 Jan 2011 14:43:17 +0000
Message-ID: <4D330405.3080505@epimorphics.com>
To: Axel Polleres <axel.polleres@deri.org>
CC: SPARQL Working Group <public-rdf-dawg@w3.org>


On 11/01/11 12:54, Axel Polleres wrote:
> catching up...
> Thanks for the explanations given the said below, did you update pp16 and/or shall we add your example as additional test case?

I haven't touch the tests.  Feel free to add a new one.

	Andy

>
> best,
> Axel
>
> On 21 Dec 2010, at 21:37, Andy Seaborne wrote:
>
>>
>>
>> On 21/12/10 10:31, Andy Seaborne wrote:
>>>
>>>
>>> On 20/12/10 17:23, Axel Polleres wrote:
>>>> Steve,
>>>>
>>>> I added a new use case pp16 along the lines you suggest, see details
>>>> below.
>>>>
>>>> On 20 Dec 2010, at 16:46, Steve Harris wrote:
>>>>
>>>>> I think pp14 would be more enlightening if the pp14.ttl included a
>>>>> disconnected foaf:knows graph, and some triples using another
>>>>> predicate. Something like:
>>>>>
>>>>> @prefix :<http://example.org/>  .
>>>>> @prefix foaf:<http://xmlns.com/foaf/0.1/>  .
>>>>>
>>>>> :a foaf:knows :b .
>>>>> :b foaf:knows :c .
>>>>> :d foaf:knows :e .
>>>>> :f foaf:name "test" .
>>>>> :a foaf:homepage :h .
>>>>>
>>>>> Even after Axel's proposed changes I find the wording a bit
>>>>> impenetrable, though admittedly I haven't had time to study the algebra.
>>>>>
>>>>> Axel, can you tell mw what results you'd expect from pp14.rq with
>>>>> that data?
>>>>>
>>>>
>>>> your data returns, according to my understanding of the algebra:
>>>>
>>>> -------------------
>>>> | X | Y |
>>>> ===================
>>>> | :a | :a |
>>>> | :a | :b |
>>>> | :a | :c |
>>>> | :b | :b |
>>>> | :b | :c |
>>>> | :c | :c |
>>>> | :d | :d |
>>>> | :d | :e |
>>>> | :e | :e |
>>>> | :f | :f |
>>>> | :h | :h |
>>>> | "test" | "test" |
>>>> -------------------
>>>>
>>>> I would, BTW, rather keep the simple use case pp14 "as is", and added
>>>> a more complex one having your extension, as well as
>>>> duplicate paths and cycles as a separate new use case:
>>>>
>>>> @prefix :<http://example.org/>  .
>>>> @prefix foaf:<http://xmlns.com/foaf/0.1/>  .
>>>>
>>>> :a foaf:knows :b .
>>>> :b foaf:knows :c .
>>>> :a foaf:knows :c .<-- duplicate path
>>>> :d foaf:knows :e .
>>>> :e foaf:knows :f .
>>>> :f foaf:knows :e .<-- cycle
>>>> :f foaf:name "test" .
>>>> :a foaf:homepage :h .
>>>>
>>>> I am not sure about the cycle handling ATM, so I can only give the
>>>> result from ARQ (which is what I checked in under pp16.srx for now):
>>>
>>> Looks like a bug to me.
>>>
>>> I want to rewrite the path evaluation to follow the spec - it predates
>>> the spec at the moment.
>>>
>>> Andy
>>
>> Working through a cut down example, I seem to get the right answers:
>>
>> == Data
>>
>> @prefix :<http://example.org/>  .
>> @prefix foaf:<http://xmlns.com/foaf/0.1/>  .
>>
>> :d foaf:knows :e .
>> :e foaf:knows :f .
>> :f foaf:knows :e .
>>
>> == Query
>> SELECT * { ?x foaf:knows* ?y }
>>
>> Write out * as {0} UNION + and label the branches:
>>
>> PREFIX :<http://example.org/>
>> PREFIX foaf:<http://xmlns.com/foaf/0.1/>
>>
>> SELECT *
>> {
>>     { BIND ("0" as ?A) ?x foaf:knows{0} ?y . }
>>     UNION
>>     { BIND ("+" as ?A) ?x  foaf:knows+ ?y . }
>> }
>>
>>
>> == Result
>> -----------------
>> | A   | x  | y  |
>> =================
>> | "0" | :d | :d |
>> | "0" | :f | :f |
>> | "0" | :e | :e |
>> | "+" | :d | :e |
>> | "+" | :d | :f |
>> | "+" | :d | :e |
>> | "+" | :f | :e |
>> | "+" | :f | :f |
>> | "+" | :e | :f |
>> | "+" | :e | :e |
>> -----------------
>>
>> which explains the (:e, :e) duplicate, once due to {0} and once due to +
>>
>> The 2 ("+", :d, :e) is an effect of how we control cycles by detecting
>> triples traversed, not node checking.
>>
>> == Data
>> :d foaf:knows :e . # T1
>> :e foaf:knows :f . # T2
>> :f foaf:knows :e . # T3
>>
>>   From d:
>>
>> Step 1: T1 =>  adds the (:d, :e) pair
>> then
>> Step 2: ->T2->T3 =>  adds the (:d, :e) pair
>>
>> In step2 , it stops because T2 would be traversed again.  The path
>> T1->T2->T3 only crossed triples once, but finds (:d, :e) twice in the
>> process. There are two ways that :d is connected to :e (1-step and
>> 3-step paths).
>>
>> If distinct is added then "node tracking answers == triple tracking
>> answers" (I think :-)
>>
>> Triple tracking causes paths to be found (scope later for path variables
>> and test on them), not nodes visited.
>>
>>          Andy
>>
>>
>
Received on Sunday, 16 January 2011 14:43:54 GMT

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