--- a/spec/latest/index.html Wed Aug 10 23:05:49 2011 -0400
+++ b/spec/latest/index.html Thu Aug 11 17:23:47 2011 -0400
@@ -2059,13 +2059,6 @@
A map that tracks if a subject has been embedded in the output of the
<a href="#framing-algorithm">Framing Algorithm</a>.
</dd>
- <dt><tdef>serialization identifier</tdef></dt>
- <dd>
- An identifier that is created to aid in the normalization process in the
- <a href="#deep-comparison-algorithm">Deep Comparison Algorithm</a>. The
- value typically takes the form of <code>s<NUMBER></code> or
- <code>c<NUMBER></code>.
- </dd>
</dl>
</section>
@@ -2239,29 +2232,47 @@
embedded objects and having all keys and values expanded according to the
steps in the <a href="#expansion-algorithm">Expansion Algorithm</a>.
</dd>
- <dt><tdef>naming base string</tdef></dt>
- <dd>
- An unlabeled node naming prefix that is not used by any other node
- in the <tref>JSON-LD input</tref> and does not start with the characters
- <code>c14n</code>. The prefix is used to temporarily name nodes during
- the normalization algorithm in a way that doesn't collide with the
- names that already exist as well as the names that will be generated by the
- normalization algorithm.
- </dd>
<dt><tdef>alpha</tdef> and <tdef>beta</tdef> values</dt>
<dd>
The words <tref>alpha</tref> and <tref>beta</tref> refer to the first and
second nodes or values being examined in an algorithm. The names are
merely used to refer to each input value to a comparison algorithm.
</dd>
- <dt><tdef>naming base string</tdef></dt>
+ <dt><tdef>labeling prefix</tdef></dt>
<dd>
- An unlabeled node naming prefix that is not used by any other node
- in the <tref>JSON-LD input</tref> and does not start with the characters
- <code>c14n</code>. The prefix is used to temporarily name nodes during
+ A random base string that starts with the characters <code>_:</code>, is
+ not used by any other node's subject IRI in the <tref>JSON-LD input</tref>,
+ and does not start with the characters
+ <code>_:c14n</code>. The prefix is used to temporarily name nodes during
the normalization algorithm in a way that doesn't collide with the
names that already exist as well as the names that will be generated by the
- normalization algorithm.
+ normalization algorithm. To prevent further collisions, an incrementing
+ <tdef>labeling counter</tdef> is appended to the base string. For
+ example, <code>_:j8r3k</code> is a proper <tref>labeling prefix</tref>.
+ </dd>
+ <dt><tdef>deterministic labeling prefix</tdef></dt>
+ <dd>
+ A base string with the value <code>_:c14n</code>. The prefix is used to
+ deterministically name nodes during the normalization algorithm. The
+ <tdef>deterministic labeling counter</tdef> is appended to the base string
+ to ensure that there are no collisions.
+ </dd>
+ <dt><tdef>renaming counter</tdef></dt>
+ <dd>
+ A counter that is used during the
+ <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>. The
+ counter typically starts at one (1) and counts up for every node that is
+ relabeled. There will be two such renaming counters in an implementation
+ of the normalization algorithm. The first is the
+ <tref>labeling counter</tref> and the second is the
+ <tref>deterministic labeling counter</tref>.
+ </dd>
+ <dt><tdef>serialization identifier</tdef></dt>
+ <dd>
+ An identifier that is created to aid in the normalization process in the
+ <a href="#deep-comparison-algorithm">Deep Comparison Algorithm</a>. The
+ value typically takes the form of <code>s<NUMBER></code> or
+ <code>c<NUMBER></code>.
</dd>
</dl>
</section>
@@ -2280,6 +2291,9 @@
<li>Expand the <tref>JSON-LD input</tref> according to the steps in
the <a href="#expansion-algorithm">Expansion Algorithm</a> and store the
result as the <strong>expanded input</strong>.</li>
+<li>Initialize the <tref>labeling prefix</tref> to a value that doesn't
+collide with any other subject IRI prefix in the graph. Initialize the
+<tref>labeling counter</tref> to 1.
<li>Create an empty <tdef>map of expanded nodes</tdef> and recursively
process every <tdef>expanded node</tdef> in the <strong>expanded input</strong>
in depth-first order:
@@ -2287,8 +2301,8 @@
<li>If the <tref>expanded node</tref> is an unlabeled node, add a
new key-value pair
where the key is <code>@subject</code> and the value is the
- concatenation of <code>_:</code> with the <tref>naming base string</tref>
- and a unique identifier, such as an incrementing counter value.</li>
+ concatenation of the <tref>labeling prefix</tref>
+ and the string value of the <tref>labeling counter</tref>.</li>
<li>Add the <tref>expanded node</tref> to the
<tref>map of expanded nodes</tref>:
<ol class="algorithm">
@@ -2331,10 +2345,10 @@
<li>For every entry in the <tref>map of expanded nodes</tref> that has a
subject IRI that begins with <code>_:c14n</code>, relabel the subject IRI
using the steps in the
-<a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>. The
-<tref>new label</tref> MUST be created by concatenating <code>_:</code> with
-the <tref>naming base string</tref> and a unique identifier, such as an
-incrementing counter value.
+<a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a> with the
+following parameters; <tref>naming base string</tref> should be the value
+of <tref>labeling prefix</tref> and <tref>renaming counter</tref> should be the
+value of <tref>labeling counter</tref>.
<li>Label all of the nodes that contain a <code>@subject</code> key associated
with a value starting with <code>_:</code> according to the steps in the
<a href="#deterministic-labeling-algorithm">Deterministic Labeling Algorithm</a>.
@@ -2345,12 +2359,18 @@
<section>
<h4>Node Relabeling Algorithm</h4>
-<p>The node relabeling algorithm takes a node containing an <tdef>old label</tdef>
-that is the subject IRI, the <tref>outgoing map</tref>,
-the <tref>incoming map</tref>, and a <tdef>new label</tdef> that is an IRI.
+<p>The node relabeling algorithm takes a node containing an
+<tdef>old label</tdef> that is the subject IRI, a
+<tdef>naming base string</tdef>, a <tref>renaming counter</tref>, and the
+<tref>incoming map</tref> and <tref>outgoing map</tref>.
</p>
<ol class="algorithm">
+ <li>Generate the <tdef>new label</tdef> by concatenating the
+ <tref>naming base string</tref> with the string value of the
+ <tref>renaming counter</tref>. Add <code>1</code>
+ to the <tref>renaming counter</tref>, ensuring to preserve the latest
+ value of the counter across multiple calls to this algorithm.
<li>For each node that is associated with the <tref>old label</tref> in the
<tref>incoming map</tref>, update all properties that reference the
<tref>old label</tref> with the <tref>new label</tref>.</li>
@@ -2369,7 +2389,8 @@
the graph.
<ol class="algorithm">
- <li>Initialize the <tdef>normalized node counter</tdef> to <code>0</code> and
+ <li>Initialize the <tref>deterministic labeling counter</tref> to
+ <code>1</code> and
the <tdef>sorted list of expanded nodes</tdef> to an empty array.</li>
<li>Place a reference to each of the nodes in the
<tref>map of expanded nodes</tref> into a
@@ -2404,11 +2425,12 @@
empty array.</li>
<li>Relabel the first node in the
resorted <tref>list of expanded nodes</tref> according to the
- <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>.
- The <tref>new label</tref> MUST be created by concatenating
- <code>_:c14n</code> with the value from the
- <tref>normalized node counter</tref>.
- Increase the <tref>normalized node counter</tref> by <code>1</code>.
+ <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>
+ with the following parameters;
+ <tref>naming base string</tref> is the value of the
+ <tref>deterministic labeling prefix</tref> and the
+ <tref>renaming counter</tref> is the
+ <tref>deterministic labeling counter</tref>.
Place the <tref>old label</tref>
in the <tref>list of all old labels</tref>.
</li>
@@ -2424,11 +2446,12 @@
<li>For each <tref>old label</tref> in the
<tref>list of old labels</tref> get the node from the
<tref>map of expanded nodes</tref> and relabel it according to the
- <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>.
- The <tref>new label</tref> MUST be created by concatenating
- <code>_:c14n</code> with the value from the
- <tref>normalized node counter</tref>.
- Increase the <tref>normalized node counter</tref> by <code>1</code>.
+ <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>
+ with the following parameters;
+ <tref>naming base string</tref> is the value of the
+ <tref>deterministic labeling prefix</tref> and the
+ <tref>renaming counter</tref> is the
+ <tref>deterministic labeling counter</tref>.
Place the <tref>old label</tref>
in the <tref>list of all old labels</tref>.
</li></ol></li>
@@ -2445,10 +2468,11 @@
<tref>list of old labels</tref> get the node from the
<tref>map of expanded nodes</tref> and relabel it according to the
<a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>
- The <tref>new label</tref> MUST be created by concatenating
- <code>_:c14n</code> with the value from the
- <tref>normalized node counter</tref>.
- Increase the <tref>normalized node counter</tref> by <code>1</code>.
+ with the following parameters;
+ <tref>naming base string</tref> is the value of the
+ <tref>deterministic labeling prefix</tref> and the
+ <tref>renaming counter</tref> is the
+ <tref>deterministic labeling counter</tref>.
Place the <tref>old label</tref>
in the <tref>list of all old labels</tref>.
</li></ol></li>