index.html
20.9 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="EN" xml:lang="EN"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>SPARQL 1.1 Property Paths</title><style type="text/css">
@import url("../shared/local.css");
code { font-family: monospace; }
div.constraint,
div.issue,
div.note,
div.notice { margin-left: 2em; }
ol.enumar { list-style-type: decimal; }
ol.enumla { list-style-type: lower-alpha; }
ol.enumlr { list-style-type: lower-roman; }
ol.enumua { list-style-type: upper-alpha; }
ol.enumur { list-style-type: upper-roman; }
div.exampleInner pre { margin-left: 1em;
margin-top: 0em; margin-bottom: 0em}
div.exampleOuter {border: 4px double gray;
margin: 0em; padding: 0em}
div.exampleInner { background-color: #d5dee3;
border-top-width: 4px;
border-top-style: double;
border-top-color: #d3d3d3;
border-bottom-width: 4px;
border-bottom-style: double;
border-bottom-color: #d3d3d3;
padding: 4px; margin: 0em }
div.exampleWrapper { margin: 4px }
div.exampleHeader { font-weight: bold;
margin: 4px}
em.rfc2119 { text-transform: lowercase;
font-variant: small-caps;
font-style: normal; }
</style><link rel="stylesheet" type="text/css" href="http://www.w3.org/StyleSheets/TR/W3C-WD" /></head><body><div class="head"><p><a href="http://www.w3.org/"><img src="http://www.w3.org/Icons/w3c_home" alt="W3C" height="48" width="72" /></a></p>
<h1><a name="title" id="title"></a>SPARQL 1.1 Property Paths</h1>
<h2><a name="w3c-doctype" id="w3c-doctype"></a>W3C Working Draft 26 January 2010</h2><dl><dt>This version:</dt><dd>
<a href="http://www.w3.org/TR/2010/WD-sparql11-property-paths-20100126/">http://www.w3.org/TR/2010/WD-sparql11-property-paths-20100126/</a>
</dd><dt>Latest version:</dt><dd>
<a href="http://www.w3.org/TR/sparql11-property-paths/">http://www.w3.org/TR/sparql11-property-paths/</a>
</dd><dt>Editor:</dt><dd>Andy Seaborne, Talis Information Limited <a href="mailto:andy.seaborne@talis.com"><andy.seaborne@talis.com></a></dd></dl><p class="copyright"><a href="http://www.w3.org/Consortium/Legal/ipr-notice#Copyright">Copyright</a> © 2010 <a href="http://www.w3.org/"><acronym title="World Wide Web Consortium">W3C</acronym></a><sup>®</sup> (<a href="http://www.csail.mit.edu/"><acronym title="Massachusetts Institute of Technology">MIT</acronym></a>, <a href="http://www.ercim.org/"><acronym title="European Research Consortium for Informatics and Mathematics">ERCIM</acronym></a>, <a href="http://www.keio.ac.jp/">Keio</a>), All Rights Reserved. W3C <a href="http://www.w3.org/Consortium/Legal/ipr-notice#Legal_Disclaimer">liability</a>, <a href="http://www.w3.org/Consortium/Legal/ipr-notice#W3C_Trademarks">trademark</a> and <a href="http://www.w3.org/Consortium/Legal/copyright-documents">document use</a> rules apply.</p></div><hr /><div>
<h2><a name="abstract" id="abstract"></a>Abstract</h2><p>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.</p><p>Property paths are a <i>time-permitting</i> feature.</p></div><div>
<h2><a name="status" id="status"></a>Status of this Document</h2><p><em>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 <a href="http://www.w3.org/TR/">W3C technical reports index</a> at http://www.w3.org/TR/.</em></p><p>This is the First Public <a href="http://www.w3.org/2005/10/Process-20051014/tr.html#RecsWD">Working Draft</a> of the "SPARQL 1.1 Property Paths" specification for review by W3C members and other interested parties.</p><p>This is a <a href="http://www.w3.org/2009/05/sparql-phase-II-charter#feature-ext">time-permitting feature</a> and may be incorporated into the main query document.</p><p>Comments on this document should be sent to <a href="mailto:public-rdf-dawg-comments@w3.org">public-rdf-dawg-comments@w3.org</a>, a mailing list with a <a href="http://lists.w3.org/Archives/Public/public-rdf-dawg-comments">public archive</a>. Questions and comments about SPARQL that are not related to this specification, including extensions and features, can be discussed on the mailing list <a href="mailto:public-sparql-dev@w3.org">public-sparql-dev@w3.org</a>, (<a href="http://lists.w3.org/Archives/Public/public-sparql-dev">public archive</a>).</p><p>This document was produced by the <a href="http://www.w3.org/2001/sw/DataAccess/">SPARQL Working Group</a>, which is part of the <a href="http://www.w3.org/2001/sw/Activity">W3C Semantic Web Activity</a>.</p>
<h4 class="no-toc no-num" id="no-endorsement">No Endorsement</h4>
<p><em>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.</em></p>
<h4 class="no-toc no-num" id="patents">Patents</h4>
<p>This document was produced by a group operating under the <a href="http://www.w3.org/Consortium/Patent-Policy-20040205/">5 February 2004 W3C Patent Policy</a>. W3C maintains a <a rel="disclosure" href="http://www.w3.org/2004/01/pp-impl/35463/status">public list of any patent disclosures</a> 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 <a href="http://www.w3.org/Consortium/Patent-Policy-20040205/#def-essential">Essential Claim(s)</a> must disclose the information in accordance with <a href="http://www.w3.org/Consortium/Patent-Policy-20040205/#sec-Disclosure">section 6 of the W3C Patent Policy</a>.</p></div><div class="toc">
<h2><a name="contents" id="contents"></a>Table of Contents</h2><p class="toc">1 <a href="#sec-intro">Introduction</a><br />
1.1 <a href="#conventions">Document Conventions</a><br />
2 <a href="#Outstanding_Issues">Outstanding Issues</a><br />
3 <a href="#path-language">Path Language</a><br />
4 <a href="#path-terminology">Path Terminology</a><br />
5 <a href="#id41857">Examples</a><br />
5.1 <a href="#simple_paths">Simple Paths</a><br />
5.2 <a href="#complex_paths">Complex Paths</a><br />
6 <a href="#path-syntax">Syntax</a><br />
7 <a href="#path-algebra">Algebra</a><br />
8 <a href="#path-evaluation">Evaluation</a><br />
</p>
<h3><a name="appendices" id="appendices"></a>Appendices</h3><p class="toc">A <a href="#sec-bibliography">References</a><br />
B <a href="#sec-cvsLog">CVS History</a><br />
</p></div><hr /><div class="body"><div class="div1">
<h2><a name="sec-intro" id="sec-intro"></a>1 Introduction</h2><p>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.</p><div class="div2">
<h3><a name="conventions" id="conventions"></a>1.1 Document Conventions</h3><p>EBNF</p></div></div><div class="div1">
<h2><a name="Outstanding_Issues" id="Outstanding_Issues"></a>2 Outstanding Issues</h2><p>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 <a href="mailto:public-rdf-dawg-comments@w3.org">public-rdf-dawg-comments@w3.org</a>
</p><ul><li>The use of "<code>^</code>" as a unary and binary operator may be confusing. An alterative is to just have a unary form and require "<code>/^</code>" in paths to combine an inverse property into a path. The <a href="http://www.w3.org/2000/10/swap/doc/Shortcuts#Paths">N3 path syntax</a> includes binary and unary "<code>^</code>".</li><li>While property paths as currently specified can be used to access RDF
lists (e.g. rdf:rest*/rdf:first), the Working Group notes that this
would be more useful if results were returned in the order they occur in
the RDF list. This presents significant complexity in the context of the
existing SPARQL algebra.</li><li>The WG has discussed providing access to the length of matched paths,
which would provide greater functionality but would complicate path
evaluation. At this time, the WG's primary aim is to specify a core set
of functionality while not blocking future enhancements.</li><li>How does this interact with inference when SPARQL is used with systems carrying out inference as part of query processing?</li><li>Paths expressions match once even if there are multiple possible paths
between two points (c.f. SPARQL BGP)</li></ul></div><div class="div1">
<h2><a name="path-language" id="path-language"></a>3 Path Language</h2><p>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.
</p><p>In the description below, <i><tt>uri</tt></i> is either a URI or a
prefixed name and <i><tt>elt</tt></i> is a path element, which may itself
be composed of path syntax constructs.
</p><table border="1" cellspacing="0"><tbody><tr><th>Syntax Form</th><th>Matches</th></tr><tr><td><tt><i>uri</i></tt></td><td> A URI or a prefixed name. A path of length one.</td></tr><tr><td><tt><i>^elt</i></tt></td><td> Inverse path (object to subject).</td></tr><tr><td><i><tt>(elt)</tt></i></td><td> A group path <i><tt>elt</tt></i>, brackets control precedence.</td></tr><tr><td><i><tt>elt1 / elt2</tt></i></td><td>A sequence path of <i><tt>elt1</tt></i>, followed by <i><tt>elt2</tt></i></td></tr><tr><td><i><tt>elt1 ^ elt2</tt></i></td><td> Shorthand for <tt><i>elt1 / ^elt2</i></tt>, that is <i><tt>elt1 </tt></i> followed by the inverse of <i><tt>elt2</tt></i>.</td></tr><tr><td> <i><tt>elt1 | elt2</tt></i></td><td>A alternative path of <i><tt>elt1</tt></i>, or <tt><i>elt2</i></tt> (all possibilities are tried).</td></tr><tr><td><i><tt>elt*</tt></i></td><td>A path of zero or more occurrences of <i><tt>elt</tt></i>.</td></tr><tr><td><i><tt>elt+</tt></i></td><td> A path of one or more occurrences of <i><tt>elt</tt></i>.</td></tr><tr><td><i><tt>elt?</tt></i></td><td>A path of zero or one <i><tt>elt</tt></i>.</td></tr><tr><td><i><tt>elt{n,m}</tt></i></td><td> A path between n and m occurrences of <i><tt>elt</tt></i>.</td></tr><tr><td> <i><tt>elt{n}</tt></i></td><td> Exactly <i><tt>n</tt></i> occurrences of <i><tt>elt</tt></i>. A fixed length path.</td></tr><tr><td><i><tt>elt{n,}</tt></i></td><td><i><tt>n</tt></i> or more occurrences of <i><tt>elt</tt></i>.</td></tr><tr><td><i><tt>elt{,n}</tt></i></td><td> Between 0 and <i><tt>n</tt></i> occurrences of <i><tt>elt</tt></i>.</td></tr></tbody></table><p>A zero occurrence of a path element always matches.
</p><p>Precedence:
</p><ul><li>URI, prefixed names</li><li>Groups</li><li>Unary operators <tt>*</tt>, <tt>?</tt>, <tt>+</tt> and <tt>{}</tt> forms</li><li>Unary ^ inverse links</li><li>Binary operators <tt>/</tt> and ^</li><li> Binary operator <tt>|</tt></li></ul><p>Precedence is left-to-right within groups.
</p></div><div class="div1">
<h2><a name="path-terminology" id="path-terminology"></a>4 Path Terminology</h2><p>Paths are "simple" if they involve only operators / (sequence), ^ (inverse,
unary or binary) and the form {<i>n</i>}, for some single integer <i>n</i>. 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.
</p><p>
A path of just a URI is still a single triple pattern.
</p><p>
A path is "complex" if it involves one or more of the operators *,?, +
and <tt>{}</tt> (except <tt>{n}</tt>). Such paths require an algebra extension.
</p><p>A path of length zero connects a graph node to itself.
</p><p>Cycles in paths are possible and are handled.
</p><p>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.
</p></div><div class="div1">
<h2><a name="id41857" id="id41857"></a>5 Examples</h2><p>See also <a href="/2009/sparql/wiki/TaskForce:PropertyPaths#Use_Cases" title="TaskForce:PropertyPaths">uses cases</a>.</p><div class="div2">
<h3><a name="simple_paths" id="simple_paths"></a>5.1 Simple Paths</h3><div class="exampleOuter">
<div class="exampleHeader"><a name="id41881" id="id41881"></a>Example: Sequence</div><p>Find the name of any people that Alice knows.</p><pre>{
?x foaf:mbox <mailto:alice@example> .
?x foaf:knows/foaf:name ?name .
}</pre></div><div class="exampleOuter">
<div class="exampleHeader"><a name="id41898" id="id41898"></a>Example: Sequence</div><p>Find the names of people 2 "<tt>foaf:knows</tt>" links away.</p><pre>{
?x foaf:mbox <mailto:alice@example> .
?x foaf:knows/foaf:knows/foaf:name ?name .
}</pre><p>This is the same as the strict SPARQL query:</p><pre>{ ?x foaf:mbox <mailto:alice@example> .
?x foaf:knows [ foaf:knows [ foaf:name ?name ]]. }</pre><p>or, with explicit variables:</p><pre>{
?x foaf:mbox <mailto:alice@example> .
?x foaf:knows ?a1 .
?a1 foaf:knows ?a2 .
?a2 foaf:name ?name .
}</pre></div><div class="exampleOuter">
<div class="exampleHeader"><a name="id41940" id="id41940"></a>Example: Filtering duplicates</div><p>Because someone Alice knows may well know Alice, the example above may
include Alice herself. This could be avoided with:
</p><pre>{ ?x foaf:mbox <mailto:alice@example> .
?x foaf:knows/foaf:knows ?y .
FILTER ( ?x != ?y )
?y foaf:name ?name
}</pre></div><div class="exampleOuter">
<div class="exampleHeader"><a name="id41956" id="id41956"></a>Example: Inverse Property Paths</div><p>These two are the same query: the second is just reversing the property
direction which swaps the roles of subject and object.</p><pre>{ ?x foaf:mbox <mailto:alice@example> }</pre><pre>{ <mailto:alice@example> ^foaf:mbox ?x }</pre></div><div class="exampleOuter">
<div class="exampleHeader"><a name="id41978" id="id41978"></a>Example: Inverse Path Sequence</div><p>Find all the people who know someone <tt>?x</tt> knows.</p><pre>{
?x foaf:knows^foaf:knows ?y .
FILTER(?x != ?y)
}</pre></div></div><div class="div2">
<h3><a name="complex_paths" id="complex_paths"></a>5.2 Complex Paths</h3><div class="exampleOuter">
<div class="exampleHeader"><a name="id42005" id="id42005"></a>Example: </div><p>Find the names of all the people that can be reached from Alice by <tt>foaf:knows</tt>:</p><pre>{
?x foaf:mbox <mailto:alice@example> .
?x foaf:knows+/foaf:name ?name .
}</pre></div><div class="exampleOuter">
<div class="exampleHeader"><a name="id42026" id="id42026"></a>Example: </div><p>Some forms of limited inference are possible as well. For example: all types
and supertypes of a resource:</p><pre>{ <http://example/thing> rdf:type/rdfs:subClassOf* ?type }</pre><p>All resources and all their inferred types:</p><pre>{ ?x rdf:type/rdfs:subClassOf* ?type }</pre></div></div></div><div class="div1">
<h2><a name="path-syntax" id="path-syntax"></a>6 Syntax</h2><p>This syntax will be incorporated into the main SPARQL grammar if the time-permitting
feature is accepted.</p><div style="font-family: monospace;"><table><tbody><tr><td> TriplesSameSubjectPath
</td><td> ::=
</td><td> VarOrTerm PropertyListNotEmptyPath | TriplesNode PropertyListPath
</td></tr><tr><td> PropertyListPath
</td><td> ::=
</td><td> PropertyListNotEmpty?
</td></tr><tr><td> PropertyListNotEmptyPath
</td><td> ::=
</td><td> ( VerbPath | VerbSimple ) ObjectList ( ';' ( ( VerbPath | VerbSimple ) ObjectList )? )*
</td></tr><tr><td> VerbPath
</td><td> ::=
</td><td> Path
</td></tr><tr><td> VerbSimple
</td><td> ::=
</td><td> Var
</td></tr><tr><td> Path
</td><td> ::=
</td><td> PathAlternative
</td></tr><tr><td> PathAlternative
</td><td> ::=
</td><td> PathSequence ( '|' PathSequence )*
</td></tr><tr><td> PathSequence
</td><td> ::=
</td><td> PathEltOrInverse ( '/' PathEltOrInverse | '^' PathElt )*
</td></tr><tr><td> PathElt
</td><td> ::=
</td><td> PathPrimary PathMod?
</td></tr><tr><td> PathEltOrInverse
</td><td> ::=
</td><td> PathElt | '^' PathElt
</td></tr><tr><td> PathMod
</td><td> ::=
</td><td> ( '*' | '?' | '+' | '{' ( Integer ( ',' ( '}' | Integer '}' ) | '}' ) ) )
</td></tr><tr><td> PathPrimary
</td><td> ::=
</td><td> ( IRIref | 'a' | '(' Path ')' )
</td></tr></tbody></table></div></div><div class="div1">
<h2><a name="path-algebra" id="path-algebra"></a>7 Algebra</h2><p><i>@@Will need to introduce temporary variables to expand simple paths.</i></p></div><div class="div1">
<h2><a name="path-evaluation" id="path-evaluation"></a>8 Evaluation</h2><p><i>@@Unfinished section</i></p><p>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.</p><p>Cycles are permitted and included in matches. Cycle detection is necessary.</p><p>Triple patterns are equivalent to a path of length exactly one. </p></div></div><div class="back"><div class="grammarTable"><table><tbody class="prod"><tr><td></td></tr></tbody></table></div><div class="div1">
<h2><a name="sec-bibliography" id="sec-bibliography"></a>A References</h2><div class="div1">
<h2><a name="sec-existing-stds" id="sec-existing-stds"></a>1 Normative References</h2></div></div><div class="div1">
<h2><a name="sec-cvsLog" id="sec-cvsLog"></a>B CVS History</h2><pre>
$Log: Overview.html,v $
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 <a href="http://lists.w3.org/Archives/Public/public-rdf-dawg/2010JanMar/0099.html">2010JanMar/0099</a>.
Revision 1.14 2010/01/06 11:08:59 aseaborne
Corrections and improvements in response to <a href="http://lists.w3.org/Archives/Public/public-rdf-dawg/2010JanMar/0055.html">2010JanMar/0055</a>. See <a href="http://lists.w3.org/Archives/Public/public-rdf-dawg/2010JanMar/0057.html">2010JanMar/0057</a>.
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
</pre></div></div></body></html>