--- a/spec/latest/index.html Sun Aug 07 23:38:45 2011 -0700
+++ b/spec/latest/index.html Mon Aug 08 15:43:47 2011 -0400
@@ -2159,6 +2159,21 @@
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>
+ <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>
</dl>
</section>
@@ -2205,18 +2220,30 @@
<section>
<h4>Node Labeling Algorithm</h4>
-<p>The node labeling algorithm sorts all of the unlabeled nodes in the graph
-and deterministically names them in descending order.</p>
+<p>The node labeling algorithm takes the <tref>list of expanded nodes</tref>
+and sorts the list, deterministically naming all of the unlabeled nodes
+in the graph.</p>
<ol class="algorithm">
- <li>???Create a <tdef>property to unlabeled node mapping</tdef> that relates
- property IRIs to unlabeled node identifiers. Create a key for every
- property that is associated with a value that has an unlabeled node
- identifier.</li>
- <li>???Create a <tdef>unlabeled node references mapping</tdef> that relates
- unlabeled nodes to the subjects that refer to them. Create a key for every
- unlabeled node with mappings to each node that references the unlabeled
- node.???</li>
+ <li>Create a <tdef>forward mapping</tdef> that relates graph
+ nodes to the IRIs of the targets nodes that
+ they reference. For example, if a node <tref>alpha</tref> refers to a
+ node <tref>beta</tref> via a property, the key in the
+ <tref>forward mapping</tref> is the subject IRI of <tref>alpha</tref> and
+ the value is an array containing at least the subject IRI of
+ <tref>beta</tref>.
+ <ol class="algorithm">
+ <li>Add all forward mappings for every node in the graph.</li>
+ </ol></li>
+ <li>Create a <tdef>reverse mapping</tdef> that relates graph nodes
+ to every other node that refers to them in the graph.
+ For example, if a node <tref>alpha</tref> refers to a
+ node <tref>beta</tref> via a property, the key in the
+ <tref>reverse mapping</tref> is the subject IRI for <tref>beta</tref> and
+ the value is an array containing at least the IRI for <tref>alpha</tref>.
+ <ol class="algorithm">
+ <li>Add all reverse mappings for every node in the graph.</li>
+ </ol></li>
<li>Label every unlabeled node according to the
<a href="#label-generation-algorithm">Label Generation Algorithm</a>
in descending order using the
@@ -2230,24 +2257,92 @@
<p>
The shallow comparison algorithm takes two unlabeled nodes,
-<strong>alpha</strong> and <strong>beta</strong>, as input and
+<tref>alpha</tref> and <tref>beta</tref>, as input and
determines which one should come first in a sorted list. The following
algorithm determines the steps that are executed in order to determine the
node that should come first in a list:
</p>
<ol class="algorithm">
- <li>The node with fewer properties is first.</li>
- <li>The node with the lexicographically lesser property is first.</li>
- <li>???Do CompareObjects for each equivalent property.???</li>
- <li>The node with fewer entries in the
- <tref>unlabeled node references mapping</tref> is first.</li>
- <li>???The node with the reference IRI (vs. bnode) is first.???</li>
- <li>???The node with the lexicographically lesser reference IRI
- is first.???</li>
- <li>???The node with the lexicographically lesser reference property
- is first.???</li>
+ <li>Compare the total number of node properties. The node with fewer
+ properties is first.</li>
+ <li>Lexicographically sort the property IRIs for each node and compare
+ the sorted lists. If an IRI is found to be lexicographically smaller, the
+ node containing that IRI is first.</li>
+ <li>Compare the property values against one another:
+ <ol class="algorithm">
+ <li>Create an <tdef>alpha list</tdef> by adding all values associated
+ with the <tref>alpha</tref> property that is not an unlabeled node.
+ Track the number of unlabeled nodes not added to the list using an
+ <tdef>alpha unlabeled counter</tdef>.</li>
+ <li>Create a <tdef>beta list</tdef> by adding all values associated
+ with the <tref>beta</tref> property that is not an unlabeled node.
+ Track the number of unlabeled nodes not added to the list using an
+ <tdef>beta unlabeled counter</tdef>.
+ <li>Compare the length of <tref>alpha list</tref> and
+ <tref>beta list</tref>. The node associated with the list containing the
+ lesser number of items is first.</li>
+ <li>Compare the <tref>alpha unlabeled counter</tref> to the
+ <tref>beta unlabeled counter</tref>, the node associated with the lesser
+ value is first.</li>
+ <li>Sort <tref>alpha list</tref> and <tref>beta list</tref> using the
+ <a href="#object-comparison-algorithm">Object Comparison Algorithm</a>
+ as the sorting comparator.
+ For each offset into the <tref>alpha list</tref>, compare the item
+ at the offset against the item at the same offset in the
+ <tref>beta list</tref> using the
+ <a href="#object-comparison-algorithm">Object Comparison Algorithm</a>.
+ The node associated with the lesser item is first.
+ </ol></li>
+ <li>Process the <tref>reverse mapping</tref> to determine order:
+ <ol class="algorithm">
+ <li>The node with fewer entries in the <tref>reverse mapping</tref>
+ is first.</li>
+ <li>Sort the <tref>reverse mapping</tref> entry for <tref>alpha</tref>
+ into a <tdef>list of sorted alpha mappings</tdef>. Sort the
+ <tref>reverse mapping</tref> entry for <tref>beta</tref>
+ into a <tdef>list of sorted beta mappings</tdef>.
+ <li>The node associated with the list of sorted mappings
+ with the least number of unlabeled nodes is first.</li>
+ <li>For each offset into the <tref>list of sorted alpha mappings</tref>,
+ compare the IRI at the offset against the IRI at the same offset in the
+ <tref>list of sorted beta mappings</tref>.
+ The node associated with the lexicographically lesser IRI is first.</li>
+ </ol></li>
+ <li>Otherwise, the nodes are equal.</li>
+</section>
+
+<section>
+<h4>Object Comparison Algorithm</h4>
+
+<p>
+The object comparison algorithm is designed to compare two graph node
+property values, <tref>alpha</tref> and <tref>beta</tref>, against the other.
+The algorithm is useful when sorting two lists of graph node properties.
+</p>
+
+<ol class="algorithm">
+ <li>If one of the values is a string and the other is not, the value that is
+ a string is first.</li>
+ <li>If both values are strings, the lexicographically lesser string is
+ first.</li>
+ <li>If one of the values is a literal and the other is not, the value that is
+ a literal is first.</li>
+ <li>If both values are literals
+ <ol class="algorithm">
+ <li>The lexicographically lesser string associated with
+ <code>@literal</code> is first.</li>
+ <li>The lexicographically lesser string associated with
+ <code>@datatype</code> is first.</li>
+ <li>The lexicographically lesser string associated with
+ <code>@language</code> is first.</li>
+ </ol></li>
+ <li>If both values are expanded IRIs, the
+ lexicographically lesser string associated with <code>@iri</code>
+ is first.</li>
+ <li>Otherwise, the two values are equivalent.</li>
</ol>
+
</section>
<section>