Feature: Paths Length

Paths length provides a syntax to define path length in the graph.

Feature description

The paths length feature will provide the ability to identify lenght of paths in SPARQL queries. It must be combined to the path feature itself.

Examples

The following examples uses the path length syntax define in Corese

SELECT ?y
{
  <http://example.org/bob> $path ?y .
} 
FILTER (match($path, foaf:knows))
FILTER (pathLength($path) >= 1 && pathLength($path) <= 2)

will retrieve Bob's friends and friends of his friends.

Can already be done with the current SPARQL specification, as follows. Hence, this property can be considered as syntactic sugar. Yet, this is more than useful is the path length variation is important.

SELECT ?x
{
  { <http://example.org/bob> foaf:knows ?y . }
  UNION
  { <http://example.org/bob> foaf:knows ?x . ?x foaf:knows ?y }
} 

Existing Implementation(s)

Corese - http://www-sop.inria.fr/edelweiss/software/corese/v2_4_1/manual/next.php

See also:

• Corese: GRAPH path in SPARQL
• SPARQLer

Virtuoso supports depth restriction in transitive SQL extension and in very similar transitive SPARQL extension. (SPARQL is extended with options that are translated to t_id, t_out, t_length etc one-to-one). The path variable syntax could be macroexpanded into the Virtuoso syntax, supporting transitivity etc. The path variable syntax has the advantage that it is shorter than the Virtuoso transitive subquery for simple cases.

Existing Specification / Documentation

See existing implementations

Compatibility

Path lengths should be compatible with the current SPARQL grammar. In that case, $path expression should be replaced by ?path.

Issues arise if the path includes some transitivity properties and inference is applied before the path being computed.

Example:

Let's imagine the following taxonomy of classes:

:LivingObject rdfs:subClassOf :Entity
:Animal rdfs:subClassOf :LivingObject 
:Dog rdfs:subClassOf :Animal
:Teckel rdfs:subClassOf :Dog

And then the following query

SELECT ?y
{
  :Entity$path ?y .
} 
FILTER (match($path, rdfs:subClassOf))
FILTER (pathLength($path) >= 1 && pathLength($path) <= 2)

Without inference, results will be

:LivingObject
:Animal

With inference on transitive properties (applied before path length computation)

:LivingObject
:Animal
:Dog
:Teckel

Links to postponed Issues

None.

Related Use Cases/Extensions

Feature:PropertyPaths

Champions

• Alexandre Passant / DERI

Use Cases

• Retrieving people in a social network from a given entry point, limiting the number of intermediate contacts to a certain value
• Querying all skos:narrower items in a SKOS taxonomy (or rdfs:subClasses in a classes hierarchy) limited to a certain depth (in order to avoid information overload in huge taxonomy, where after a certain depth, the classes / instances are no more relevant compared to the root class / instance)

References

• teleconference discussion