W3C

SPARQL 1.1 Property Paths

W3C Working Draft 26 January 2010

Obsolete Draft (Document Status Update, 10 January 2014)

This document is obsolete. The normative text is: SPARQL 1.1 Query Language, Section 9: Property Paths.

This version:
http://www.w3.org/TR/2010/WD-sparql11-property-paths-20100126/
Latest version:
http://www.w3.org/TR/sparql11-property-paths/
Editor:
Andy Seaborne, Talis Information Limited <andy.seaborne@talis.com>

Abstract

This document describes SPARQL Property Paths. Property Paths give a more succinct way to write parts of basic graph patterns and also extend matching of triple pattern to arbitrary length paths. Property paths do not invalidate or change any existing SPARQL query.

Property paths are a time-permitting feature.

Status of this Document

This section describes the status of this document at the time of its publication. Other documents may supersede this document. A list of current W3C publications and the latest revision of this technical report can be found in the W3C technical reports index at http://www.w3.org/TR/.

This is the First Public Working Draft of the "SPARQL 1.1 Property Paths" specification for review by W3C members and other interested parties.

This is a time-permitting feature and may be incorporated into the main query document.

Comments on this document should be sent to public-rdf-dawg-comments@w3.org, a mailing list with a public archive. Questions and comments about SPARQL that are not related to this specification, including extensions and features, can be discussed on the mailing list public-sparql-dev@w3.org, (public archive).

This document was produced by the SPARQL Working Group, which is part of the W3C Semantic Web Activity.

No Endorsement

Publication as a Working Draft does not imply endorsement by the W3C Membership. This is a draft document and may be updated, replaced or obsoleted by other documents at any time. It is inappropriate to cite this document as other than work in progress.

Patents

This document was produced by a group operating under the 5 February 2004 W3C Patent Policy. W3C maintains a public list of any patent disclosures made in connection with the deliverables of the group; that page also includes instructions for disclosing a patent. An individual who has actual knowledge of a patent which the individual believes contains Essential Claim(s) must disclose the information in accordance with section 6 of the W3C Patent Policy.

Table of Contents

1 Introduction
    1.1 Document Conventions
2 Outstanding Issues
3 Path Language
4 Path Terminology
5 Examples
    5.1 Simple Paths
    5.2 Complex Paths
6 Syntax
7 Algebra
8 Evaluation

Appendices

A References
B CVS History


1 Introduction

A property path is a possible route through a graph between two graph nodes. A trivial case is a property path of length exactly 1, which is a triple pattern. Property paths allow for more concise expression of some SPARQL basic graph patterns and also add the ability to match arbitrary length paths.

1.1 Document Conventions

EBNF

2 Outstanding Issues

This section notes significant areas of discussion. Comments from the community are actively sought on these matters, as well as the rest of the document. Please send comments to public-rdf-dawg-comments@w3.org

3 Path Language

A property path expression (or just 'path') is similar to a string regular expression but over properties, not characters. Query evaluation determines all matches of a path expression and binds subject or object as appropriate. Only one match per route through the graph is recorded - no duplicates for any given path expression.

In the description below, uri is either a URI or a prefixed name and elt is a path element, which may itself be composed of path syntax constructs.

Syntax FormMatches
uri A URI or a prefixed name. A path of length one.
^elt Inverse path (object to subject).
(elt) A group path elt, brackets control precedence.
elt1 / elt2A sequence path of elt1, followed by elt2
elt1 ^ elt2 Shorthand for elt1 / ^elt2, that is elt1 followed by the inverse of elt2.
elt1 | elt2A alternative path of elt1, or elt2 (all possibilities are tried).
elt*A path of zero or more occurrences of elt.
elt+ A path of one or more occurrences of elt.
elt?A path of zero or one elt.
elt{n,m} A path between n and m occurrences of elt.
elt{n} Exactly n occurrences of elt. A fixed length path.
elt{n,}n or more occurrences of elt.
elt{,n} Between 0 and n occurrences of elt.

A zero occurrence of a path element always matches.

Precedence:

Precedence is left-to-right within groups.

4 Path Terminology

Paths are "simple" if they involve only operators / (sequence), ^ (inverse, unary or binary) and the form {n}, for some single integer n. Such paths are fixed length. They are translated to triple patterns in the transformation to the SPARQL algebra and do not require special path-evaluation at runtime.

A path of just a URI is still a single triple pattern.

A path is "complex"  if it involves one or more of the operators *,?, + and {} (except {n}). Such paths require an algebra extension.

A path of length zero connects a graph node to itself.

Cycles in paths are possible and are handled.

Paths do not need to be anchored at one end or the other, although this can lead to large numbers of result because the whole graph is searched.

5 Examples

See also uses cases.

5.1 Simple Paths

Example: Sequence

Find the name of any people that Alice knows.

{
  ?x foaf:mbox <mailto:alice@example> .
  ?x foaf:knows/foaf:name ?name .
 }
Example: Sequence

Find the names of people 2 "foaf:knows" links away.

{ 
  ?x foaf:mbox <mailto:alice@example> .
  ?x foaf:knows/foaf:knows/foaf:name ?name .
 }

This is the same as the strict SPARQL query:

{  ?x  foaf:mbox <mailto:alice@example> .
   ?x  foaf:knows [ foaf:knows [ foaf:name ?name ]]. }

or, with explicit variables:

{
  ?x  foaf:mbox <mailto:alice@example> .
  ?x  foaf:knows ?a1 .
  ?a1 foaf:knows ?a2 .
  ?a2 foaf:name ?name .
}
Example: Filtering duplicates

Because someone Alice knows may well know Alice, the example above may include Alice herself. This could be avoided with:

{ ?x foaf:mbox <mailto:alice@example> .
   ?x foaf:knows/foaf:knows ?y .
   FILTER ( ?x != ?y )
   ?y foaf:name ?name 
}
Example: Inverse Property Paths

These two are the same query: the second is just reversing the property direction which swaps the roles of subject and object.

{ ?x foaf:mbox <mailto:alice@example> }
{ <mailto:alice@example> ^foaf:mbox ?x }
Example: Inverse Path Sequence

Find all the people who know someone ?x knows.

{
  ?x foaf:knows^foaf:knows ?y .  
  FILTER(?x != ?y)
}

5.2 Complex Paths

Example:

Find the names of all the people that can be reached from Alice by foaf:knows:

{
  ?x foaf:mbox <mailto:alice@example> .
  ?x foaf:knows+/foaf:name ?name .
 }
Example:

Some forms of limited inference are possible as well. For example: all types and supertypes of a resource:

{ <http://example/thing> rdf:type/rdfs:subClassOf* ?type }

All resources and all their inferred types:

{ ?x rdf:type/rdfs:subClassOf* ?type }

6 Syntax

This syntax will be incorporated into the main SPARQL grammar if the time-permitting feature is accepted.

TriplesSameSubjectPath  ::=   VarOrTerm PropertyListNotEmptyPath | TriplesNode PropertyListPath
PropertyListPath  ::= PropertyListNotEmpty?
PropertyListNotEmptyPath  ::= ( VerbPath | VerbSimple ) ObjectList ( ';' ( ( VerbPath | VerbSimple ) ObjectList )? )*
VerbPath  ::= Path
VerbSimple  ::= Var
Path  ::= PathAlternative
PathAlternative  ::= PathSequence ( '|' PathSequence )*
PathSequence  ::= PathEltOrInverse ( '/' PathEltOrInverse | '^' PathElt )*
PathElt  ::= PathPrimary PathMod?
PathEltOrInverse  ::= PathElt | '^' PathElt
PathMod  ::= ( '*' | '?' | '+' | '{' ( Integer ( ',' ( '}' | Integer '}' ) | '}' ) ) )
PathPrimary  ::= ( IRIref | 'a' | '(' Path ')' )

7 Algebra

@@Will need to introduce temporary variables to expand simple paths.

8 Evaluation

@@Unfinished section

Path evaluation yields a set of bindings of variables (excluding any system-generated variables). If there are two or more paths, from <a> to <b>, only a unique solution is returned.

Cycles are permitted and included in matches. Cycle detection is necessary.

Triple patterns are equivalent to a path of length exactly one.

A References

1 Normative References

B CVS History

  $Log: Overview.html,v $
  Revision 1.2  2014-01-10 19:59:41  sandro
  *** empty log message ***

  Revision 1.1  2010-01-27 16:24:12  bertails
  sparql

  Revision 1.9  2010/01/27 01:48:05  apollere2
  fixed broken fragment ID.

  Revision 1.8  2010/01/24 14:46:12  apollere2
  Minor typo fix.CVS: ----------------------------------------------------------------------

  Revision 1.7  2010/01/24 14:45:21  apollere2
  Changed Editor's draft to First Public working draft.

  Revision 1.6  2010/01/24 14:40:51  apollere2
  Added no-endorsement boiler plate.

  Revision 1.5  2010/01/24 14:34:30  apollere2
  Fixes of URIs in gen.html.

  Revision 1.4  2010/01/24 14:24:10  apollere2
  Document type is WD, not FPWD.

  Revision 1.17  2010/01/22 21:19:25  aseaborne
  Fix validation problems after XSLT transformation

  Revision 1.16  2010/01/22 16:26:23  apollere2
  XSLT conversion to gen.html for FPWD.

  Revision 1.15  2010/01/11 10:27:00  aseaborne
  Corrections and improvements in response to 2010JanMar/0099.

  Revision 1.14  2010/01/06 11:08:59  aseaborne
  Corrections and improvements in response to 2010JanMar/0055. See 2010JanMar/0057.

  Revision 1.13  2010/01/05 11:21:14  aseaborne
  Correct the description of operator precedence

  Revision 1.12  2010/01/04 12:11:14  aseaborne
  Fix markup

  Revision 1.11  2010/01/04 12:08:41  aseaborne
  Fix markup

  Revision 1.10  2010/01/04 12:07:23  aseaborne
  Fix markup

  Revision 1.9  2010/01/04 12:06:31  aseaborne
   Abstract expanded.
   Terminolgy change: "inverse", not "reverse"
   Issues section placed at front.  Added issues for path length and "^"
   Various editorial corrections.
   Fix example using foaf:knows^foaf:knows

  Revision 1.8  2009/11/06 15:11:30  aseaborne
  Transfer content from wiki

  Revision 1.7  2009/11/06 15:09:51  aseaborne
  Transfer content from wiki

  Revision 1.6  2009/11/06 15:05:47  aseaborne
  Transfer content from wiki

  Revision 1.5  2009/11/06 15:03:25  aseaborne
  Transfer content from wiki
  
  Revision 1.4  2009/11/06 14:57:35  aseaborne
  Transfer content from wiki
  
  Revision 1.3  2009/11/06 14:47:33  aseaborne
  Transfer content from wiki
  
  Revision 1.2  2009/11/06 14:34:53  aseaborne
  Transfer content from wiki
  
  Revision 1.1  2009/11/06 13:51:34  aseaborne
  xmlspec template