W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > October to December 2010

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

From: Andy Seaborne <andy.seaborne@epimorphics.com>
Date: Tue, 21 Dec 2010 21:37:19 +0000
Message-ID: <4D111E0F.60902@epimorphics.com>
To: SPARQL Working Group <public-rdf-dawg@w3.org>


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 Tuesday, 21 December 2010 21:37:55 GMT

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