initial LD Patch WD ldpatch
authorAlexandre Bertails <bertails@gmail.com>
Wed, 09 Jul 2014 20:41:04 -0400
branchldpatch
changeset 702 73a7b38f2dc6
parent 701 d64b9d9aad22
child 703 d272f5f55195
initial LD Patch WD
ldpatch.html
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/ldpatch.html	Wed Jul 09 20:41:04 2014 -0400
@@ -0,0 +1,674 @@
+<!DOCTYPE html>
+<html>
+  <head>
+    <title>Linked Data Patch Format</title>
+    <meta charset='utf-8'>
+    <script src='https://www.w3.org/Tools/respec/respec-w3c-common'
+            async class='remove'></script>
+    <script class='remove'>
+      var preProc = {
+        apply: function(c) {
+                  // terms definitions
+                  refs = document.querySelectorAll('tdef') ;
+                  for (var i = 0; i < refs.length; i++) {
+                      var item = refs[i];
+                      if (!item) continue ;
+                      var p = item.parentNode ;
+                      var con = item.innerHTML ;
+                      var ref = item.getAttribute('title') ;
+                      if (!ref) {
+                          ref = item.textContent ;
+                      }
+                      if (ref) {
+                          ref = ref.replace(/\n/g, '_') ;
+                          ref = ref.replace(/\s+/g, '_') ;
+                      }
+                      var sp = document.createElement( 'dfn' ) ;
+                      sp.title = ref ;
+                      sp.innerHTML = con ;
+                      p.replaceChild(sp, item) ;
+                  }
+                  // term references
+                  refs = document.querySelectorAll('tref') ;
+                  for (var i = 0; i < refs.length; i++) {
+                      var item = refs[i];
+                      if (!item) continue ;
+                      var p = item.parentNode ;
+                      var con = item.innerHTML ;
+                      var ref = item.getAttribute('title') ;
+                      if (!ref) {
+                          ref = item.textContent ;
+                      }
+                      if (ref) {
+                          ref = ref.replace(/\n/g, '_') ;
+                          ref = ref.replace(/\s+/g, '_') ;
+                      }
+
+                      var sp = document.createElement( 'a' ) ;
+                      var id = item.textContent ;
+                      sp.className = 'tref' ;
+                      sp.title = ref ;
+                      sp.innerHTML = con ;
+                      p.replaceChild(sp, item) ;
+                  }
+              }
+      };
+
+      function updateExample(doc, content) {
+        // perform transformations to make it render and prettier
+        content = content.replace(/<!--/, '');
+        content = content.replace(/-->/, '');
+        content = doc._esc(content);
+        content = content.replace(/\*\*\*\*([^*]*)\*\*\*\*/g, '<span class="hilite">$1</span>') ;
+        return content ;
+      };
+
+      function updateDTD(doc, content) {
+        // perform transformations to
+        // make it render and prettier
+        content = '<pre class="dtd">' + doc._esc(content) + '</pre>';
+        content = content.replace(/!ENTITY % ([^ \t\r\n]*)/g, '!ENTITY <span class="entity">% $1</span>');
+        content = content.replace(/!ELEMENT ([^ \t$]*)/mg, '!ELEMENT <span class="element">$1</span>');
+        return content;
+      };
+
+      function updateSchema(doc, content) {
+        // perform transformations to
+        // make it render and prettier
+        content = '<pre class="dtd">' + doc._esc(content) + '</pre>';
+        content = content.replace(/&lt;xs:element\s+name=&quot;([^&]*)&quot;/g, '&lt;xs:element name="<span class="element" id="schema_element_$1">$1</span>"') ;
+        return content;
+      };
+
+      function updateTTL(doc, content) {
+        // perform transformations to
+        // make it render and prettier
+        content = '<pre class="sh_sourceCode">' + doc._esc(content) + '</pre>';
+        content = content.replace(/@prefix/g, '<span class="sh_keyword">@prefix</span>');
+        return content;
+      };
+
+      var respecConfig = {
+          // specification status (e.g. WD, LCWD, WG-NOTE, etc.). If in doubt use ED.
+          specStatus:           "ED",
+          
+          // the specification's short name, as in http://www.w3.org/TR/short-name/
+          shortName:            "ld-patch",
+
+          // if your specification has a subtitle that goes below the main
+          // formal title, define it here
+          // subtitle   :  "an excellent document",
+
+          // if you wish the publication date to be other than the last modification, set this
+          // publishDate:  "2009-08-06",
+
+          // if the specification's copyright date is a range of years, specify
+          // the start date here:
+          // copyrightStart: "2005"
+
+          // if there is a previously published draft, uncomment this and set its YYYY-MM-DD date
+          // and its maturity status
+          // previousPublishDate:  "1977-03-15",
+          // previousMaturity:  "WD",
+
+          // if there a publicly available Editor's Draft, this is the link
+          edDraftURI:           "http://ld-specs.github.io/ld-patch/",
+
+          // if this is a LCWD, uncomment and set the end of its review period
+          // lcEnd: "2009-08-05",
+
+          // editors, add as many as you like
+          // only "name" is required
+          editors:  [
+              {
+                  name:       "Alexandre Bertails"
+              ,   url:        "http://bertails.org/"
+              ,   mailto:     "alexandre@bertails.org"
+              ,   company:    "Pellucid Analytics"
+              ,   companyURL: "http://www.pellucid.com"
+              },
+              {
+                  name:       "Pierre-Antoine Champin"
+              ,   url:        "http://liris.cnrs.fr/~pchampin/en/"
+              ,   mailto:     "pchampin@liris.cnrs.fr"
+              ,   company:    "Université de Lyon"
+              ,   companyURL: "http://www.universite-lyon.fr/"
+              },
+              {
+                  name:       "Andrei Sambra"
+              ,   url:        "https://deiu.rww.io/profile/card#me"
+              ,   mailto:     "asambra@mit.edu"
+              ,   company:    "MIT"
+              ,   companyURL: "http://web.mit.edu"
+              },
+          ],
+
+          // name of the WG
+          wg:           "Linked Data Platform Working Group",
+          
+          // URI of the public WG page
+          wgURI:        "http://www.w3.org/2012/ldp",
+          
+          // name (without the @w3c.org) of the public mailing to which comments are due
+          wgPublicList: "public-ldp-comments",
+          
+          // URI of the patent status for this WG, for Rec-track documents
+          // !!!! IMPORTANT !!!!
+          // This is important for Rec-track documents, do not copy a patent URI from a random
+          // document unless you know what you're doing. If in doubt ask your friendly neighbourhood
+          // Team Contact.
+          wgPatentURI:  "http://www.w3.org/Consortium/Patent-Policy-20040205/",
+          // !!!! IMPORTANT !!!! MAKE THE ABOVE BLINK IN YOUR HEAD
+          preProcess: [ preProc ]
+      };
+    </script>
+  </head>
+  <body>
+    <section id='abstract'>
+      <p>
+Linked Data Patch Format (LD Patch) defines a language for expressing a sequence of operations to apply to a RDF Graph; it is suitable for use with the HTTP PATCH method. The "text/ldpatch" media type is used to identify such Patch documents.
+      </p>
+    </section>
+    
+    <section id='sotd'>
+      <p>
+        @@You need to have a custom SotD paragraph. Maybe give a succinct description of your spec's
+        status.@@
+      </p>
+    </section>
+    
+    <section class='informative' id='introduction'>
+      <h1>Introduction</h1>
+      <p>
+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).
+      </p>
+      <p>
+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. The "text/ldpatch" media type is used to identify such LD Patch documents.
+      </p>
+      <p>
+An instance of the LD Patch language (or LD Patch document) defines a list of operations to be performed against an RDF Graph, namely the addition or removal of RDF triples in this graph.
+      </p>
+      <p>
+        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 <code>&lt;http://example.org/timbl#&gt;</code>) and two events he attended.
+      </p>
+      <pre class='example'>
+@prefix schema: &lt;http://schema.org/&gt; .
+@prefix profile: &lt;http://ogp.me/ns/profile#&gt; .
+@prefix ex: &lt;http://example.org/vocab#&gt; .
+
+&lt;http://example.org/timbl#&gt; a schema:Person ;
+  schema:alternateName "TimBL" ;
+  profile:first_name "Tim" ;
+  profile:last_name "Berners-Lee" ;
+  schema:workLocation [ schema:name "W3C/MIT" ] ;
+  schema:attendee _:b1, _:b2 ;
+  ex:preferredLanguages ( "en" "fr" ).
+
+_:b1  ;
+  schema:name "F2F5 - Linked Data Platform" ;
+  schema:url &lt;https://www.w3.org/2012/ldp/wiki/F2F5&gt; .
+
+_:b2 a schema:Event ;
+  schema:name "TED 2009" ;
+  schema:startDate "2009-02-04" .
+  schema:url &lt;http://conferences.ted.com/TED2009/&gt; .
+      </pre>
+      <p>
+The following is an example HTTP Patch request, conveying an LD Patch document:
+      </p>
+      <pre class='example'>
+PATCH /timbl HTTP/1.1
+Host: example.org
+Content-Length: 478
+Content-Type: text/ldpatch
+If-Match: "abc123"
+
+@prefix rdf: &lt;http://www.w3.org/1999/02/22-rdf-syntax-ns#&gt; .
+@prefix schema: &lt;http://schema.org&gt; .
+@prefix profile: &lt;http://ogp.me/ns/profile#&gt; .
+@prefix ex: &lt;http://example.org/vocab#&gt; .
+
+Delete &lt;#&gt; profile:first_name "Tim" .
+Add    &lt;#&gt; profile:first_name "Timothy" .
+
+UpdateList &lt;#&gt; ex:preferredLanguages 1>2 ( "fr-CH" ) .
+
+Bind ?event &lt;#&gt; /schema:attendee[/schema:url = &lt;http://conferences.ted.com/TED2009/&gt;]  .
+Add ?event rdf:type schema:Event .
+
+Bind ?ted &lt;http://conferences.ted.com/TED2009/&gt; /-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" .
+      </pre>
+      <p>
+This example introduces most features of the LD Patch format: @prefix and prefixed names, the <tref>Add</tref>, <tref>Delete</tref> and <tref>UpdateList</tref> operations, the <tref>Bind</tref>-ing mechanism and blank node creation.
+      </p>
+      <p>
+The following is the resulting (patched) document.
+      </p>
+      <pre class='example'>
+@prefix schema: &lt;http://schema.org/&gt; .
+@prefix profile: &lt;http://ogp.me/ns/profile#&gt; .
+@prefix ex: &lt;http://example.org/vocab#&gt; .
+
+&lt;http://example.org/timbl#&gt; a schema:Person ;
+  schema:alternateName "TimBL" ;
+  profile:first_name "Timothy" ;
+  profile:last_name "Berners-Lee" ;
+  schema:workLocation [ schema:name "W3C/MIT" ] ;
+  schema:attendee _:b1, _:b2 ;
+  ex:preferredLanguages ( "en" "fr-CH" ).
+
+_:b1  ;
+  schema:name "F2F5 - Linked Data Platform" ;
+  schema:url &lt;https://www.w3.org/2012/ldp/wiki/F2F5&gt; .
+
+_:b2 a schema:Event ;
+  schema:name "TED 2009" ;
+  schema:url &lt;http://conferences.ted.com/TED2009/&gt; ;
+  schema:location [
+    schema:name "Long Beach, California";
+    schema:geo [ schema:latitude "33.7817" ; schema:longitude "-118.2054" ] .
+  ] .
+      </pre>
+
+
+    </section>
+
+<!--      <p id='expressive-power'>
+        The scope of LD Patch is intentionally limited when compared to SPARQL Update capabilities. Its expressive power is limited to (relative) RDF Graphs. Matching nodes is achieved using property paths. Nodes can be bound to variables. The language includes support for blank nodes and RDF Lists.
+      </p>
+      <p id='design-choices'>
+        The authors of the document made conscious choices when designing the LD Patch language. Here are a few:
+        <ul>
+          <li>LD Patch was thought to be used in Linked Data applications. It is <strong>not</strong> designed for general purpose RDF applications.</li>
+          <li>if more expressive power is desired, the authors recommends the use of SPARQL Update.</li>
+          <li>LD Patch is not design to describe diffs between RDF Graphs: it is meants to be used in applications as a real patching language. That being said, it is strongly inspired from <a href="http://afs.github.io/rdf-patch/">RDF Patch</a> and is (mostly?) a superset.</li>
+          <li>compatibity with SPARQL Update was not sought as there is no intention to make LD Patch's semantics a subset of SPARQL Update's. As a result, an LDP Patch instance is not a valid SPARQL update query.</li>
+          <li>being able to match Blank Nodes is a desired and non-negociable property</li>
+          <li>good performance characteristics of the operational semantics requires some trade-offs in the features of the language.</li>
+          <li></li>
+        </ul>
+      </p>
+
+-->
+
+       
+    <section class='informative' id='language-features'>
+      <h1>LD Patch format</h1>
+      <p>
+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 <tref>prefixes</tref> used to abbreviate URIs. Then each statement either binds a variable to a matching node, or defines a modification on the graph.
+      </p>
+      <p>
+
+      </p>
+      <section>
+        <h2><tdef>Prefixes</tdef></h2>
+        <p>
+LD Patch offers the possibility to abbreviate URIs by using Turtle's <i>@prefix</i> 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.
+        </p>
+        <p>
+Once a prefix such as <code>@prefix foo: &lt;http://example.org/ns#&gt;</code> is defined, any mention of a URI later in the document may use a <tref>PrefixedName</tref> that starts with <code>foo:</code> to stand for the longer URI. So for example, the <tref>PrefixedName</tref> <code>foo:bar</code> is a shorthand for the URI <code>&lt;http://example.org/ns#bar&gt;</code>.
+        </p>
+      </section>
+
+      <section>
+        <h2><tdef>Node matching semantics</tdef></h2>
+        <p>
+LD Patch borrows much of its syntax to Turtle (@@@ref) and SPARQL (@@@ref) 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 <em>fresh</em> blank node, that needs to be created in the patched RDF graph. (@@@ remark that this is different from RDF-Patch)
+        </p>
+        <p>
+In order to be able to address blank nodes already present in the graph, LD Patch has two mechanisms: <tref>Bind</tref>ing a variable to a blank node reachable with a <tref>path expression</tref>, and <tref>UpdateList</tref> 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. (@@@give here an example of pathological graph)
+        </p>
+      </section>
+
+      <section>
+        <h2><tdef>Path expression</tdef></h2>
+        <p>
+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:
+        </p>
+        <ul>
+          <li>A <tref>StepForward</tref> is defined by a URI, and consists in following outgoing arcs having that URI as their predicate.</li>
+          <li>A <tref>StepBackward</tref> is defined by a URI preceded with the minus ("-") sign, and consists in following incoming arcs having that URI as their predicate.</li>
+          <li>A <tref>StepAt</tref> is defined by an integer <i>n</i>, and consists in following <i>n</i> <code>rdf:rest</code> arcs and one <code>rdf:first</code> arc in order to reach the corresponding member of an RDF collection.</li>
+        </ul>
+        <p>
+Note that each step can, in general, result in <em>several</em> matching nodes, as a given node can have several (incoming or outgoing) arcs with the same predicate.
+        </p>
+        <p>
+A Path may also contains <tref>Constraint</tref>s, which are of two kinds:
+        </p>
+        <ul>
+          <li>A unicity constraint, described by the <em>bang</em> ("!") character, ensures that the result of the path so far contains exactly one node.</li>
+          <li>A <tref>filter</tref>, consisting of a path in square brackets ("[", "]"), keeps only from the matching nodes so far those that “satisfy” the enclosed path, i.e. those from which the enclosed path reaches at least one node.</li>
+          <li>Additionally, the path in a <tref>filter</tref> can be followed by the equal ("=") sign and a <tref>Value</tref>. In that case, only the node for which that particular value is reached through the enclosed path are kept.</li>
+        </ul>
+        <p>
+The path below (taken from our running example) will look for all the events attended by the starting node, and keep only those  having <code>&lt;http://conferences.ted.com/TED2009/&gt;</code> as their URL.
+        <pre class='example'>
+/schema:attendee[/schema:url = &lt;http://conferences.ted.com/TED2009/&gt;]
+        </pre>
+        </p>
+      </section>
+
+      <section>
+        <h2><tdef>Bind</tdef></h2>
+        <p>
+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 (@@@ but a variable _can_ be redefined). Following the example above, the Bind operation creates a new variable called <code>event</code>, starting from the RDF Term <code>&lt;#&gt;</code> and following the path expression <code>/schema:attendee[/schema:url = &lt;http://conferences.ted.com/TED2009/&gt;]</code> in order to identify the RDF Term to which this variable will point -- i.e. <code>_:b2</code>.
+        <pre class='example'>
+...
+Bind ?event &lt;#&gt; /schema:attendee[/schema:url = &lt;http://conferences.ted.com/TED2009/&gt;] .
+...
+        </pre>
+        </p>
+        <p>
+The Bind operation is defined by three components: <tref>Var</tref>, <tref>Value</tref> and <tref>Path</tref>, the last component being optional.
+        </p>
+        <p>
+<tref>Var</tref> contains a unique name for the new variable. Variables are prefixed by "?"; the "?" character is not part of the variable name.
+        </p>
+        <p>
+<tref>Value</tref> is the RDF Term that will be used as starting point when following the path expression.
+        </p>
+        <p>
+<tref>Path</tref> is the expression that is used to identify the RDF Term to which the Variable will point. It is comprised of <tref>Step</tref>(s) and/or <tref>Constraint</tref>(s).
+        </p>
+      </section>
+
+      <section>
+        <h2><tdef>Add</tdef></h2>
+        <p>
+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 <tref>Subject</tref>, a <tref>Predicate</tref> and either an <tref>Object</tref> or a <tref>List</tref>.
+        <pre class='example'>
+...
+Add    &lt;#&gt; profile:first_name "Timothy" .
+...
+Add ?event rdf:type schema:Event .
+...
+        </pre>
+When the third component is an <tref>Object</tref>, then a single statement will be added. On the other hand, when it is a <tref>List</tref>, all the intermediate blank nodes and corresponding statements will be added to construct a well formed RDF collection (@@@ref to RDF-Schema) (in addition to the triple with the given <tref>Subject</tref>, <tref>Predicate</tref> and that collection as the object).
+        </p>
+      </section>
+
+      <section>
+        <h2><tdef>Delete</tdef></h2>
+        <p>
+The Delete operation is used to remove a single RDF triple from the existing graph. The syntax for the Delete operation requires a <tref>Subject</tref>, a <tref>Predicate</tref> and an <tref>Object</tref>.
+        <pre class='example'>
+...
+Delete &lt;#&gt; profile:first_name "Tim" .
+...
+Delete ?ted schema:startDate "2009-02-04".
+...
+        </pre>
+        </p>
+      </section>
+
+      <section>
+        <h2><tdef>UpdateList</tdef></h2>
+        <p>
+The UpdateList operation is used to update the members of an RDF collection (@@@ref). That collection is supposed to be the object of a triple, specified by its <tref>Subject</tref> and <tref>Predicate</tref>. A <tref>Slice</tref> specification then describes which members (if any) of the collections are affected by the operation, and then a <tref>List</tref> 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".
+        <pre class='example'>
+...
+UpdateList &lt;#&gt; ex:preferredLanguages 1>2 ( "fr-CH" ) .
+...
+        </pre>
+        </p>
+        <p>
+UpdateList works in a similar way to <a href="https://docs.python.org/3/reference/expressions.html#slicings">slicing in Python</a> 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.
+        </p>
+        <p>
+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. @@@TODO eplain that indexes start at 0  @@@TODO give some examples here.
+        </p>
+      </section>
+
+    </section>
+
+
+    <section id='concrete-syntax'>
+      <h1>Concrete Syntax</h1>
+      <p>
+      </p>
+      <pre>
+<tdef>LDPatch</tdef> ::= Prologue Statement*
+<tdef>Prologue</tdef> ::= <tref>prefixID</tref>*
+<tdef>Statement</tdef> ::= <tref>Bind</tref> | <tref>Add</tref> | <tref>Delete</tref> | <tref>UpdateList</tref>
+<tref>Bind</tref> ::= ("Bind" | "B") <tref>Var</tref> <tref>Value</tref> <tref>Path</tref>? "."
+<tref>Add</tref> ::= ("Add" | "A") <tref>Subject</tref> <tref>Predicate</tref> ( <tref>Object</tref> | <tref>List</tref> ) "."
+<tref>Delete</tref> ::= ("Delete" | "D") <tref>Subject</tref> <tref>Predicate</tref> <tref>Object</tref> "."
+<tref>UpdateList</tref> ::= ("UpdateList" | "UL") <tref>Subject</tref> <tref>Predicate</tref> <tref>Slice</tref> <tref>List</tref> "."
+
+<tdef>Subject</tdef> ::= <tref>iri</tref> | <tref>BlankNode</tref> | <tref>Var</tref>
+<tdef>Predicate</tdef> ::= <tref>iri</tref>
+<tdef>Object</tdef> ::= <tref>iri</tref> | <tref>BlankNode</tref> | <tref>literal</tref> | <tref>Var</tref>
+<tdef>Value</tdef> ::= <tref>iri</tref> | <tref>literal</tref> | <tref>Var</tref>
+<tdef>List</tdef> ::= '(' <tref>Object</tref>* ')'
+
+<tref>Path</tref> ::= ( <tref>Step</tref> | <tref>Constraint</tref> )*
+<tdef>Step</tdef> ::= '/' ( '-' <tref>iri</tref> | <tref>iri</tref> | <tref>INDEX</tref> )
+<tdef>Constraint</tdef> ::= '[' <tref>Path</tref> ( '=' <tref>Value</tref> )? ']' | '!'
+
+<tdef>Slice</tdef> ::= <tref>INDEX</tref>? '&gt;' <tref>INDEX</tref>?
+<tdef>INDEX</tdef> ::= [0-9]+
+
+// copied from SPARQL
+
+// supposed to be `Var ::= VAR1 | VAR2` but here only VAR1
+<tref>Var</tref> ::= '?' <tref>VARNAME</tref>
+<tdef>VARNAME</tdef> ::= ( <tref>PN_CHARS_U</tref> | [0-9] ) ( <tref>PN_CHARS_U</tref> | [0-9] | #x00B7 | [#x0300-#x036F] | [#x203F-#x2040] )*
+
+// copied from Turtle
+
+<tdef>prefixID</tdef> ::= "@prefix" PNAME_NS IRIREF "."
+<tref>Literal</tref> ::= <tref>RDFLiteral</tref> | <tref>NumericLiteral</tref> | <tref>BooleanLiteral</tref>
+<tdef>NumericLiteral</tdef> ::= <tref>INTEGER</tref> | <tref>DECIMAL</tref> | <tref>DOUBLE</tref>
+<tdef>RDFLiteral</tdef> ::= <tref>String</tref> (<tref>LANGTAG</tref> | '^^' <tref>iri</tref>)?
+<tdef>BooleanLiteral</tdef> ::= 'true' | 'false'
+<tref>String</tref> ::= <tref>STRING_LITERAL_QUOTE</tref> | <tref>STRING_LITERAL_SINGLE_QUOTE</tref> | <tref>STRING_LITERAL_LONG_SINGLE_QUOTE</tref> | <tref>STRING_LITERAL_LONG_QUOTE</tref>
+<tref>iri</tref> ::= <tref>IRIREF</tref> | <tref>PrefixedName</tref>
+<tdef>PrefixedName</tdef> ::= <tref>PNAME_LN</tref> | <tref>PNAME_NS</tref>
+<tref>BlankNode</tref> ::= <tref>BLANK_NODE_LABEL</tref> | <tref>ANON</tref>
+<tdef>IRIREF</tdef> ::= '&lt;' ([^#x00-#x20&lt;&gt;"{}|^`\] | <tref>UCHAR</tref>)* '&gt;' /* #x00=NULL #01-#x1F=control codes #x20=space */
+<tdef>PNAME_NS</tdef> ::= <tref>PN_PREFIX</tref>? ':'
+<tdef>PNAME_LN</tdef> ::= <tref>PNAME_NS</tref> <tref>PN_LOCAL</tref>
+<tdef>BLANK_NODE_LABEL</tdef> ::= '_:' (<tref>PN_CHARS_U</tref> | [0-9]) ((<tref>PN_CHARS</tref> | '.')* <tref>PN_CHARS</tref>)?
+<tdef>LANGTAG</tdef> ::= '@' [a-zA-Z]+ ('-' [a-zA-Z0-9]+)*
+<tdef>INTEGER</tdef> ::= [+-]? [0-9]+
+<tdef>DECIMAL</tdef> ::= [+-]? [0-9]* '.' [0-9]+
+<tdef>DOUBLE</tdef> ::= [+-]? ([0-9]+ '.' [0-9]* <tref>EXPONENT</tref> | '.' [0-9]+ <tref>EXPONENT</tref> | [0-9]+ <tref>EXPONENT</tref>)
+<tdef>EXPONENT</tdef> ::= [eE] [+-]? [0-9]+
+<tdef>STRING_LITERAL_QUOTE</tdef> ::= '"' ([^#x22#x5C#xA#xD] | <tref>ECHAR</tref> | <tref>UCHAR</tref>)* '"'      /* #x22=" #x5C=\ #xA=new line #xD=carriage return */
+<tdef>STRING_LITERAL_SINGLE_QUOTE</tdef> ::= "'" ([^#x27#x5C#xA#xD] | <tref>ECHAR</tref> | <tref>UCHAR</tref>)* "'"      /* #x27=' #x5C=\ #xA=new line #xD=carriage return */
+<tdef>STRING_LITERAL_LONG_SINGLE_QUOTE</tdef> ::= "'''" (("'" | "''")? ([^'\] | <tref>ECHAR</tref> | <tref>UCHAR</tref>))* "'''"
+<tdef>STRING_LITERAL_LONG_QUOTE</tdef> ::= '"""' (('"' | '""')? ([^"\] | <tref>ECHAR</tref> | <tref>UCHAR</tref>))* '"""'
+<tdef>UCHAR</tdef> ::= '\\u' <tref>HEX</tref> <tref>HEX</tref> <tref>HEX</tref> <tref>HEX</tref> | '\\U' <tref>HEX</tref> <tref>HEX</tref> <tref>HEX</tref> <tref>HEX</tref> <tref>HEX</tref> <tref>HEX</tref> <tref>HEX</tref> <tref>HEX</tref>
+<tdef>ECHAR</tdef> ::= '\' [tbnrf"'\]
+<tdef>WS</tdef> ::= #x20 | #x9 | #xD | #xA /* #x20=space #x9=character tabulation #xD=carriage return #xA=new line */
+<tdef>ANON</tdef> ::= '[' <tref>WS</tref>* ']'
+<tdef>PN_CHARS_BASE</tdef> ::= [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]
+<tdef>PN_CHARS_U</tdef> ::= <tref>PN_CHARS_BASE</tref> | '_'
+<tdef>PN_CHARS</tdef> ::= <tref>PN_CHARS_U</tref> | '-' | [0-9] | #x00B7 | [#x0300-#x036F] | [#x203F-#x2040]
+<tdef>PN_PREFIX</tdef> ::= <tref>PN_CHARS_BASE</tref> ((<tref>PN_CHARS</tref> | '.')* <tref>PN_CHARS</tref>)?
+<tdef>PN_LOCAL</tdef> ::= (<tref>PN_CHARS_U</tref> | ':' | [0-9] | <tref>PLX</tref>) ((<tref>PN_CHARS</tref> | '.' | ':' | <tref>PLX</tref>)* (<tref>PN_CHARS</tref> | ':' | <tref>PLX</tref>))?
+<tdef>PLX</tdef> ::= <tref>PERCENT</tref> | <tref>PN_LOCAL_ESC</tref>
+<tdef>PERCENT</tdef> ::= '%' <tref>HEX</tref> <tref>HEX</tref>
+<tdef>HEX</tdef> ::= [0-9] | [A-F] | [a-f]
+<tdef>PN_LOCAL_ESC</tdef> ::= '\' ('_' | '~' | '.' | '-' | '!' | '$' | '&amp;' | "'" | '(' | ')' | '*' | '+' | ',' | ';' | '=' | '/' | '?' | '#' | '@' | '%')
+      </pre>
+    </section>
+
+    <section id='abstract-syntax'>
+      <h1>Abstract Syntax</h1>
+      <p>
+The LD Patch data model makes use of the commonly defined <a href="http://en.wikipedia.org/wiki/Abstract_data_type">Abstract Data Types</a> <a href="http://en.wikipedia.org/wiki/Set_(computer_science)">Set</a>, <a href="http://en.wikipedia.org/wiki/List_(computer_science)">List</a> and <a href="http://en.wikipedia.org/wiki/Option_type">Option</a>, used here as type constructors. For example, <code>Set(A)</code> denotes the type for the sets of elements of type <code>A</code>. We assume that they come with their common operations, such as the function <code>size&nbsp;:&nbsp;Set&nbsp;→&nbsp;Int</code>.					
+      </p>
+      <pre>
+<tref>LDPatch</tref> ::= <tref>List</tref>(<tref>Statement</tref>)
+
+<tref>Statement</tref> ::= <tref>Add</tref> | <tref>AddList</tref> | <tref>Delete</tref> | <tref>Bind</tref> | <tref>UpdateList</tref>
+<tref>Add</tref>       ::= (<tref>Subject</tref>, <tref>Predicate</tref>, <tref>Object</tref>)
+<tdef>AddList</tdef>   ::= (<tref>Subject</tref>, <tref>Predicate</tref>, <tref>List</tref>(<tref>Object</tref>))
+<tref>Delete</tref>    ::= (<tref>Subject</tref>, <tref>Predicate</tref>, <tref>Object</tref>)
+<tref>Bind</tref>      ::= (<tref>Var</tref>, <tref>Value</tref>, <tref>Path</tref>)
+<tref>UpdateList</tref>   ::= (<tref>Subject</tref>, <tref>Predicate</tref>, <tref>Slice</tref>, <tref>List</tref>(<tref>Object</tref>))
+
+<tdef>Path</tdef>         ::= <tref>List</tref>(<tref>PathElement</tref>)
+<tdef>PathElement</tdef>  ::= <tref>Step</tref> | <tref>Constraint</tref>
+<tref>Step</tref>         ::= <tref>StepForward</tref> | <tref>StepBackward</tref> | <tref>StepAt</tref>
+<tref>Constraint</tref>   ::= <tref>Filter</tref> | UNICITY_CONSTRAINT
+<tdef>StepForward</tdef>  ::= <tref>IRI</tref>
+<tdef>StepBackward</tdef> ::= <tref>IRI</tref>
+<tdef>StepAt</tdef>       ::= <tref>Integer</tref>
+<tdef>Filter</tdef>       ::= (<tref>Path</tref>, Option(<tref>Value</tref>))
+
+<tref>Slice</tref>            ::= <tref>Range</tref> | <tref>EverythingAfter</tref> | END
+<tdef>Range</tdef>            ::= (<tref>Integer</tref>, <tref>Integer</tref>)
+<tdef>EverythingAfter</tdef>  ::= <tref>Integer</tref>
+
+<tref>Subject</tref>   ::= <tref>IRI</tref> | <tref>BlankNode</tref> | <tref>Var</tref>
+<tref>Predicate</tref> ::= <tref>IRI</tref>
+<tref>Object</tref>    ::= <tref>IRI</tref> | <tref>BlankNode</tref> | <tref>Literal</tref> | <tref>Var</tref>
+<tref>Value</tref>     ::= <tref>IRI</tref> | <tref>Literal</tref> | <tref>Var</tref>
+
+<tdef>Var</tdef>       ::= <tref>String</tref>
+<tdef>IRI</tdef>       ::= 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
+<tdef>BlankNode</tdef> ::= RDF blank node http://www.w3.org/TR/2014/REC-rdf11-concepts-20140225/#section-blank-nodes
+<tdef>Literal</tdef>   ::= RDF Literal http://www.w3.org/TR/2014/REC-rdf11-concepts-20140225/#section-Graph-Literal
+<tdef>String</tdef>    ::= a Unicode String
+      </pre>
+
+    </section>
+    
+    <section id='operational-semantics'>
+      <h1>Operational Semantics</h1>
+      <p>
+The denotational RDF semantics makes use of the <a href="http://en.wikipedia.org/wiki/Set-builder_notation">set-builder notation</a> for building the RDF sets.
+      </p>
+      <p>@@TODO@@</p>
+      <p>
+LD Patch abides to the semantics of the <a href="http://tools.ietf.org/html/rfc5789" target="_blank">HTTP PATCH method</a>, 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.
+      </p>
+<!--pre>An Env(ironment) is a Map from Var-s to Node-s
+Env      ::= Map(Var, Set(Node))
+
+TBD
+---
+
+env[x]
+env[x -> nodes]
+
+matchTriples: Graph -> Option(Node) -> Uri -> Option(Node) -> Set((Node, Uri, Node))
+matchTriples: (g: Graph) -> (s: Option(Node)) -> (p: Uri) -> (o: Option(Node)) -> { matchingTriples: Set((Node, Uri, Node)) | triple matches the pattern (s, p, o) in g -> triple ∈ matchingNodes }
+
++: Graph -> Set(Triple) -> Graph
+
+-: Graph -> Set(Triple) -> Graph
+
+sem functions
+-------------
+
+sem_varOrConcreteNode is a function that maps a Var to a Node or a ConcreteNode to itself
+sem_varOrConcreteNode: Env -> VarOrConcreteNode -> Set(Node)
+sem_varOrConcreteNode(env, v: Var) = env[v]
+sem_varOrConcreteNode(env, uri: Uri) = Set(uri)
+sem_varOrConcreteNode(env, literal: Literal) = Set(literal)
+
+sem_matchingNodes: Graph -> Set(Node) -> Path -> Set(Node)
+sem_matchingNodes(graph, nodes, List()) = nodes
+sem_matchingNodes(graph, nodes, (Forward, uri, mode) :: restPath) =
+  let triples = { matchTriples(graph, node, uri, ANY) | node ∈ nodes } in
+  let matchingNodes = { o | (s, p, o) ∈ triples } in
+  if mode is Single and size(matchingNodes) is not 1 then throw error
+  sem_matchingNodes(graph, matchingNodes, restPath)
+sem_matchingNodes(graph, nodes, (Backward, uri, mode) :: restPath) =
+  let triples = { matchTriples(graph, ANY, uri, node) | node ∈ nodes } in
+  let matchingNodes = { s | (s, p, o) ∈ triples } in
+  if mode is Single and size(matchingNodes) is not 1 then throw error
+  sem_matchingNodes(graph, matchingNodes, restPath)
+
+makeTriples: Set(Node) -> OrientedPredicate -> Node -> Set(Triple)
+makeTriples(nodes, (Forward, uri), node) =
+  { (n, uri, node) | n ∈ nodes }
+makeTriples(nodes, (Backward, uri), node) =
+  { (node, uri, n) | n ∈ nodes }
+
+
+sem_bind: (Env, Graph) -> Bind -> (Env, Graph)
+sem_bind((env, graph), Bind(start, path, v)) =
+  let nodes = sem_matchingNodes(sem_varOrConcreteNode(graph, env, start), path) in
+  (env[v -> nodes], graph)
+
+sem_add: (Env, Graph) -> Add -> (Env, Graph)
+sem_add((env, graph), Add(start, path, orientedPredicate, (node, pgTriples))) =
+  let nodes = sem_matchingNodes(sem_varOrConcreteNode(graph, env, start), path) in  
+  let triples = makeTriples(nodes, orientedPredicate, node) in
+  (env, graph + triples + pgTriples)
+
+
+sem_delete: (Env, Graph) -> Delete -> (Env, Graph)
+sem_delete((env, graph), Delete(start, path, orientedPredicate, None)) =
+  let nodes = sem_matchingNodes(sem_varOrConcreteNode(graph, env, start), path) in
+  let triples = { matchTriples(graph, node, orientedPredicate, None) | node ∈ nodes } in
+  (env, graph - triples)
+sem_delete((env, graph), Delete(start, path, orientedPredicate, Some((node, pgTriples)))) =
+  let nodes = sem_matchingNodes(sem_varOrConcreteNode(graph, env, start), path) in
+  let triples = { matchTriples(graph, node, orientedPredicate, Some(node)) | node ∈ nodes } in
+  (env, graph - triples - pgTriples)
+
+sem_cut: (Env, Graph) -> Cut -> (Env, Graph)
+sem_cut((env, graph), Cut(varOrConcreteNode)) =
+  let nodes = sem_varOrConcreteNode(graph, env, varConcreteNode) in
+  let triples = connectedGraph(nodes) in
+  (env, graph = triples)
+
+
+connectedGraph: Graph -> Set(Node) -> Set(Triple)
+connectedGraph(graph, nodes) =
+  let f(triples) = { matchingTriples(o, None, None)  | (s, p, o) ∈ triples } in
+  fixpoint f
+
+
+sem_update: (Env, Graph) -> Update -> (Env, Graph)
+sem_update((env, graph), Update(varOrConcreteNode, (pgNode, pgTriples))) =
+  let nodes = sem_varOrConcreteNode(graph, env, varOrConcreteNode) in
+  let incomingTriples = { matchingTriples(None, None, node) | node ∈ nodes } in
+  let newIncomingTriples = { (s, p, pgNode) | (s, p, _) ∈ incomingTriples } in
+  let connectedTriples = connectedGraph(nodes) in
+  (env, graph - incomingTriples - connectedTriples + newIncomingTriples + pgTriples)
+
+sem_patch: Graph -> List(Statement) -> Graph
+sem_patch(g, statements) = sem_patch_state(({}, g), statements)
+
+sem_statement: (Env, Graph) -> Statement -> (Env, Graph)
+sem_statement(state, bind: Bind) = sem_bind(state, bind)
+sem_statement(state, add: Add) = sem_bind(state, add)
+sem_statement(state, delete: Delete) = sem_bind(state, delete)
+sem_statement(state, update: Update) = sem_bind(state, update)
+
+sem_patch_state: (Env, Graph) -> List(Statement) -> Graph
+sem_patch_state((env, graph), List()) = graph
+sem_patch_state(state, statement :: restStatements) =
+  let newState = sem_statement(state, statement) in
+  sem_patch_state(newState, restStatements)
+
+
+
+
+TODO:
+* runtime error
+* parsing error
+* grammar
+* lists
+* examples
+* best practices
+
+        </pre-->
+    </section>
+    
+
+  </body>
+</html>