RE: [AccessingRdfLists] relationship with property paths?



> -----Original Message-----
> From: Lee Feigenbaum [mailto:figtree@gmail.com] On Behalf Of Lee
> Feigenbaum
> Sent: 17 March 2009 18:06
> To: Seaborne, Andy
> Cc: SPARQL Working Group
> Subject: Re: [AccessingRdfLists] relationship with property paths?
> 
> Seaborne, Andy wrote:
> 
> > That's a slight catch to know about with a query like:
> >
> > PREFIX  rdf:    <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
> > SELECT * { ?list rdf:rest*/rdf:first ?member }
> >
> > Because if the data is:
> > ---- Data:
> > ("A" "B" "C") .
> >
> > Which is in triples:
> > ---- Same data:
> > _:b1      rdf:first  "A" .
> > _:b1      rdf:rest  _:b2 .
> > _:b2      rdf:first  "B" .
> > _:b2      rdf:rest  _:b3 .
> > _:b3      rdf:first  "C" .
> > _:b3      rdf:rest  rdf:nil .
> > ----
> >
> > The results are:
> >
> > -----------------
> > | list | member |
> > =================
> > | _:x0 | "B"    |
> > | _:x0 | "C"    |
> > | _:x1 | "A"    |
> > | _:x1 | "B"    |
> > | _:x1 | "C"    |
> > | _:x2 | "C"    |
> > -----------------
> >
> > That's 3*"C", 2*"B" and 1*"A" because the tail of the RDF list is
> itself a list.
> 
> Oops.
> 
> > If ?list is bound it would work.
> 
> ...which it probably is in many (most?) examples of this.
> 
> > As would:
> > SELECT DISTINCT ?member { ?list rdf:rest*/rdf:first ?member }
> >
> > including as a sub-query.
> 
> Ah, I see.
> 
> Andy, ARQ returns the list items in order when you use list:member,
> right? If we were to defer on this issue in favor of property paths,
> that might be a point in favor of some solution to the issue that David
> Newman rose on the teleconference earlier: is there a way with property
> paths to specify that the results should come back in an order that's
> related to where things appear in the matched path?
> 
> Lee


ARQ does happen to return items from a list in order and that order gets preserved usually but it's fortuitous - people write queries in a certain way that causes it to happen.  The actual property function does find the list members and generate the bindings in order. But it also relies on another aspect of ARQ - most subsequent operations when used with an in-memory graph do not reorder the intermediate results.   It also happens to be true with a part of the form above because the path is linear.

But consider:

SELECT DISTINCT ?member 
{ 
  <#me> :someList ?list .
  ?list rdf:rest*/rdf:first ?member 
  ?member foaf:name "FRED"
}

In this case, a processor might well decide to look up ?member foaf:name "FRED", do the first triple pattern and  then do the list part as checking membership.  It might not come out in list order .  This does not currently happen in ARQ but only because the optimization across both paths and triple patterns is not aggressively reordering - yet.

If it's written: 

SELECT DISTINCT ?member 
{ 
  ?member rdfs:label "Talented"
  <#me> :someList ?list .
  ?list rdf:rest*/rdf:first ?member 
}

It might well be unordered on ?member.

Such ordering isn't specified in SPARQL/2008 - the only way to guarantee it is to have an ORDER BY clause at the level of the output and to include something to sort by in the output.

An idea: 
   Replace * with {?len} and capture the length

(lots of details - which length? Only shortest possible? What about two routes, same length through different intermediate graph nodes?) 

SELECT DISTINCT ?member 
{ ?list rdf:rest{?length}/rdf:first ?member }
ORDER BY ?length

Operations that combine or extend results would not need to be defined to be order preserving. A slick system might notice it's query plan was already ordered and not actually do the ORDER BY as it's unnecessarily.

 Andy

Received on Wednesday, 18 March 2009 12:30:17 UTC