improved UpdateList and a number of other things ldpatch
authorPierre-Antoine <pchampin@liris.cnrs.fr>
Fri, 21 Nov 2014 11:23:48 +0100
branchldpatch
changeset 901 caf4bc0d15f0
parent 900 17d919a48bfa
child 902 f6bc6c22fd2b
improved UpdateList and a number of other things
fig-alt-update-list-2.svg
ldpatch.html
--- a/fig-alt-update-list-2.svg	Fri Nov 21 01:31:20 2014 -0500
+++ b/fig-alt-update-list-2.svg	Fri Nov 21 11:23:48 2014 +0100
@@ -31,7 +31,7 @@
      showgrid="true"
      units="cm"
      inkscape:zoom="1.6402035"
-     inkscape:cx="538.5595"
+     inkscape:cx="539.77886"
      inkscape:cy="156.22344"
      inkscape:window-x="0"
      inkscape:window-y="27"
@@ -180,7 +180,7 @@
        x="169.642">
       <tspan
          style="font-style:italic"
-         id="tspan3265">bef</tspan>
+         id="tspan3265">spre</tspan>
     </text>
   </g>
   <g
@@ -207,7 +207,7 @@
        x="581.98199">
       <tspan
          style="font-style:italic"
-         id="tspan3269">aft</tspan>
+         id="tspan3269">opost</tspan>
     </text>
   </g>
   <g
@@ -595,6 +595,15 @@
          sodipodi:cy="-207"
          sodipodi:rx="30.5947"
          sodipodi:ry="18" />
+      <text
+         style="font-size:13.99999905px;text-anchor:middle;font-family:'Times,serif'"
+         id="text72-1"
+         y="-205.341"
+         x="309.29651">
+        <tspan
+           style="font-style:italic"
+           id="tspan3265-6">opre</tspan>
+      </text>
     </g>
     <g
        transform="matrix(0.98784308,0,0,1,-44.620034,261.03926)"
@@ -614,6 +623,16 @@
          sodipodi:cy="-176"
          sodipodi:rx="28.695299"
          sodipodi:ry="18" />
+      <text
+         transform="matrix(0.77952179,0,0,0.83111984,435.18333,-180.52889)"
+         style="font-size:16.84473991px;text-anchor:middle;stroke-width:0.83111984;stroke-miterlimit:4;stroke-dasharray:2.49335947, 2.49335947;stroke-dashoffset:0;filter:url(#filter4307);font-family:'Times,serif'"
+         id="text72-1-3"
+         y="7.4453754"
+         x="14.975238">
+        <tspan
+           style="font-style:italic"
+           id="tspan3265-6-5">spost</tspan>
+      </text>
     </g>
     <path
        d="m 340.04249,85.03926 28.34646,0"
--- a/ldpatch.html	Fri Nov 21 01:31:20 2014 -0500
+++ b/ldpatch.html	Fri Nov 21 11:23:48 2014 +0100
@@ -413,13 +413,13 @@
     <section class='normative' id='semantics'>
       <h1>LD Patch Semantics</h1>
       <p>
-An LD Patch document is applied to a Linked Data resource identified by an IRI (the <dfn>target IRI</dfn>) and represented by an RDF graph (the <dfn>target graph</dfn>). It is made of a prologue and a list of statements, where the order <strong>must be respected</strong>. The prologue declares a number of <a>prefixes</a> used to abbreviate IRIs. Then, each statement either binds a variable to a matching node from the <a>target graph</a>, or specifies a modification on the <a>target graph</a>.
+An LD Patch document is applied to a Linked Data resource identified by an IRI (the <dfn>target IRI</dfn>) and represented by an RDF graph (the <dfn>target graph</dfn>). It is made of a prologue and a list of statements, where the order <strong>must be respected</strong>. The prologue declares a number of <a href="#grammar-production-prefixID">prefixes</a> used to abbreviate IRIs as <a href="#grammar-production-PrefixedName">PrefixedName</a>s. Then, each statement either binds a variable to a matching node from the <a>target graph</a>, or specifies a modification on the <a>target graph</a>.
       </p>
 
 
 
 
-      <section id="node-matching-semantics">
+      <section id="nodes-and-triples-semantics">
         <h2><dfn>Nodes and triples Semantics</dfn></h2>
         <p>
 LD Patch borrows much of its syntax and semantics from <a href="http://www.w3.org/TR/turtle/">Turtle</a> [[Turtle]] for describing nodes and triples. Especially, whenever production rules <a class="internalDFN" href="#grammar-production-triples">triples</a> or <a class="internalDFN" href="#grammar-production-collection">collection</a> are used, Turtle semantics must be applied to parse them as a set of triples that we call an <dfn>argument graph</dfn>.
@@ -429,7 +429,7 @@
         </p>
         <ul>
           <li>
-            The base IRI used to resolve relative IRIs MUST be <a>target IRI</a>.
+            The base IRI used to resolve relative IRIs MUST be the <a>target IRI</a>.
           </li>
           <li>
             LD Patch allows <a href="#grammar-production-Var">Var</a>iables in subject or object positions. A variable MUST be <a title="bind">bound</a> prior to its first use in the LD Patch Document, and it must be replaced by the last node to which it has been bound (in case it appears in several <a>Bind</a> statements).
@@ -546,7 +546,7 @@
         <section id="cut-statement">
           <h2><dfn>Cut</dfn></h2>
           <p>
-              The <a>Cut</a> operation is used to remove one or more triples from the <a>target graph</a> connected to a specific RDF node (an IRI or a blank node, potentially through a bound variable). The triples being removed correspond to the <a href="http://en.wikipedia.org/wiki/Connectivity_%28graph_theory%29">connected graph</a> accessible from the given RDF node through blank nodes, and following the direction of the predicates.
+              The <a>Cut</a> operation is used to remove one or more triples from the <a>target graph</a> connected to a specific blank node <var>b</var>. More precisely, it removes from the <a>target graph</a> all the outgoing arcs of <var>b</var>, and for each object <var>o</var> of those triples being a blank node, the <a>Cut</a> operation is recursively applied to <var>o</var>.
           <pre class='example'>
 Cut ?workLocation .
           </pre>
@@ -556,48 +556,94 @@
         <section id="update-list-statement">
           <h2><dfn>UpdateList</dfn></h2>
           <p>
-              The <a>UpdateList</a> operation is used to update the members of an <a href="http://www.w3.org/TR/rdf-schema/#ch_collectionvocab">RDF collection</a>. The first two arguments are the <a class="internalDFN" href="#grammar-production-subject">subject</a> (up to <a>var</a>iable binding) and <a class="internalDFN" href="#grammar-production-predicate">predicate</a> of the RDF triple that unambiguously identify the target collection to be updated: it is in the object position of this triple. The third argument specifies which <a>Slice</a> will be replaced by a new collection: this is the fourth argument of the statement.
-          </p>
-
-          <p>
-              A <dfn>Slice</dfn> is described by two positive integers separated by "<code>..</code>". The second integer can be omitted, in that case it denotes the end of the list. If both integers are omitted (i.e. "<code>..</code>" alone), this denotes by convention the empty slice at the end of the list. Indexes start at 0.
+The UpdateList operation is used to update some members of an <a href="http://www.w3.org/TR/rdf-schema/#ch_collectionvocab">RDF collection</a>. This is done by replacing a (possibly empty) sublist of that collection, identified by a <a>Slice specification</a>, by another sublist. 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.
           </p>
 
-          <p>
-              @@ TODO better explanations @@
-              In the example below, <a>UpdateList</a> is used to replace the second and third member of <code>( "foo" "bar" "baz" "qux" )</code> by list <code>( 1 2 3 )</code>.
-          </p>
-          
-          <pre class='example'>
-UpdateList ex:s ex:p 2..4 ( 1 2 3 ) .
-          </pre>
+        <p>
+First, recall that a collection in RDF is either the empty collection <code>rdf:nil</code> or a node (usually blank) having an <code>rdf:first</code> arc pointing to its first element, and an <code>rdf:rest</code> pointing to another collection. For example, the collection <code>( "lorem" "ipsum" "dolor" "sit" "amet" )</code> is modeled as represented in the upper part of <a href="#fig-an-example-rdf-collection"></a> below.
 
-          <p>
-              Here is an intuition of the algorithm being applied:
-          </p>
-          <ul>
-              <li>Step 1: find the last triple sLeft/pLeft/oRight on the left side of slice (corner case: index 0, or empty list => sLeft/pLeft can be s/p)</li>
-              <li>Step 2: find the first node sRight on the right side of the slice</li>
-              <li>Step 3: connect the lists
-                  <ul>
-                      <li>remove the triples from the slice</li>
-                      <li>remove last triple of the new list</li>
-                      <li>remove sLeft/pLeft/oLeft</li>
-                      <li>add sLeft/pLeft/headNewList</li>
-                      <li>add sSlice/pSlice/sRight</li>
-                  </ul>
+          <figure>
+            <img src="fig-alt-update-list.svg" alt="( &quote;lorem&quote; &quote;ipsum&quote; &quote;dolor&quote; &quote;sit&quote; &quote;amet&quote; ) ( &quote;foo&quote; &quote;bar&quote; &quote;baz&quote; )">
+            <figcaption>Two example RDF collections</figcaption>
+          </figure>
+
+A node in a collection failing to have exactly one <code>rdf:first</code> and one <code>rdf:rest</code> outgoing arcs is considered malformed, and the <a>UpdateList</a> operation MUST fail if it encounters such a node.
+        </p>
+
+        <p>
+The <a>UpdateList</a> operation is defined by four components: a <a href="#grammar-production-varOrIRI">variable or IRI</a> <var>s</var>, an <a href="#grammar-production-predicate">predicate</a> <var>p</var>, a <a>slice specification</a> and an argument graph <var>g</var> containing an RDF collection. It MUST fail if the <a>target graph</a> contains no more more than one triple with subject <var>s</var> and object <var>p</var>, or if the object of that triple is not a collection.
+        </p>
+
+        <p>
+The <dfn>slice specification</dfn> is composed of two positive integers <var>imin</var> and <var>imax</var> separated by "<code>..</code>". An omitted value is interpreted as the length of the collection. The first value <var>imin</var> MUST be less than or equal to <var>imax</var>, which MUST be less than or equal to the lenth of the collection. The slice represents the sublist being preceded by <var>imin</var> elements in the collection, and stopping after the <var>imax</var><sup>th</sup> element. For example, in <a href="#fig-an-example-rdf-collection"></a>, the slice <code>2..4</code> is the sublist <code>("dolor" "sit")</code>, the slice <code>3..</code> is the sublist <code>("sit" "amet")</code>, the slice <code>2..2</code> is an empty sublist located between <code>"ipsum"</code> and <code>"dolor"</code>, and the slice <code>..</code> is an empty sublist located at the end of the list.
+        </p>
+
+        <p>
+Below is an algorithm explaining how <a>UpdateList</a> can processed. The result of this algorithm is illustrated in <a href="#fig-updatelist-result"></a>.
+        </p>
+        <ul>
+          <li>
+            Let <var>spre</var> be <var>s</var>, <var>ppre</var> be <var>p</var> and <var>opre</var> the object of the triple (<var>s</var>, <var>p</var>, ?) from the <a>target graph</a>.
+          </li>
+          <li>
+            Repeat <var>imin</var> times:
+            <ul>
+              <li>
+                Set <var>spre</var> to <var>opre</var>, <var>ppre</var> to <code>rdf:rest</code> and <var>opre</var> to the object of the triple (<var>opre</var>, <code>rdf:rest</code>, ?) from the <a>target graph</a>.
               </li>
-          </ul>
+            </ul>
+          </li>
+          <li>
+            Let <var>spost</var> be <var>spre</var>, <var>ppost</var> be <var>ppre</var> and <var>opost</var> be <var>opre</var>.
+          </li>
+          <li>
+            Repeat (<var>imax</var>-<var>imin</var>) times:
+            <ul>
+              <li>
+                Remove from the <a>target graph</a> the arcs (<var>spost</var>, <var>ppost</var>, <var>opost</var>).
+              </li>
+              <li>
+                Let <var>elt</var> be the object of the triple (<var>spost</var>, <code>rdf:first</code>, ?). Remove from the <a>target graph</a> the arc (<var>spost</var>, <code>rdf:first</code>, <var>elt</var>). If <var>elt</var> is a blank node, apply the <a>Cut</a> operation to <var>elt</var>.
+              </li>
+              <li>
+                Set <var>spost</var> to <var>opost</var>, <var>ppost</var> to <code>rdf:rest</code> and <var>opost</var> to the object of the triple (<var>opost</var>, <code>rdf:rest</code>, ?) from the <a>target graph</a>.
+              </li>
+            </ul>
+          </li>
+          <li>
+            Remove from the <a>target graph</a> the arcs (<var>spre</var>, <var>ppre</var>, <var>opre</var>) and (<var>spost</var>, <var>ppost</var>, <var>opost</var>). (NB: in some situations, they may be the same arc, or have already been removed by a previous step)
+          </li>
+          <li>
+            If <var>col</var> is the empty collection
+            <ul>
+              <li>
+                Then
+                <ul>
+                  <li>
+                    Add in the <a>target graph</a> the arc (<var>spre</var>, <var>ppre</var>, <var>opost</var>).
+                  </li>
+                </ul>
+              </li>
+              <li>
+                Else
+                <ul>
+                  <li>
+                    Add all the arcs resulting from the parsing of <var>col</var> to the target graph, let <var>fst</var> be the first node of the corresponding new collection, and <var>lst</var> the last node of that collection (excluding <code>rdf:nil</code>).
+                  </li>
+                  <li>
+                    Add in the <a>target graph</a> the arcs (<var>spre</var>, <var>ppre</var>, <var>fst</var>) and (<var>lst</var>, <var>ppost</var>, <var>opost</var>).
+                  </li>
+                </ul>
+              </li>
+            </ul>
+          </li>
 
-          <p>
-              (TODO do we need a better picture?) Graphically, that's what it looks like:
-          </p>
+          <figure id="fig-updatelist-result">
+            <img src="fig-alt-update-list-2.svg" alt="( &quote;lorem&quote; &quote;ipsum&quote; &quote;dolor&quote; &quote;sit&quote; &quote;amet&quote; ) ( &quote;foo&quote; &quote;bar&quote; &quote;baz&quote; )">
+            <figcaption>The result of UpdateList s p 2..4 ("foo" "bar" "baz")</figcaption>
+          </figure>
 
 
-          <div id="updatelist-algo">
-              <img src="updatelist-algo.svg" />
-          </div>
-
         </section>
       </section>
 
@@ -620,8 +666,8 @@
             <li id="cut-non-bnode">If a <a>Cut</a> operation is called on a variable not bound to a blank node, then a HTTP 422 (Unprocessable Entity) error status code MUST be returned.</li>
             <li id="delete-non-existing-triple">If a <a>Delete</a> attempts to remove a non-existing triple, then a HTTP 422 (Unprocessable Entity) error status code MUST be returned.</li>
             <li id="updatelist-non-list-argument">If the <a class="internalDFN" href="#grammar-production-subject">subject</a> and <a class="internalDFN" href="#grammar-production-predicate">predicate</a> provided to a <a>UpdateList</a> operation fail to match a collection, then a HTTP 422 (Unprocessable Entity) error status code MUST be returned.</li>
-            <li id="wrong-order-for-indexes">If the indexes in a <a>Slice</a> are in the wrong order (e.g. <code>2868..42</code>), then the parsing fails and a 400 (Bad Request) error status code MUST be returned.</li>
-            <li id="wrong-index">If an index in a <a>Slice</a> has no corresponding element in an <code>rdf:List</code>, then a 422 (Unprocessable Entity) error status code MUST be returned.</li>
+            <li id="wrong-order-for-indexes">If the indexes in a <a>slice specification</a> are in the wrong order (e.g. <code>2868..42</code>), then the parsing fails and a 400 (Bad Request) error status code MUST be returned.</li>
+            <li id="wrong-index">If an index in a <a>slice specification</a> is greated than the length of the <code>rdf:List</code>, then a 422 (Unprocessable Entity) error status code MUST be returned.</li>
             <li id="unknown-prefix">If a prefix name (<a class="internalDFN" href="#grammar-production-PNAME_NS">PNAME_NS</a>) is used without being previously declared, then the parsing fails and a 400 (Bad Request) error status code MUST be returned.</li>
             <li id="unknown-variable">If a <a>var</a>iable is used without being previously bound, then the parsing fails and a 400 (Bad Request) error status code MUST be returned.</li>
 
@@ -686,10 +732,10 @@
     <section id="turtle-sparql-comparison">
         <h1>LD Patch compared to Turtle and SPARQL</h1>
         <p>
-            The LD Patch syntax uses a Turtle [[!Turtle]] style syntax for its <a class="internalDFN" href="#grammar-production-triples">triples</a> production. This production differs from the Turtle language in that the <a class="internalDFN" href="#grammar-production-subject">subject</a> and <a class="internalDFN" href="#grammar-production-predicate">predicate</a> production rules allow the use of variables.
+            The LD Patch syntax uses a Turtle [[!Turtle]] style syntax for its <a class="internalDFN" href="#grammar-production-triples">triples</a> production. This production differs from the Turtle language in that the <a class="internalDFN" href="#grammar-production-subject">subject</a> and <a class="internalDFN" href="#grammar-production-object">object</a> production rules allow the use of variables.
         </p>
         <p>
-            LD Patch variables are restricted to the <a class="internalDFN" href="#grammar-production-VAR1">VAR1</a> production rule from SPARQL 1.1 [[!sparql11-query]], only allowing a trailing '<code>?</code>'.
+            LD Patch variables are restricted to the <a class="internalDFN" href="#grammar-production-VAR1">VAR1</a> production rule from SPARQL 1.1 [[!sparql11-query]], only allowing a leading '<code>?</code>'.
         </p>
         <p>
             Finally, the prefix directive is restricted to the <a class="internalDFN" href="#grammar-production-prefixID">prefixID</a> production rule in Turtle [[!Turtle]], only allowing <code>@prefix</code>.