--- a/spec/latest/index.html Thu Aug 11 21:15:42 2011 -0400
+++ b/spec/latest/index.html Fri Aug 12 17:15:38 2011 -0400
@@ -2267,7 +2267,7 @@
<tref>labeling counter</tref> and the second is the
<tref>deterministic labeling counter</tref>.
</dd>
- <dt><tdef>serialization identifier</tdef></dt>
+ <dt><tdef>serialization label</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
@@ -2402,7 +2402,7 @@
key is an unlabeled node identifier and the value is a map. The value
map contains a <tref>serialization map</tref> with keys that are
unlabeled node identifiers that map to values that are
- <tref>serialization identifier</tref>s.</li>
+ <tref>serialization label</tref>s.</li>
<li>Create a <tdef>map of outgoing serializations</tdef> where the key is
an unlabeled node identifier and the value is a serialization string.
</li>
@@ -2410,7 +2410,7 @@
is an unlabeled node identifier and the value is a map. The value
map contains a <tref>serialization map</tref> with keys that are
unlabeled node identifiers that map to values that are
- <tref>serialization identifier</tref>s.</li>
+ <tref>serialization label</tref>s.</li>
<li>Create a <tdef>map of incoming serializations</tdef> where the key is
an unlabeled node identifier and the value is a serialization string.
</li>
@@ -2616,12 +2616,12 @@
the result.
</li>
<li>Initialize the <tdef>mapping counter</tdef> to <code>1</code>.
- Initialize the <tdef>list of unserialized identifiers</tdef> to an
+ Initialize the <tdef>list of unserialized labels</tdef> to an
empty array. Initialize the
- <tdef>processed identifiers map</tdef>,
+ <tdef>processed labels map</tdef>,
the <tdef>incoming serialization map</tdef>,
the <tdef>outgoing serialization map</tdef>, and
- the <tdef>serialized identifier map</tdef> to empty maps.
+ the <tdef>serialized labels map</tdef> to empty maps.
<li>Compare incoming and outgoing edges for each node, updating the
serialization maps as each node is processed:
<ol class="algorithm">
@@ -2630,19 +2630,19 @@
following the steps in the
<a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
Provide <tref>alpha</tref>,
- the <tref>processed identifiers map</tref>,
+ the <tref>processed labels map</tref>,
the <tref>outgoing serialization map</tref>,
- the <tref>serialized identifier map</tref> and the
- <tref>list of unserialized identifiers</tref> to the algorithm as inputs.
+ the <tref>serialized labels map</tref> and the
+ <tref>list of unserialized labels</tref> to the algorithm as inputs.
<li>If the subject IRI for <tref>beta</tref> does not exist in the
<tref>outgoing serialization map</tref>, generate the serialization by
following the steps in the
<a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
Provide <tref>beta</tref>,
- the <tref>processed identifiers map</tref>,
+ the <tref>processed labels map</tref>,
the <tref>outgoing serialization map</tref>,
- the <tref>serialized identifier map</tref> and the
- <tref>list of unserialized identifiers</tref> to the algorithm as inputs.
+ the <tref>serialized labels map</tref> and the
+ <tref>list of unserialized labels</tref> to the algorithm as inputs.
<li>If the lexicographical value of the entry for <tref>alpha</tref> in
the <tref>outgoing serialization map</tref> is greater than the entry
for <tref>beta</tref> in the <tref>outgoing serialization map</tref>,
@@ -2653,19 +2653,19 @@
following the steps in the
<a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
Provide <tref>alpha</tref>,
- the <tref>processed identifiers map</tref>,
+ the <tref>processed labels map</tref>,
the <tref>incoming serialization map</tref>,
- the <tref>serialized identifier map</tref> and the
- <tref>list of unserialized identifiers</tref> to the algorithm as inputs.
+ the <tref>serialized labels map</tref> and the
+ <tref>list of unserialized labels</tref> to the algorithm as inputs.
<li>If the subject IRI for <tref>beta</tref> does not exist in the
<tref>incoming serialization map</tref>, generate the serialization by
following the steps in the
<a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
Provide <tref>beta</tref>,
- the <tref>processed identifiers map</tref>,
+ the <tref>processed labels map</tref>,
the <tref>incoming serialization map</tref>,
- the <tref>serialized identifier map</tref> and the
- <tref>list of unserialized identifiers</tref> to the algorithm as inputs.
+ the <tref>serialized labels map</tref> and the
+ <tref>list of unserialized labels</tref> to the algorithm as inputs.
<li>If the lexicographical value of the entry for <tref>alpha</tref> in
the <tref>incoming serialization map</tref> is greater than the entry
for <tref>beta</tref> in the <tref>incoming serialization map</tref>,
@@ -2680,47 +2680,40 @@
<p>
The node serialization algorithm takes a node,
-a <tref>processed identifiers map</tref>, a
-<tdef>serialization map</tdef>, a <tref>serialized identifier map</tref>,
-and a <tref>list of unserialized identifiers</tref> as inputs and generates
+a <tref>processed labels map</tref>, a
+<tdef>serialization map</tdef>, a <tref>serialized labels map</tref>,
+and a <tref>list of unserialized labels</tref> as inputs and generates
deterministic serializations for all unlabeled nodes in the graph. The
node's subject IRI will be called the <tdef>label</tdef> in this algorithm.
</p>
<ol class="algorithm">
<li>If the <tref>label</tref> exists in the
- <tref>processed identifiers map</tref>, terminate the algorithm as the
- <tref>serialization identifier</tref> has already been created</li>
+ <tref>processed labels map</tref>, terminate the algorithm as the
+ <tref>serialization label</tref> has already been created</li>
<li>Set the value associated with the <tref>label</tref> in the
- <tref>processed identifiers map</tref> to <code>true</code>.
+ <tref>processed labels map</tref> to <code>true</code>.
<li>Generate the next <tdef>serialization label</tdef> for the
- <tref>label</tref>:
- <ol class="algorithm">
- <li>If the <tref>label</tref> starts with the string <code>_:c14n</code>,
- the <tref>serialization label</tref> is the letter <code>c</code>
- followed by the number that follows <code>_:c14n</code> in the
- <tref>label</tref>.</li>
- <li>Otherwise, the <tref>serialization label</tref> is the
- letter <code>s</code> followed by the string value of
- <tref>mapping count</tref>. Increment the <tref>mapping count</tref> by
- <code>1</code>.</li>
- </ol>
+ <tref>label</tref> following the
+ <a href="#serialization-label-generation-algorithm">Serialization Label Generation Algorithm</a>
+ passing the <tref>label</tref> and the <tref>mapping count</tref> as
+ parameters to the algorithm.</li>
<li>For every property in the node that references a target node with a
subject IRI that starts with <code>_:</code>
(the <tdef>target node label</tdef>):
<ol class="algorithm">
<li>Look up the <tref>target node label</tref> in the
- <tref>processed identifiers map</tref> and if a mapping exists,
- update the <tref>serialized identifier map</tref> where the key is
+ <tref>processed labels map</tref> and if a mapping exists,
+ update the <tref>serialized labels map</tref> where the key is
the value in the <tref>serialization map</tref> and the value is the
<tref>target node label</tref>.</li>
<li>Otherwise, add the <tref>target node label</tref> to the
- <tref>list of unserialized identifiers</tref>.
+ <tref>list of unserialized labels</tref>.
</ol>
</li>
<li>Set the <tdef>maximum serialization combinations</tdef> to
<code>1</code> or the length of the
- <tref>list of unserialized identifiers</tref>, whichever is greater.</li>
+ <tref>list of unserialized labels</tref>, whichever is greater.</li>
<li>While the <tref>maximum serialization combinations</tref> is greater than
<code>0</code>, perform the
<a href="#combinatorial-serialization-algorithm">Combinatorial Serialization Algorithm</a>
@@ -2731,22 +2724,91 @@
</section>
<section>
+<h4>Serialization Label Generation Algorithm</h4>
+
+<p>
+The algorithm generates a <tref>serialization label</tref> given a
+<tref>label</tref> and a <tref>mapping count</tref>.
+</p>
+
+<li>
+ <ol class="algorithm">
+ <li>If the <tref>label</tref> starts with the string <code>_:c14n</code>,
+ the <tref>serialization label</tref> is the letter <code>c</code>
+ followed by the number that follows <code>_:c14n</code> in the
+ <tref>label</tref>.</li>
+ <li>Otherwise, the <tref>serialization label</tref> is the
+ letter <code>s</code> followed by the string value of
+ <tref>mapping count</tref>. Increment the <tref>mapping count</tref> by
+ <code>1</code> ensuring that the value persists across multiple
+ invocations of this algorithm.</li>
+ </ol>
+</li>
+</section>
+
+<section>
<h4>Combinatorial Serialization Algorithm</h4>
<p>
-SerializeCombos(top, mapping, mapped, notMapped, dir):
+SerializeCombos() takes a <tref>label</tref>,
+a <tref>serialization map</tref>, a <tref>serialization label</tref>, a
+<tref>processed labels map</tref>, a <tref>serialization map</tref>,
+a <tref>serialized labels map</tref>, and a
+<tref>list of unserialized labels</tref> as inputs and generates
+deterministic serializations for all possible combinations of graphs.
</p>
<ol class="algorithm">
- <li>If notMapped is non-empty, copy mapped and assign the next serialization name to its first bnode, remove it from the list, and update mapped.
+ <li>If the <tref>list of unserialized labels</tref> is not empty:
<ol class="algorithm">
- <li>For max(1, notMapped.length) recurse into SerializeCombos with the original mapping for the first call and a copy of the mapping for each subsequent call. Rotate notMapped on each iteration.</li>
- </ol>
- </li>
- <li>If notMapped is empty, save an entry mapping from the bnode's serialization name to the reverse mapping (mapped) and its sorted keys then do SerializeMapping.
+ <li>Copy the <tref>serialization map</tref> to the
+ <tdef>serialization map copy</tdef>.</li>
+ <li>Remove the first <tref>unserialized label</tref> from the
+ <tref>list of unserialized labels</tref> and create a new
+ <tdef>new serialization label</tdef> according to the
+ <a href="#serialization-label-generation-algorithm">Serialization Label Generation Algorithm</a>
+ passing the <tref>unserialized label</tref> and the
+ <tref>mapping counter</tref> as parameters.
+ <li>Create a new key-value mapping in the
+ <tref>serialization map copy</tref>
+ where the key is the <tref>new serialization label</tref> and the value
+ is the <tref>unserialized label</tref>.
+<li>Set the <tdef>maximum serialization rotations</tdef> to
+ <code>1</code> or the length of the
+ <tref>list of unserialized labels</tref>, whichever is greater.</li>
+<li>While the <tref>maximum serialization rotations</tref> is greater than
+ <code>0</code>:
+ <ol class="algorithm">
+ <li>If this is the first iteration in the loop, perform the
+ <a href="#combinatorial-serialization-algorithm">Combinatorial Serialization Algorithm</a>
+ passing in the <tref>label</tref>, the <tref>serialization map copy</tref>,
+ the <tref>serialization label</tref>, the
+ <tref>processed labels map</tref>,
+ <tref>serialized labels map</tref>, and the
+ <tref>list of unserialized labels</tref>.</li>
+ <li>If this is not the first iteration in the loop, perform the
+ <a href="#combinatorial-serialization-algorithm">Combinatorial Serialization Algorithm</a>
+ passing in the <tref>label</tref>, the <tref>serialization map copy</tref>,
+ the <tref>serialization label</tref>, and temporary copies of the
+ <tref>processed labels map</tref>,
+ <tref>serialized labels map</tref>, and the
+ <tref>list of unserialized labels</tref>.</li>
+ <li>Decrement the <tref>maximum serialization rotations</tref> by
+ <code>1</code> for each iteration.
+ </ol></li>
+ <li>If the <tref>list of unserialized labels</tref> is empty:
<ol class="algorithm">
- <li>If the serialization is lexicographically less than the current serialization or the current serialization is null, then iterate over the sorted keys, get the reverse-mapped adjacent bnode and recursively call SerializeNode on each iteration.</li>
- <li>Do SerializeMapping then if the serialization is lexicographically less than the current serialization or the current serialization is null, then set it as the least serialization for the bnode in the given edge direction ('property' or 'reference').</li>
+ <li>???Save an entry mapping from the bnode's
+serialization name to the reverse mapping (mapped) and its sorted keys then do SerializeMapping:
+ <ol class="algorithm">
+ <li>???If the serialization is lexicographically less than the current
+serialization or the current serialization is null, then iterate over the
+sorted keys, get the reverse-mapped adjacent bnode and recursively call
+SerializeNode on each iteration.</li>
+ <li>???Do SerializeMapping then if the serialization is lexicographically
+less than the current serialization or the current serialization is null, then
+set it as the least serialization for the bnode in the given edge direction
+('property' or 'reference').</li>
</ol>
</li>
</ol>
@@ -2774,23 +2836,6 @@
</section>
-<section>
-<h4>Label Generation Algorithm</h4>
-
-<p>
-NameNode(bnode):
-</p>
-
-<ol class="algorithm">
- <li>Remove the first blank node from the list of sorted blank nodes.</li>
- <li>Give it the next canonical name.</li>
- <li>Give canonical names to each blank node key in its property serialization mapping in lexicographical order.</li>
- <li>Give canonical names to each blank node key in its reference serialization mapping in lexicographical order.</li>
- <li>Set all serializations containing newly-named blank nodes to null.</li>
-</ol>
-
-</section>
-
</section>
<section>