Abstract

Linked Data Patch Format (LD Patch) defines a language for expressing a sequence of operations to apply to Linked Data resources; it is suitable for use with the HTTP PATCH method.

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/.

Although the Linked Data Platform (LDP) Working Group is currently favoring LD Patch, it seeks more input in deciding which format to promote for use in LDP PATCH [LDP] operations on RDF Sources. Other viable candidates include:

At this point, the advantage leans towards LD Patch in terms of simplicity, ease of implementation, and run-time performance on anticipated data. We welcome data relevant to this decision.

This document was published by the Linked Data Platform Working Group as an Editor's Draft. If you wish to make comments regarding this document, please send them to public-ldp-comments@w3.org (subscribe, archives). All comments are welcome.

Publication as a First Public 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.

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.

This document is governed by the 14 October 2005 W3C Process Document.

Table of Contents

1. Introduction

This section is non-normative.

Linked Data "describes a method of publishing structured data so that it can be interlinked and become more useful. It builds upon standard Web technologies such as HTTP, RDF and URIs, but rather than using them to serve web pages for human readers, it extends them to share information in a way that can be read automatically by computers. This enables data from different sources to be connected and queried." (source Wikipedia).

This document defines the Linked Data Patch Format (LD Patch), a format for describing changes to apply to Linked Data. It is suitable for use with HTTP PATCH [rfc5789], a method to perform partial modifications to Web resources.

An instance of the LD Patch language (or LD Patch document) defines a list of operations to be performed against a Linked Data resource, namely the addition or removal of RDF [rdf11-concepts] triples in this graph.

The LD Patch format described in this document should be seen as an "assembly language" for updating RDF Graphs in a resource-centric fashion. It is the intention to confine its expressive power to an RDF diff with partial support for blank nodes and rdf:List manipulations. For more powerful operations on RDF Graphs and Quad Stores, the LDP WG recommends the reader to consider SPARQL Update [sparql11-update].

Example

The following RDF Graph will be used as an example through this specification. It describes the relation between a person named Tim Berners-Lee (denoted by <http://example.org/timbl#>) and two events he attended.

Example 1
@prefix schema: <http://schema.org/> .
@prefix profile: <http://ogp.me/ns/profile#> .
@prefix ex: <http://example.org/vocab#> .
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
<http://example.com/timbl#> a schema:Person ;
  schema:alternateName "TimBL" ;
  profile:first_name "Tim" ;
  profile:last_name "Berners-Lee" ;
  schema:workLocation [ schema:name "W3C/MIT" ] ;
  schema:performerIn _:b1, _:b2 ;
  ex:preferredLanguages ( "en" "fr" ).

_:b1 schema:name "F2F5 - Linked Data Platform" ;
  schema:url <https://www.w3.org/2012/ldp/wiki/F2F5> .

_:b2 a schema:Event ;
  schema:name "TED 2009" ;
  schema:startDate "2009-02-04" ;
  schema:url <http://conferences.ted.com/TED2009/> .

The following is an example HTTP Patch request, conveying an LD Patch document:

Example 2
PATCH /timbl HTTP/1.1
Host: example.org
Content-Length: 478
Content-Type: text/ldpatch
If-Match: "abc123"

@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix schema: <http://schema.org/> .
@prefix profile: <http://ogp.me/ns/profile#> .
@prefix ex: <http://example.org/vocab#> .

Delete <#> profile:first_name "Tim" .
Add    <#> profile:first_name "Timothy" .

UpdateList <#> ex:preferredLanguages 1..2 ( "fr-CH" ) .

Bind ?event <#> /schema:performerIn[/schema:url = <https://www.w3.org/2012/ldp/wiki/F2F5>]  .
Add ?event rdf:type schema:Event .

Bind ?ted <http://conferences.ted.com/TED2009/> /^schema:url! .
Delete ?ted schema:startDate "2009-02-04".
Add ?ted schema:location _:loc .
Add _:loc schema:name "Long Beach, California" .
Add _:loc schema:geo _:geo .
Add _:geo schema:latitude "33.7817" .
Add _:geo schema:longitude "-118.2054" .

This example introduces most features of the LD Patch format: @prefix and prefixed names, the Add, Delete and UpdateList operations, the Bind-ing mechanism and blank node creation. The "text/ldpatch" media type is prospectively used to identify such LD Patch documents.

The following is the resulting (patched) document.

Example 3
@prefix schema: <http://schema.org/> .
@prefix profile: <http://ogp.me/ns/profile#> .
@prefix ex: <http://example.org/vocab#> .

<http://example.com/timbl#> a schema:Person ;
  schema:alternateName "TimBL" ;
  profile:first_name "Timothy" ;
  profile:last_name "Berners-Lee" ;
  schema:workLocation [ schema:name "W3C/MIT" ] ;
  schema:performerIn _:b1, _:b2 ;
  ex:preferredLanguages ( "en" "fr-CH" ).

_:b1 a schema:Event ;
  schema:name "F2F5 - Linked Data Platform" ;
  schema:url <https://www.w3.org/2012/ldp/wiki/F2F5> .

_:b2 a schema:Event ;
  schema:name "TED 2009" ;
  schema:url <http://conferences.ted.com/TED2009/> ;
  schema:location [
    schema:name "Long Beach, California";
    schema:geo [ schema:latitude "33.7817" ; schema:longitude "-118.2054" ]
  ] .

2. LD Patch format

This section is non-normative.

A LD Patch document is made of a prologue and a list of statements, where the order is relevant. The prologue declares a numver of prefixes used to abbreviate URIs. Then each statement either binds a variable to a matching node, or defines a modification on the graph.

2.1 Prefixes

LD Patch offers the possibility to abbreviate URIs by using Turtle's @prefix directive that allows declaring a short prefix name for a long prefix of repeated URIs. This is useful for many RDF vocabularies that are all defined in nearby namespace URIs, possibly using XML's namespace mechanism that works in a similar fashion.

Once a prefix such as @prefix foo: <http://example.org/ns#> is defined, any mention of a URI later in the document may use a PrefixedName that starts with foo: to stand for the longer URI. So for example, the PrefixedName foo:bar is a shorthand for the URI <http://example.org/ns#bar>.

2.2 Node matching semantics

LD Patch borrows much of its syntax to Turtle [turtle] and SPARQL [sparql11-query] for describing nodes. IRIs (either abbreviated or not) and literals represent the corresponding node in the graph being patched. Blank nodes, on the other hand, pose a problem, as they have no global identifier. Indeed, blank node identifiers have their scope limited to the document in which they appear. As a consequence, whenever a blank node identifiers appears in an LD Patch document, it is understood to denote a fresh blank node, that needs to be created in the patched RDF graph. They cannot interfere with existing blank nodes in the graph.

In order to be able to address blank nodes already present in the graph, LD Patch has two mechanisms: Binding a variable to a blank node reachable with a path expression, and UpdateList to deal with those blank nodes that constitute RDF collections. There are cases where those mechanisms will not be able to unambiuously adress a given blank node, but those cases are deemed pathological, and out of the scope of this specification.

2.3 Pathological graph

Given an RDF graph G, a blank node b is said to be unambiguous in G if there exists a couple (n, p) where

such that applying p to n results in a unique {b}.

It is easy to see that only the unambiguous blank nodes of a graph can be handled in LD Patch.

Consider for example the following graph:

Example 4
<#> foaf:name "Alice" ; foaf:knows _:b1, _:b2 .
_:b1 a foaf:Person .
_:b2 a foaf:Person ; schema:workLocation _:b3 .
_:b3 schema:name "W3C/MIT" .

The blank nodes _:b2 and _:b3 are unambiguous (they can for example be reached unambiguoulsy from the literal "W3C/MIT"). The blank node _:b1, on the other hand, is ambigious as all path expressions that can can match it would also match _:b2.

Another example is a graph containing only blank nodes. All its nodes are therefore ambiguous as they can not be reached from a URI or a literal. Such a graph is not interesting in the context of linked data as it contains no URI to link to or from it.

Therefore, ambiguous blank nodes are considered a pathological case in the context of Linked Data, and so the fact that they cannot be coped with in LD Patch is deemed acceptable. Furthermore, their presence in a graph does not prevent the other nodes of that graph to be handled by LD Patch.

2.4 Path expression

LD Patch uses path expressions to describe possible routes through a graph between two graph nodes. The main goal is to allow addressing a blank node by “walking” the arcs of the graph from an already identified node. A path is composed by a number of steps, which can be of three kinds:

Note that each step can, in general, result in several matching nodes, as a given node can have several (incoming or outgoing) arcs with the same predicate.

A Path may also contains Constraints, which are of two kinds:

The path below (taken from our running example) will look for all the events attended by the starting node, and keep only those having <http://conferences.ted.com/TED2009/> as their URL.

Example 5
/schema:performerIn[/schema:url = <http://conferences.ted.com/TED2009/>]

Should ld-patch use a slash like sparql does, instead of as it currently does?

2.5 Bind

The Bind operation is used to create a new variable by binding or assigning an RDF Term to the variable. The bound variable has a global scope. Use of a given variable name anywhere in an LD Patch document identifies the same variable, although variables can be overriden in subsequent Bound statements. Following the example above, the Bind operation creates a new variable called event, starting from the RDF Term <#> and following the path expression /schema:performerIn[/schema:url = <http://conferences.ted.com/TED2009/>] in order to identify the RDF Term to which this variable will be bound to -- i.e. _:b2.

Example 6
Bind ?event <#> /schema:performerIn[/schema:url = <http://conferences.ted.com/TED2009/>] .

The Bind operation is defined by three components: Var, Value and Path, the last component being optional.

Var contains a unique name for the new variable. Variables are prefixed by "?"; the "?" character is not part of the variable name.

Value is the RDF Term that will be used as starting point when following the path expression.

Path is the expression that is used to identify the RDF Term to which the Variable will be bound. It is comprised of Step(s) and/or Constraint(s).

2.6 Add

The Add operation is used to add or append new RDF triples to the existing graph. To add new RDF triple, the operation requires a Subject, a Predicate and either an Object or a List.

Example 7
Add <#> profile:first_name "Timothy" .

Add ?event rdf:type schema:Event .
When the third component is an Object, then a single statement will be added. On the other hand, when it is a List, all the intermediate blank nodes and corresponding statements will be added to construct a well formed RDF collection (in addition to the triple with the given Subject, Predicate and that collection as the object).

2.7 Delete

The Delete operation is used to remove a single RDF triple from the existing graph. The syntax for the Delete operation requires a Subject, a Predicate and an Object.

Example 8
Delete <#> profile:first_name "Tim" .

Delete ?ted schema:startDate "2009-02-04".

2.8 UpdateList

The UpdateList operation is used to update the members of an RDF collection. That collection is supposed to be the object of a triple, specified by its Subject and Predicate. A Slice specification then describes which members (if any) of the collections are affected by the operation, and then a List of new members is provided. In the example below, UpdateList is used to replace the second member of a collection by the literal "fr-CH".

Example 9
UpdateList <#> ex:preferredLanguages 1..2 ( "fr-CH" ) .

UpdateList works in a similar way to slicing in Python or similar languages. In general, it replaces a part (“slice”) of a list by another list. To remove members, one can replace them by an empty list. To insert new values between two members, one can set a non empty list to the empty slice comprised between those two members.

In LD Patch, a slice is described by two positive integers separated by "..". The second integer can be omitted, in that case it denotes the end of the list. If both integers are omitted (i.e. ".." alone), this denotes by convention the empty slice at the end of the list. Indexes start at 0.

The following example shows the syntax for appending elements to a list:

Example 10
UpdateList <#> ex:preferredLanguages .. ( "fr-CH" ) .

In this final example, we replace all the elements after index 2 with the provided list:

Example 11
UpdateList <#> ex:preferredLanguages 2.. ( "fr-CH" ) .

3. Concrete Syntax

LDPatch ::= Prologue Statement*
Prologue ::= prefixID*
Statement ::= Bind | Add | Delete | UpdateList
Bind ::= ("Bind" | "B") Var Value Path? "."
Add ::= ("Add" | "A") Subject Predicate ( Object | List ) "."
Delete ::= ("Delete" | "D") Subject Predicate Object "."
UpdateList ::= ("UpdateList" | "UL") Subject Predicate Slice List "."

Subject ::= iri | BlankNode | Var
Predicate ::= iri
Object ::= iri | BlankNode | literal | Var
Value ::= iri | literal | Var
List ::= '(' Object* ')'

Path ::= ( Step | Constraint )*
Step ::= '/' ( '^' iri | iri | INDEX )
Constraint ::= '[' Path ( '=' Value )? ']' | '!'

Slice ::= INDEX? '..' INDEX?
INDEX ::= [0-9]+

// copied from SPARQL

// supposed to be `Var ::= VAR1 | VAR2` but here only VAR1
Var ::= '?' VARNAME
VARNAME ::= ( PN_CHARS_U | [0-9] ) ( PN_CHARS_U | [0-9] | #x00B7 | [#x0300-#x036F] | [#x203F-#x2040] )*

// copied from Turtle

prefixID ::= "@prefix" PNAME_NS IRIREF "."
Literal ::= RDFLiteral | NumericLiteral | BooleanLiteral
NumericLiteral ::= INTEGER | DECIMAL | DOUBLE
RDFLiteral ::= String (LANGTAG | '^^' iri)?
BooleanLiteral ::= 'true' | 'false'
String ::= STRING_LITERAL_QUOTE | STRING_LITERAL_SINGLE_QUOTE | STRING_LITERAL_LONG_SINGLE_QUOTE | STRING_LITERAL_LONG_QUOTE
iri ::= IRIREF | PrefixedName
PrefixedName ::= PNAME_LN | PNAME_NS
BlankNode ::= BLANK_NODE_LABEL | ANON
IRIREF ::= '<' ([^#x00-#x20<>"{}|^`\] | UCHAR)* '>' /* #x00=NULL #01-#x1F=control codes #x20=space */
PNAME_NS ::= PN_PREFIX? ':'
PNAME_LN ::= PNAME_NS PN_LOCAL
BLANK_NODE_LABEL ::= '_:' (PN_CHARS_U | [0-9]) ((PN_CHARS | '.')* PN_CHARS)?
LANGTAG ::= '@' [a-zA-Z]+ ('-' [a-zA-Z0-9]+)*
INTEGER ::= [+-]? [0-9]+
DECIMAL ::= [+-]? [0-9]* '.' [0-9]+
DOUBLE ::= [+-]? ([0-9]+ '.' [0-9]* EXPONENT | '.' [0-9]+ EXPONENT | [0-9]+ EXPONENT)
EXPONENT ::= [eE] [+-]? [0-9]+
STRING_LITERAL_QUOTE ::= '"' ([^#x22#x5C#xA#xD] | ECHAR | UCHAR)* '"'      /* #x22=" #x5C=\ #xA=new line #xD=carriage return */
STRING_LITERAL_SINGLE_QUOTE ::= "'" ([^#x27#x5C#xA#xD] | ECHAR | UCHAR)* "'"      /* #x27=' #x5C=\ #xA=new line #xD=carriage return */
STRING_LITERAL_LONG_SINGLE_QUOTE ::= "'''" (("'" | "''")? ([^'\] | ECHAR | UCHAR))* "'''"
STRING_LITERAL_LONG_QUOTE ::= '"""' (('"' | '""')? ([^"\] | ECHAR | UCHAR))* '"""'
UCHAR ::= '\\u' HEX HEX HEX HEX | '\\U' HEX HEX HEX HEX HEX HEX HEX HEX
ECHAR ::= '\' [tbnrf"'\]
WS ::= #x20 | #x9 | #xD | #xA /* #x20=space #x9=character tabulation #xD=carriage return #xA=new line */
ANON ::= '[' WS* ']'
PN_CHARS_BASE ::= [A-Z] | [a-z] | [#x00C0-#x00D6] | [#x00D8-#x00F6] | [#x00F8-#x02FF] | [#x0370-#x037D] | [#x037F-#x1FFF] | [#x200C-#x200D] | [#x2070-#x218F] | [#x2C00-#x2FEF] | [#x3001-#xD7FF] | [#xF900-#xFDCF] | [#xFDF0-#xFFFD] | [#x10000-#xEFFFF]
PN_CHARS_U ::= PN_CHARS_BASE | '_'
PN_CHARS ::= PN_CHARS_U | '-' | [0-9] | #x00B7 | [#x0300-#x036F] | [#x203F-#x2040]
PN_PREFIX ::= PN_CHARS_BASE ((PN_CHARS | '.')* PN_CHARS)?
PN_LOCAL ::= (PN_CHARS_U | ':' | [0-9] | PLX) ((PN_CHARS | '.' | ':' | PLX)* (PN_CHARS | ':' | PLX))?
PLX ::= PERCENT | PN_LOCAL_ESC
PERCENT ::= '%' HEX HEX
HEX ::= [0-9] | [A-F] | [a-f]
PN_LOCAL_ESC ::= '\' ('_' | '~' | '.' | '-' | '!' | '$' | '&' | "'" | '(' | ')' | '*' | '+' | ',' | ';' | '=' | '/' | '?' | '#' | '@' | '%')
      

4. Abstract Syntax

The LD Patch data model makes use of the commonly defined Abstract Data Types Set, List and Option, used here as type constructors. For example, Set(A) denotes the type for the sets of elements of type A.

LDPatch ::= List(Statement)

Statement ::= Add | AddList | Delete | Bind | UpdateList
Add       ::= (Subject, Predicate, Object)
AddList   ::= (Subject, Predicate, List(Object))
Delete    ::= (Subject, Predicate, Object)
Bind      ::= (Var, Value, Path)
UpdateList   ::= (Subject, Predicate, Slice, List(Object))

Path         ::= List(PathElement)
PathElement  ::= Step | Constraint
Step         ::= StepForward | StepBackward | StepAt
Constraint   ::= Filter | UNICITY_CONSTRAINT
StepForward  ::= IRI
StepBackward ::= IRI
StepAt       ::= Integer
Filter       ::= (Path, Option(Value))

Slice            ::= Range | EverythingAfter | END
Range            ::= (Integer, Integer)
EverythingAfter  ::= Integer

Subject   ::= IRI | BlankNode | Var
Predicate ::= IRI
Object    ::= IRI | BlankNode | Literal | Var
Value     ::= IRI | Literal | Var

Var       ::= String
IRI       ::= RDF URI-reference http://www.w3.org/TR/2014/REC-rdf11-concepts-20140225/#section-IRIs as subsequently restricted by SPARQL http://www.w3.org/TR/rdf-sparql-query/#docTerminology
BlankNode ::= RDF blank node http://www.w3.org/TR/2014/REC-rdf11-concepts-20140225/#section-blank-nodes
Literal   ::= RDF Literal http://www.w3.org/TR/2014/REC-rdf11-concepts-20140225/#section-Graph-Literal
String    ::= a Unicode String
      

5. Operational Semantics

LD Patch abides to the semantics of the HTTP PATCH method, in that the server MUST apply the entire set of changes atomically and never provide (e.g., in response to a GET during this operation) a partially modified representation. If the entire patch document cannot be successfully applied (e.g., one of the instructions has failed), then the server MUST NOT apply any of the changes.

A. Acknowledgements

This section is non-normative.

TODO

B. Internet Media Type, File Extension and Macintosh File Type

TODO: here comes the section about "text/ldpatch" registration.

C. References

C.1 Normative references

[LDP]
Steve Speicher; John Arwe; Ashok Malhotra. Linked Data Platform 1.0. 19 June 2014. W3C Candidate Recommendation. URL: http://www.w3.org/TR/ldp/
[rdf11-concepts]
Richard Cyganiak; David Wood; Markus Lanthaler. RDF 1.1 Concepts and Abstract Syntax. 25 February 2014. W3C Recommendation. URL: http://www.w3.org/TR/rdf11-concepts/
[rfc5789]
L. Dusseault; J. Snell. PATCH Method for HTTP. March 2010. Proposed Standard. URL: http://www.ietf.org/rfc/rfc5789.txt

C.2 Informative references

[sparql11-query]
Steven Harris; Andy Seaborne. SPARQL 1.1 Query Language. 21 March 2013. W3C Recommendation. URL: http://www.w3.org/TR/sparql11-query/
[sparql11-update]
Paul Gearon; Alexandre Passant; Axel Polleres. SPARQL 1.1 Update. 21 March 2013. W3C Recommendation. URL: http://www.w3.org/TR/sparql11-update/
[turtle]
Eric Prud'hommeaux; Gavin Carothers. RDF 1.1 Turtle. 25 February 2014. W3C Recommendation. URL: http://www.w3.org/TR/turtle/