--- a/spec/latest/json-ld-api/index.html Tue Jan 10 10:33:10 2012 -0800
+++ b/spec/latest/json-ld-api/index.html Tue Jan 10 11:53:46 2012 -0800
@@ -19,10 +19,11 @@
berjon.biblio["MICRODATA"] = "Ian Hickson; et al. <a href=\"http://www.w3.org/TR/microdata/\"><cite>Microdata</cite></a> 04 March 2010. W3C Working Draft. URL: <a href=\"http://www.w3.org/TR/microdata/\">http://www.w3.org/TR/microdata/</a> ";
berjon.biblio["HTML-RDFA"] = "Manu Sporny; et al. <a href=\"http://www.w3.org/TR/rdfa-in-html/\"><cite>HTML+RDFa</cite></a> 04 March 2010. W3C Working Draft. URL: <a href=\"http://www.w3.org/TR/rdfa-in-html/\">http://www.w3.org/TR/rdfa-in-html/</a> ";
berjon.biblio["BCP47"] = "A. Phillips, M. Davis. <a href=\"http://tools.ietf.org/rfc/bcp/bcp47.txt\"><cite>Tags for Identifying Languages</cite></a> September 2009. IETF Best Current Practice. URL: <a href=\"http://tools.ietf.org/rfc/bcp/bcp47.txt\">http://tools.ietf.org/rfc/bcp/bcp47.txt</a>";
- berjon.biblio["JSON-LD"] = "Manu Sporny, Gregg Kellogg, et al. <a href=\"http://json-ld.org/spec/latest/json-ld-syntax/\"><cite>The JSON-LD Syntax</cite></a> Latest. W3C Editor's Draft. URL: <a href=\"http://json-ld.org/spec/latest/json-ld-syntax/\">http://json-ld.org/spec/latest/json-ld-syntax/</a>";
+ berjon.biblio["JSON-LD"] = "Manu Sporny, Gregg Kellogg. <a href=\"http://json-ld.org/spec/latest/json-ld-syntax/\"><cite>The JSON-LD Syntax</cite></a> Latest. W3C Editor's Draft. URL: <a href=\"http://json-ld.org/spec/latest/json-ld-syntax/\">http://json-ld.org/spec/latest/json-ld-syntax/</a>";
berjon.biblio["RDF-API"] = "Manu Sporny, Benjamin Adrian, Nathan Rixham; et al. <a href=\"http://www.w3.org/2010/02/rdfa/sources/rdf-api/\"><cite>RDF API</cite></a> Latest. W3C Editor's Draft. URL: <a href=\"http://www.w3.org/2010/02/rdfa/sources/rdf-api/\">http://www.w3.org/2010/02/rdfa/sources/rdf-api/</a>";
berjon.biblio["RDF-INTERFACES"] = "Nathan Rixham, Manu Sporny, Benjamin Adrian; et al. <a href=\"http://www.w3.org/2010/02/rdfa/sources/rdf-interfaces/\"><cite>RDF Interfaces</cite></a> Latest. W3C Editor's Draft. URL: <a href=\"http://www.w3.org/2010/02/rdfa/sources/rdf-interfaces/\">http://www.w3.org/2010/02/rdfa/sources/rdf-interfaces/</a>";
berjon.biblio["JSON-POINTER"] = "P. Bryan, Ed. <cite><a href=\"http://www.ietf.org/id/draft-pbryan-zyp-json-pointer-01.txt\">JSON Pointer</a></cite> Latest. IETF Draft. URL: <a href=\"http://www.ietf.org/id/draft-pbryan-zyp-json-pointer-01.txt\">http://www.ietf.org/id/draft-pbryan-zyp-json-pointer-01.txt</a>";
+ berjon.biblio["RDF-NORMALIZATION"] = "Manu Sporny, Dave Longley. <a href=\"http://json-ld.org/spec/latest/rdf-graph-normalization/\"><cite>RDF Graph Normalization</cite></a> Latest. W3C Editor's Draft. URL: <a href=\"http://json-ld.org/spec/latest/rdf-graph-normalization/\">http://json-ld.org/spec/latest/rdf-graph-normalization/</a>";
// process the document before anything else is done
var refs = document.querySelectorAll('adef') ;
@@ -562,12 +563,14 @@
</dd>
- <dt>object normalize()</dt>
+ <dt>DOMString normalize()</dt>
<dd><a href="#normalization">Normalizes</a> the given <code>input</code>
according to the steps in the
<a href="#normalization-algorithm">Normalization Algorithm</a>. The
<code>input</code> MUST be copied, normalized and returned if there are
no errors. If the compaction fails, <code>null</code> MUST be returned.
+ The output is the serialized representation returned from the
+ <a href="#normalization-algorithm">Normalization Algorithm</a>.
<dl class="parameters">
<dt>object input</dt>
<dd>The JSON-LD object to perform normalization upon.</dd>
@@ -587,7 +590,7 @@
</dd>
- <dt>object triples()</dt>
+ <dt>void triples()</dt>
<dd>Processes the <code>input</code> according to the
<a href="#rdf-conversion-algorithm">RDF Conversion Algorithm</a>, calling
the provided <code>tripleCallback</code> for each triple generated.
@@ -884,32 +887,30 @@
<section>
<h2>Value Expansion</h2>
<p>Some values in JSON-LD can be expressed in a compact form. These values
- are required to be expanded at times when processing JSON-LD documents.
- </p>
+ are required to be expanded at times when processing JSON-LD documents.</p>
<p>The algorithm for expanding a <em>value</em> takes an <tref>active property</tref>
and <tref>active context</tref>. It is implemented as follows:</p>
- <ol class="algorithm">
- <li>If <em>value</em> is <tref>true</tref>, <tref>false</tref> or <tref>number</tref>, expand the value by
- adding a two new key-value pairs. The first key-value pair will be <code>@value</code> and
- the string representation of <em>value</em>. The second key-value pair will be <code>@type></code>,
- and the expanded version of <code>xsd:boolean</code>, <code>xsd:integer</code>, or <code>xsd:double</code>,
- depending on <em>value</em>.
- <li>Otherwise, if <tref>active property</tref> is the target of an <code>@id</code> coercion,
- expand the value by adding a new key-value pair where the
- key is <code>@id</code> and the value is the expanded IRI according to the <a href="#iri-expansion">IRI
- Expansion</a> rules.</li>
- <li>Otherwise, if <tref>active property</tref> is the target of typed literal coercion,
- expand <em>value</em> by adding two new key-value pairs. The first key-value pair will be <code>@value</code>
- and the unexpanded value. The second key-value pair will be <code>@type</code> and the associated coercion
- datatype expanded according to the <a href="#iri-expansion">IRI Expansion</a> rules.</li>
- <li>Otherwise, if the <tref>active context</tref> has a <code>@language</code>,
- expand <em>value</em> by adding two new key-value pairs. The first key-value pair will be <code>@value</code>
- and the unexpanded value. The second key-value pair will be <code>@language</code> and value of
- <code>@language</code> from the <tref>active context</tref>.</li> <li>Otherwise, <em>value</em> is already
- expanded.</li>
- </ol>
- </p>
+ <ol class="algorithm">
+ <li>If <em>value</em> is <tref>true</tref>, <tref>false</tref> or <tref>number</tref>, expand the value by
+ adding a two new key-value pairs. The first key-value pair will be <code>@value</code> and
+ the string representation of <em>value</em>. The second key-value pair will be <code>@type></code>,
+ and the expanded version of <code>xsd:boolean</code>, <code>xsd:integer</code>, or <code>xsd:double</code>,
+ depending on <em>value</em>.</li>
+ <li>Otherwise, if <tref>active property</tref> is the target of an <code>@id</code> coercion,
+ expand the value by adding a new key-value pair where the
+ key is <code>@id</code> and the value is the expanded IRI according to the <a href="#iri-expansion">IRI
+ Expansion</a> rules.</li>
+ <li>Otherwise, if <tref>active property</tref> is the target of typed literal coercion,
+ expand <em>value</em> by adding two new key-value pairs. The first key-value pair will be <code>@value</code>
+ and the unexpanded value. The second key-value pair will be <code>@type</code> and the associated coercion
+ datatype expanded according to the <a href="#iri-expansion">IRI Expansion</a> rules.</li>
+ <li>Otherwise, if the <tref>active context</tref> has a <code>@language</code>,
+ expand <em>value</em> by adding two new key-value pairs. The first key-value pair will be <code>@value</code>
+ and the unexpanded value. The second key-value pair will be <code>@language</code> and value of
+ <code>@language</code> from the <tref>active context</tref>.</li> <li>Otherwise, <em>value</em> is already
+ expanded.</li>
+ </ol>
</section>
<section>
@@ -955,7 +956,7 @@
<p>Expansion is the process of taking a JSON-LD document and applying a
context such that all IRI, datatypes, and literal values are expanded so
that the context is no longer necessary. JSON-LD document expansion
- is typically used as a part of <a href="#normalization">Framing</a> or
+ is typically used as a part of <a href="#framing">Framing</a> or
<a href="#normalization">Normalization</a>.</p>
<p>For example, assume the following JSON-LD input document:</p>
@@ -1024,14 +1025,14 @@
using this algorithm, passing copies of the <tref>active context</tref> and <tref>active
property</tref>.</li>
<li>Otherwise, expand the value according to the <a href="#value-expansion">Value Expansion</a> rules,
- passing <tref>active property</tref>.
+ passing <tref>active property</tref>.</li>
</ol>
</li>
<li>Remove the context from the object.</li>
</ol>
</li>
<li>Otherwise, expand <em>value</em> according to the <a href="#value-expansion">Value Expansion</a> rules,
- passing <tref>active property</tref>.
+ passing <tref>active property</tref>.</li>
</ol>
</section>
@@ -1127,7 +1128,7 @@
<li>Otherwise:
<ol class="algorithm">
<li>If the key is not a <tref>keyword</tref>, set as <tref>active property</tref> and
- compact according to <a href="#iri-compaction">IRI Compaction</a>.
+ compact according to <a href="#iri-compaction">IRI Compaction</a>.</li>
<li>If the value is an object
<ol class="algorithm">
<li>If the value contains only an <code>@id</code> key or the value contains a
@@ -1141,7 +1142,7 @@
</li>
<li>Otherwise, if the value is an <tref>array</tref>, the compacted value is the result of
performing this algorithm on the value.</li>
- <li>Otherwise, the value is already compacted.
+ <li>Otherwise, the value is already compacted.</li>
</ol>
</li>
</ol>
@@ -1322,6 +1323,10 @@
<tref>JSON-LD output</tref>. The following series of steps is the recursive
portion of the framing algorithm:</p>
+<p class="issue">Doubtful that the Framing Algorithm requires the
+ <a href="#normalization-algorithm">Normalization Algorithm</a>
+ any longer, perhaps needs to be a <em>Flattening Algorithm</em> instead.</p>
+
<ol class="algorithm">
<li>Initialize the <tref>framing context</tref> by setting the
<tref>object embed flag</tref>, clearing the
@@ -1460,15 +1465,15 @@
<p class="issue">This algorithm is a work in progress, do not implement it.</p>
<p>Normalization is the process of taking <tref>JSON-LD input</tref> and
- performing a deterministic transformation on that input that results in all
- aspects of the graph being fully expanded and named in the
- <tref>JSON-LD output</tref>. The normalized output is generated in such a way
- that any conforming JSON-LD processor will generate identical output
- given the same input. The problem is a fairly difficult technical
- problem to solve because it requires a directed graph to be ordered into a
- set of nodes and edges in a deterministic way. This is easy to do when all of
- the nodes have unique names, but very difficult to do when some of the nodes
- are not labeled.</p>
+ performing a deterministic transformation on that input that results in
+ a normalized and serialized RDF representation.
+ The normalized output is generated in such a way
+ that any conforming JSON-LD (or other RDF) processor will generate identical serialized output
+ given the same input.</p>
+
+<p>Normalization is achieved by transforming <tref>JSON-LD input</tref> to RDF,
+ as described in <a href="#rdf-conversion">RDF Conversion</a>, invoking the normalization procedure
+ as described in [[!RDF-NORMALIZATION]], returning the serialized results.</p>
<p>Normalization is useful when comparing two graphs against one another,
when generating a detailed list of differences between two graphs, and
@@ -1496,988 +1501,26 @@
<p>The example below is the normalized form of the JSON-LD document above:</p>
-<p class="note">Whitespace is used below to aid readability. The normalization
- algorithm for JSON-LD removes all unnecessary whitespace in the fully
- normalized form.</p>
-
<pre class="example" data-transform="updateExample">
<!--
-[{
- "@id": "_:c14n0",
- "http://xmlns.com/foaf/0.1/homepage": {
- "@id": "http://manu.sporny.org/"
- },
- "http://xmlns.com/foaf/0.1/name": "Manu Sporny"
-}]
+_:c14n0 <http://xmlns.com/foaf/0.1/homepage> <http://manu.sporny.org/> .
+_:c14n0 <http://xmlns.com/foaf/0.1/name> "Manu Sporny" .
-->
</pre>
-<p>Notice how all of the <tref>term</tref>s have been expanded and sorted in
- alphabetical order. Also, notice how the <tref>subject</tref> has been labeled with a
- named <tref>blank node</tref>. Normalization ensures that any arbitrary graph
- containing exactly the same information would be normalized to exactly the same form
- shown above.</p>
-
-<p>In time, there may be more than one normalization algorithm that will need
- to be identified. For identification purposes, this algorithm is named
- "Universal Graph Normalization Algorithm 2011"
- (<abbr title="Universal Graph Normalization Algorithm 2011">UGNA2011</abbr>).</p>
-
-<section>
-<h3>Normalization Algorithm Terms</h3>
- <dl>
- <dt><tdef>label</tdef></dt>
- <dd>
- The subject <tref>IRI</tref> associated with a graph node. The subject IRI is expressed
- using a key-value pair in a <tref>JSON object</tref> where the key is
- <code>@id</code> and the value is a string that is an IRI or
- a <tref>JSON object</tref> containing the key <code>@id</code> and
- a value that is a string that is an IRI.
- </dd>
- <dt><tdef>list of expanded nodes</tdef></dt>
- <dd>
- A list of all nodes in the <tref>JSON-LD input</tref> graph containing no
- 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>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>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 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
- value typically takes the form of <code>s<NUMBER></code> or
- <code>c<NUMBER></code>.
- </dd>
-</dl>
-</section>
-
-<section>
-<h3>Normalization State</h3>
-
-<p>When performing the steps required by the normalization algorithm,
- it is helpful to track the many pieces of information in a
- data structure called the <tdef>normalization state</tdef>. Many of these
- pieces simply provide indexes into the graph. The information
- contained in the <tref>normalization state</tref> is described below.</p>
-
-<dl>
- <dt><tdef>node state</tdef></dt>
- <dd>
- Each node in the graph will be assigned a <tref>node state</tref>. This
- state contains the information necessary to deterministically
- <tref>label</tref> all nodes in the graph. A <tref>node state</tref>
- includes:
- <dl>
- <dt><tdef>node reference</tdef></dt>
- <dd>
- A <tref>node reference</tref> is a reference to a node in the graph.
- For a given <tref>node state</tref>, its <tref>node reference</tref>
- refers to the node that the state is for. When a
- <tref>node state</tref> is created, its <tref>node reference</tref>
- should be to the node it is created for.
- </dd>
- <dt><tdef>outgoing list</tdef></dt>
- <dd>
- Lists the <tref>label</tref>s for all nodes that are properties of
- the <tref>node reference</tref>. This list should be initialized
- by iterating over every object associated with a property in the
- <tref>node reference</tref> adding its label if it is another node.
- </dd>
- <dt><tdef>incoming list</tdef></dt>
- <dd>
- Lists the <tref>label</tref>s for all nodes in the graph for which
- the <tref>node reference</tref> is a property. This list is
- initialized to an empty list.
- </dd>
- <dt><tdef>outgoing serialization map</tdef></dt>
- <dd>
- Maps node <tref>label</tref>s to <tref>serialization label</tref>s.
- This map is initialized to an empty map. When this map is populated,
- it will be filled with keys that are the <tref>label</tref>s of every node in the
- graph with a label that begins with <code>_:</code> and that has a
- path, via properties, that starts with the
- <tref>node reference</tref>.
- </dd>
- <dt><tdef>outgoing serialization</tdef></dt>
- <dd>
- A string that can be lexicographically compared to the
- <tref>outgoing serialization</tref>s of other
- <tref>node state</tref>s. It is a representation of the
- <tref>outgoing serialization map</tref> and other related
- information. This string is initialized to an empty string.
- </dd>
- <dt><tdef>incoming serialization map</tdef></dt>
- <dd>
- Maps node <tref>label</tref>s to <tref>serialization label</tref>s.
- This map is initialized to an empty map. When this map is populated,
- it will be filled with keys that are the <tref>label</tref>s of every
- node in the graph with a <tref>label</tref> that begins with
- <code>_:</code> and that has a path, via properties, that ends with
- the <tref>node reference</tref>.
- </dd>
- <dt><tdef>incoming serialization</tdef></dt>
- <dd>
- A string that can be lexicographically compared to the
- <tref>outgoing serialization</tref>s of other
- <tref>node state</tref>s. It is a representation of the
- <tref>incoming serialization map</tref> and other related
- information. This string is initialized to an empty string.
- </dd>
- </dl>
- </dd>
- <dt><tdef>node state map</tdef></dt>
- <dd>
- A mapping from a node's <tref>label</tref> to a <tref>node state</tref>.
- It is initialized to an empty map.
- </dd>
- <dt><tdef>labeling prefix</tdef></dt>
- <dd>
- The labeling prefix is a string that is used as the beginning of a node
- <tref>label</tref>. It should be initialized to a random base string that
- starts with the characters <code>_:</code>, is not used by any other
- node's <tref>label</tref> in the <tref>JSON-LD input</tref>, and does not
- start with the characters <code>_:c14n</code>. The prefix has two uses.
- First it 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. Second, it will eventually be set to <code>_:c14n</code> to
- generate the final, deterministic labels for nodes in the graph. This
- prefix will be concatenated with the <tref>labeling counter</tref> to
- produce a node <tref>label</tref>. For example, <code>_:j8r3k</code> is
- a proper initial value for the <tref>labeling prefix</tref>.
- </dd>
- <dt><tdef>labeling counter</tdef></dt>
- <dd>
- A counter that is used to label nodes. It is appended to the
- <tref>labeling prefix</tref> to create a node <tref>label</tref>. It is
- initialized to <code>1</code>.
- </dd>
- <dt><tdef>deterministic labeling counter</tdef></dt>
- <dd class="issue">
- Not defined.
- </dd>
- <dt><tdef>map of flattened nodes</tdef></dt>
- <dd>
- A map containing a representation of all nodes in the graph where the
- key is a node <tref>label</tref> and the value is a single
- <tref>JSON object</tref> that has no nested sub-objects
- and has had all properties for the same node merged into a single
- <tref>JSON object</tref>.
- </dd>
-</dl>
-
-</section>
-
<section>
<h3>Normalization Algorithm</h3>
-<p>The normalization algorithm expands the <tref>JSON-LD input</tref>,
- flattens the data structure, and creates an initial set of names for all
- nodes in the graph. The flattened data structure is then processed by a
- node labeling algorithm in order to get a fully expanded and named list of
- nodes which is then sorted. The result is a deterministically named and
- ordered list of graph nodes.</p>
-
-<ol class="algorithm">
- <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>Create a <tref>normalization state</tref>.</li>
- <li>Initialize the <tref>map of flattened nodes</tref> by recursively
- processing every <tdef>expanded node</tdef> in the
- <strong>expanded input</strong> in depth-first order:
- <ol class="algorithm">
- <li>If the <tref>expanded node</tref> is an unlabeled node, add a
- new key-value pair to the <tref>expanded node</tref>
- where the key is <code>@id</code> and the value is the
- concatenation of the <tref>labeling prefix</tref>
- and the string value of the <tref>labeling counter</tref>.
- Increment the <tref>labeling counter</tref>.</li>
- <li>Add the <tref>expanded node</tref> to the
- <tref>map of flattened nodes</tref>:
- <ol class="algorithm">
- <li>If the <tref>expanded node</tref>'s <tref>label</tref> is already
- in the
- <tref>map of flattened nodes</tref> merge all properties from the
- entry in the <tref>map of flattened nodes</tref> into the
- <tref>expanded node</tref>.</li>
- <li>Go through every property associated with an array in the
- <tref>expanded node</tref> and remove any duplicate <tref>IRI</tref> entries from
- the array. If the resulting array only has one IRI entry, change it
- from an array to an object.</li>
- <li>Set the entry for the <tref>expanded node</tref>'s <tref>label</tref>
- in the <tref>map of flattened nodes</tref> to the
- <tref>expanded node</tref>.
- </li>
- </ol>
- </li>
- <li>After exiting the recursive step, replace the reference to the
- <tref>expanded node</tref> with an object containing a single
- key-value pair where the key is <code>@id</code> and the value is
- the value of the <code>@id</code> key in the node.</li>
- </ol>
- </li>
- <li>For every entry in the <tref>map of flattened nodes</tref>, insert a
- key-value pair into the <tref>node state map</tref> where the key is the
- key from the <tref>map of flattened nodes</tref> and the value is a
- <tref>node state</tref> where its <tref>node reference</tref> refers to
- the value from the <tref>map of flattened nodes</tref>.</li>
- <li>Populate the <tref>incoming list</tref> for each <tref>node state</tref>
- by iterating over every node in the graph and adding its <tref>label</tref>
- to the <tref>incoming list</tref> associated with each node found in its
- properties.</li>
- <li>For every entry in the <tref>node state map</tref> that has a
- <tref>label</tref> that begins with <code>_:c14n</code>, relabel the node using the
- <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>.</li>
- <li>Label all
- of the nodes that contain a <code>@id</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>.</li>
-</ol>
-</section>
-
-<section>
-<h4>Node Relabeling Algorithm</h4>
-
-<p>This algorithm renames a node by generating a unique
-<tdef>new label</tdef> and updating all references to that <tref>label</tref>
-in the <tref>node state map</tref>. The <tdef>old label</tdef> and the
-<tref>normalization state</tref> must be given as an input to the
-algorithm. The <tref>old label</tref> is the current <tref>label</tref> of
-the node that is to be relabeled.</p>
-
-<p>The node relabeling algorithm is as follows:</p>
-
-<ol class="algorithm">
- <li>If the <tref>labeling prefix</tref> is <code>_:c14n</code> and the
- <tref>old label</tref> begins with <code>_:c14n</code> then return as
- the node has already been renamed.
- </li>
- <li>Generate the <tref>new label</tref> by concatenating the
- <tref>labeling prefix</tref> with the string value of the
- <tref>labeling counter</tref>. Increment the <tref>labeling counter</tref>.
- </li>
- <li>For the <tref>node state</tref> associated with the
- <tref>old label</tref>, update every node in the <tref>incoming list</tref>
- by changing all the properties that reference the <tref>old label</tref> to
- the <tref>new label</tref>.
- </li>
- <li>Change the <tref>old label</tref> key in the <tref>node state map</tref>
- to the <tref>new label</tref> and set the associated
- <tref>node reference</tref>'s <tref>label</tref> to the
- <tref>new label</tref>.
- </li>
-</ol>
-</section>
-
-<section>
-<h4>Deterministic Labeling Algorithm</h4>
-
-<p>The deterministic labeling algorithm takes the
-<tref>normalization state</tref>
-and produces a <tdef>list of finished nodes</tdef> that is sorted and
-contains deterministically named and expanded nodes from the graph.</p>
-
-<ol class="algorithm">
- <li>Set the <tref>labeling prefix</tref> to <code>_:c14n</code>, the
- <tref>labeling counter</tref> to <code>1</code>,
- the <tref>list of finished nodes</tref> to an empty array, and create
- an empty array, the <tdef>list of unfinished nodes</tdef>.</li>
- <li>For each <tref>node reference</tref> in the <tref>node state map</tref>:
- <ol class="algorithm">
- <li>If the node's <tref>label</tref> does not start with <code>_:</code>
- then put the <tref>node reference</tref> in the
- <tref>list of finished nodes</tref>.
- </li>
- <li>If the node's <tref>label</tref> does start with <code>_:</code>
- then put the <tref>node reference</tref> in the
- <tref>list of unfinished nodes</tref>.
- </li>
- </ol>
- </li>
- <li>Append to the <tref>list of finished nodes</tref> by processing
- the remainder of the <tref>list of unfinished nodes</tref> until it is
- empty:
- <ol class="algorithm">
- <li>Sort the <tref>list of unfinished nodes</tref> in descending order
- according to the
- <a href="#deep-comparison-algorithm">Deep Comparison Algorithm</a> to
- determine the sort order.</li>
- <li>Create a <tdef>list of labels</tdef> and initialize it to an
- empty array.</li>
- <li>For the first node from the <tref>list of unfinished nodes</tref>:
- <ol class="algorithm">
- <li>Add its <tref>label</tref> to the <tref>list of labels</tref>.
- </li>
- <li>For each key-value pair from its associated
- <tref>outgoing serialization map</tref>, add the key to a list and
- then sort the list according to the lexicographical order of the
- keys' associated values. Append the list to the
- <tref>list of nodes to label</tref>.
- <span class="issue"><tdef>list of nodes to label</tdef> not defined.</span>
- </li>
- <li>For each key-value pair from its associated
- <tref>incoming serialization map</tref>, add the key to a list and
- then sort the list according to the lexicographical order of the
- keys' associated values. Append the list to the
- <tref>list of nodes to label</tref>.
- </li></ol></li>
- <li>For each <tref>label</tref> in the <tref>list of labels</tref>,
- relabel the associated node according to the
- <a href="#node-relabeling-algorithm">Node Relabeling Algorithm</a>. If
- any <tref>outgoing serialization map</tref> contains a key that
- matches the <tref>label</tref>, clear the map and set the associated
- <tref>outgoing serialization</tref> to an empty string. If any
- <tref>incoming serialization map</tref> contains a key that
- matches the <tref>label</tref>, clear the map and set the associated
- <tref>incoming serialization</tref> to an empty string.
- </li>
- <li>
- Remove each node with a <tref>label</tref> that starts with
- <code>_:c14n</code> from the <tref>list of unfinished nodes</tref> and
- add it to the <tref>list of finished nodes</tref>.
- </li>
- </ol>
- </li>
- <li>Sort the <tref>list of finished nodes</tref> in descending order
- according to the
- <a href="#deep-comparison-algorithm">Deep Comparison Algorithm</a> to
- determine the sort order.</li>
-</ol>
-</section>
-
-<section>
-<h4>Shallow Comparison Algorithm</h4>
-
-<p>
- The shallow comparison algorithm takes two unlabeled nodes,
- <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>Compare the total number of node properties. The node with fewer
- properties is first.</li>
- <li>Lexicographically sort the property <tref>IRI</tref>s 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 values of each property against one another:
- <ol class="algorithm">
- <li>The node associated with fewer property values is first.
- </li>
- <li>Create an <tdef>alpha list</tdef> by adding all values associated
- with the <tref>alpha</tref> property that are not unlabeled nodes.
- </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.
- </li>
- <li>Compare the length of <tref>alpha list</tref> and
- <tref>beta list</tref>. The node associated with the list containing
- the fewer number of items is first.</li>
- <li>Sort <tref>alpha list</tref> and <tref>beta list</tref> according to
- the
- <a href="#object-comparison-algorithm">Object Comparison Algorithm</a>.
- 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> according to the
- <a href="#object-comparison-algorithm">Object Comparison Algorithm</a>.
- The node associated with the lesser item is first.</li>
- </ol>
- </li>
- <li>Process the <tref>incoming list</tref>s associated with each node to
- determine order:
- <ol class="algorithm">
- <li>The node with the shortest <tref>incoming list</tref> is first.</li>
- <li>Sort the <tref>incoming list</tref>s according to incoming property
- and then incoming <tref>label</tref>.</li>
- <li>The node associated with the fewest number of incoming nodes is
- first.</li>
- <li>For each offset into the <tref>incoming list</tref>s,
- compare the associated properties and <tref>label</tref>s:
- <ol class="algorithm">
- <li>The node associated with a <tref>label</tref> that does not begin with
- <code>_:</code> is first.</li>
- <li>If the nodes' <tref>label</tref>s do not begin with
- <code>_:</code>, then the node associated with the
- lexicographically lesser <tref>label</tref> is first.</li>
- <li>The node associated with the lexicographically lesser associated
- property is first.</li>
- <li>The node with the <tref>label</tref> that does not begin with
- <code>_:c14n</code> is first.</li>
- <li>The node with the lexicographically lesser <tref>label</tref>
- is first.</li>
- </ol>
- </li>
- </ol>
- </li>
- <li>Otherwise, the nodes are equivalent.</li>
-</ol>
-</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 <tref>string</tref> and the other is not, the value that is
- a string is first.
- </li>
- <li>If both values are <tref>string</tref>s, 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>@value</code> is first.
- </li>
- <li>The lexicographically lesser string associated with
- <code>@type</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 <tref>IRI</tref>s, the
- lexicographically lesser string associated with <code>@id</code>
- is first.</li>
- <li>Otherwise, the two values are equivalent.</li>
-</ol>
-
-</section>
-
-<section>
-<h4>Deep Comparison Algorithm</h4>
-
-<p>
- The deep comparison algorithm is used to compare the difference between two
- nodes, <tref>alpha</tref> and <tref>beta</tref>.
- A deep comparison takes the incoming and outgoing node edges in
- a graph into account if the number of properties and value of those properties
- are identical. The algorithm is helpful when sorting a list of nodes and will
- return whichever node should be placed first in a list if the two nodes are
- not truly equivalent.</p>
-
-<p>When performing the steps required by the deep comparison algorithm, it
- is helpful to track state information about mappings. The information
- contained in a <tref>mapping state</tref> is described below.</p>
-
-<dl class="algorithm">
- <dt><tdef>mapping state</tdef></dt>
- <dd>
- <dl>
- <dt><tdef>mapping counter</tdef></dt>
- <dd>
- Keeps track of the number of nodes that have been mapped to
- <tref>serialization label</tref>s. It is initialized to
- <code>1</code>.
- </dd>
- <dt><tdef>processed labels map</tdef></dt>
- <dd>
- Keeps track of the <tref>label</tref>s of nodes that have already
- been assigned <tref>serialization label</tref>s. It is initialized
- to an empty map.
- </dd>
- <dt><tdef>serialized labels map</tdef></dt>
- <dd>
- Maps a node <tref>label</tref> to its associated
- <tref>serialization label</tref>. It is initialized to an empty map.
- </dd>
- <dt><tdef>adjacent info map</tdef></dt>
- <dd>
- Maps a <tref>serialization label</tref> to the node
- <tref>label</tref> associated with it, the list of sorted
- <tref>serialization label</tref>s for adjacent nodes, and the map of
- adjacent node <tref>serialization label</tref>s to their associated
- node <tref>label</tref>s. It is initialized to an empty map.
- </dd>
- <dt><tdef>key stack</tdef></dt>
- <dd>
- A stack where each element contains an array of adjacent
- <tref>serialization label</tref>s and an index into that array. It
- is initialized to a stack containing a single element where its
- array contains a single string element <code>s1</code> and its
- index is set to <code>0</code>.
- </dd>
- <dt><tdef>serialized keys</tdef></dt>
- <dd>
- Keeps track of which <tref>serialization label</tref>s have already
- been written at least once to the <tref>serialization string</tref>.
- It is initialized to an empty map.
- </dd>
- <dt><tdef>serialization string</tdef></dt>
- <dd>
- A string that is incrementally updated as a serialization is built.
- It is initialized to an empty string.
- </dd>
- </dl>
- </dd>
-</dl>
-
-<p>The deep comparison algorithm is as follows:</p>
+<p>The normalization algorithm transforms the <tref>JSON-LD input</tref>
+ into RDF, normalizes it according to [[!RDF-NORMALIZATION]]. The result
+ is a serialized representation that represents a deterministically
+ RDF graph.</p>
<ol class="algorithm">
- <li>Perform a comparison between <tref>alpha</tref> and <tref>beta</tref>
- according to the
- <a href="#shallow-comparison-algorithm">Shallow Comparison Algorithm</a>.
- If the result does not show that the two nodes are equivalent, return
- the result.
- </li>
- <li>Compare incoming and outgoing edges for each node, updating their
- associated <tref>node state</tref> as each node is processed:
- <ol class="algorithm">
- <li>If the <tref>outgoing serialization map</tref> for <tref>alpha</tref>
- is empty, generate the serialization according to the
- <a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
- Provide <tref>alpha</tref>'s <tref>node state</tref>, a new
- <tref>mapping state</tref>,
- <code>outgoing direction</code> to the algorithm as inputs.</li>
- <li>If the <tref>outgoing serialization map</tref> for <tref>beta</tref>
- is empty, generate the serialization according to the
- <a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
- Provide <tref>beta</tref>'s <tref>node state</tref>, a new
- <tref>mapping state</tref>, and
- <code>outgoing direction</code> to the algorithm as inputs.</li>
- <li>If <tref>alpha</tref>'s <tref>outgoing serialization</tref> is
- lexicographically less than <tref>beta</tref>'s, then
- <tref>alpha</tref> is first. If it is greater, then <tref>beta</tref>
- is first.</li>
- <li>If the <tref>incoming serialization map</tref> for <tref>alpha</tref>
- is empty, generate the serialization according to the
- <a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
- Provide <tref>alpha</tref>'s <tref>node state</tref>, a new
- <tref>mapping state</tref> with its <tref>serialized labels map</tref>
- set to a copy of <tref>alpha</tref>'s
- <tref>outgoing serialization map</tref>, and
- <code>incoming direction</code> to the algorithm as inputs.</li>
- <li>If the <tref>incoming serialization map</tref> for <tref>beta</tref>
- is empty, generate the serialization according to the
- <a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
- Provide <tref>beta</tref>'s <tref>node state</tref>, a new
- <tref>mapping state</tref> with its <tref>serialized labels map</tref>
- set to a copy of <tref>beta</tref>'s
- <tref>outgoing serialization map</tref>, and
- <code>incoming direction</code> to the algorithm as inputs.</li>
- <li>If <tref>alpha</tref>'s <tref>incoming serialization</tref> is
- lexicographically less than <tref>beta</tref>'s, then
- <tref>alpha</tref> is first. If it is greater, then <tref>beta</tref>
- is first.</li>
- </ol></li>
-</ol>
-</section>
-
-<section>
-<h4>Node Serialization Algorithm</h4>
-
-<p>The node serialization algorithm takes a <tref>node state</tref>, a
- <tref>mapping state</tref>, and a <tdef>direction</tdef> (either
- <code>outgoing direction</code> or <code>incoming direction</code>) as
- inputs and generates a deterministic serialization for the
- <tref>node reference</tref>.</p>
-
-<ol class="algorithm">
- <li>If the <tref>label</tref> exists in the
- <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 labels map</tref> to <code>true</code>.
- </li>
- <li>Generate the next <tref>serialization label</tref> for the
- <tref>label</tref> according to the
- <a href="#serialization-label-generation-algorithm">Serialization Label Generation Algorithm</a>.
- </li>
- <li>Create an empty map called the <tdef>adjacent serialized labels map</tdef>
- that will store mappings from <tref>serialization label</tref>s to adjacent
- node <tref>label</tref>s.</li>
- <li>Create an empty array called the
- <tdef>adjacent unserialized labels list</tdef> that will store
- <tref>label</tref>s of adjacent nodes that haven't been assigned
- <tref>serialization label</tref>s yet.
- </li>
- <li>For every <tref>label</tref> in a list, where the list the
- <tref>outgoing list</tref> if
- the <tref>direction</tref> is <code>outgoing direction</code> and the
- <tref>incoming list</tref> otherwise, if the <tref>label</tref> starts with
- <code>_:</code>, it is the <tdef>target node label</tdef>:
- <ol class="algorithm">
- <li>Look up the <tref>target node label</tref> in the
- <tref>processed labels map</tref> and if a mapping exists,
- update the <tref>adjacent serialized labels map</tref> where the key is
- the value in the <tref>serialization map</tref>
- (<span class="issue"><tdef>serialization map</tdef> is used, but should it be <tref>directed serialization map</tref>,
- <tref>outgoing serialization map</tref>or <tref>incoming serialization map</tref>?</span>)
- and the value is the
- <tref>target node label</tref>.</li>
- <li>Otherwise, add the <tref>target node label</tref> to the
- <tref>adjacent unserialized labels list</tref>.</li>
- </ol>
- </li>
- <li>Set the <tdef>maximum serialization combinations</tdef> to
- <code>1</code> or the length of the
- <tref>adjacent unserialized labels list</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>
- passing the <tref>node state</tref>, the <tref>mapping state</tref> for the
- first iteration and a copy of it for each subsequent iteration, the
- generated <tref>serialization label</tref>, the <tref>direction</tref>,
- the <tref>adjacent serialized labels map</tref>, and the
- <tref>adjacent unserialized labels list</tref>.
- Decrement the <tref>maximum serialization combinations</tref> by
- <code>1</code> for each iteration.</li>
+ <li>Transform the <tref>JSON-LD input</tref> to RDF according to the steps in
+ the <a href="#rdf-conversion-algorithm">RDF Conversion Algorithm</a>.</li>
+ <li>Return the result of [[!RDF-NORMALIZATION]] on that RDF.</li>
</ol>
-
-</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 state</tref> and returns the
- <tref>serialization label</tref>.</p>
-
- <ol class="algorithm">
- <li>If the <tref>label</tref> is already in the
- <tref>serialization labels map</tref>, return its associated value.
- (<span class="issue"><tdef>serialization labels map</tdef> is used, but should it be <tref>directed serialization map</tref>,
- <tref>outgoing serialization map</tref>or <tref>incoming serialization map</tref>?</span>)
- </li>
- <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 counter</tref>. Increment the <tref>mapping counter</tref> by
- <code>1</code>.
- </li>
- <li>Create a new key-value pair in the <tref>serialization labels map</tref>
- where the key is the <tref>label</tref> and the value is the
- generated <tref>serialization label</tref>.
- </li>
- </ol>
-</section>
-
-<section>
-<h4>Combinatorial Serialization Algorithm</h4>
-
-<p>The combinatorial serialization algorithm takes a <tref>node state</tref>, a
- <tref>mapping state</tref>, a <tref>serialization label</tref>, a
- <tref>direction</tref>, a <tref>adjacent serialized labels map</tref>,
- and a <tref>adjacent unserialized labels list</tref> as inputs and generates
- the lexicographically least serialization of nodes relating to the
- <tref>node reference</tref>.</p>
-
-<ol class="algorithm">
- <li>If the <tref>adjacent unserialized labels list</tref> is not empty:
- <ol class="algorithm">
- <li>Copy the <tref>adjacent serialized labels map</tref> to the
- <tdef>adjacent serialized labels map copy</tdef>.</li>
- <li>Remove the first <tdef>unserialized label</tdef> from the
- <tref>adjacent unserialized labels list</tref> and create a new
- <tdef>new serialization label</tdef> according to the
- <a href="#serialization-label-generation-algorithm">Serialization Label Generation Algorithm</a>.</li>
- <li>Create a new key-value mapping in the
- <tref>adjacent serialized labels map copy</tref>
- where the key is the <tref>new serialization label</tref> and the value
- is the <tref>unserialized label</tref>.</li>
- <li>Set the <tdef>maximum serialization rotations</tdef> to
- <code>1</code> or the length of the
- <tref>adjacent unserialized labels list</tref>, whichever is greater.
- </li>
- <li>While the <tref>maximum serialization rotations</tref> is greater than
- <code>0</code>:
- <ol class="algorithm">
- <li>Recursively perform the
- <a href="#combinatorial-serialization-algorithm">Combinatorial Serialization Algorithm</a>
- passing the <tref>mapping state</tref> for the first iteration of the
- loop, and a copy of it for each subsequent iteration.
- </li>
- <li>Rotate the elements in the
- <tref>adjacent unserialized labels list</tref> by shifting each of
- them once to the right, moving the element at the end of the list
- to the beginning of the list.
- </li>
- <li>Decrement the <tref>maximum serialization rotations</tref> by
- <code>1</code> for each iteration.
- </li>
- </ol>
- </li>
- </ol>
- </li>
- <li>If the <tref>adjacent unserialized labels list</tref> is empty:
- <ol class="algorithm">
- <li>Create a <tdef>list of keys</tdef> from the keys in the
- <tref>adjacent serialized labels map</tref> and sort it
- lexicographically.
- </li>
- <li>Add a key-value pair to the <tref>adjacent info map</tref> where
- the key is the <tref>serialization label</tref> and the value is
- an object containing the <tref>node reference</tref>'s label, the
- <tref>list of keys</tref> and the
- <tref>adjacent serialized labels map</tref>.
- </li>
- <li>Update the <tref>serialization string</tref> according to the
- <a href="#mapping-serialization-algorithm">Mapping Serialization Algorithm</a>.
- </li>
- <li>If the <tref>direction</tref> is <code>outgoing direction</code>
- then <tdef>directed serialization</tdef> refers to the
- <tref>outgoing serialization</tref> and the
- <tdef>directed serialization map</tdef> refers to the
- <tref>outgoing serialization map</tref>, otherwise it refers to the
- <tref>incoming serialization</tref> and the
- <tref>directed serialization map</tref> refers to the
- <tref>incoming serialization map</tref>. Compare the
- <tref>serialization string</tref> to the
- <tref>directed serialization</tref> according to the
- <a href="#mapping-serialization-algorithm">Serialization Comparison Algorithm</a>.
- If the <tref>serialization string</tref> is less than or equal to
- the <tref>directed serialization</tref>:
- <ol class="algorithm">
- <li>For each value in the <tref>list of keys</tref>, run the
- <a href="#node-serialization-algorithm">Node Serialization Algorithm</a>.
- </li>
- <li>Update the <tref>serialization string</tref> according to the
- <a href="#mapping-serialization-algorithm">Mapping Serialization Algorithm</a>.
- </li>
- <li>Compare the <tref>serialization string</tref> to the
- <tref>directed serialization</tref> again and if it is less than
- or equal and the length of the <tref>serialization string</tref> is
- greater than or equal to the length of the
- <tref>directed serialization</tref>, then set the
- <tref>directed serialization</tref> to the
- <tref>serialization string</tref> and set the
- <tref>directed serialization map</tref> to the
- <tref>serialized labels map</tref>.
- </li>
- </ol>
- </li>
- </ol>
- </li>
-</ol>
-
-</section>
-
-<section>
-<h4>Serialization Comparison Algorithm</h4>
-
-<p>The serialization comparison algorithm takes two serializations,
- <tref>alpha</tref> and <tref>beta</tref> and returns either which of the two
- is less than the other or that they are equal.</p>
-
-<ol class="algorithm">
- <li>Whichever serialization is an empty string is greater. If they are
- both empty strings, they are equal.</li>
- <li>Return the result of a lexicographical comparison of <tref>alpha</tref>
- and <tref>beta</tref> up to the number of characters in the shortest of
- the two serializations.
- </li>
-</ol>
-</section>
-
-<section>
-<h4>Mapping Serialization Algorithm</h4>
-
-<p>The mapping serialization algorithm incrementally updates the
- <tref>serialization string</tref> in a <tref>mapping state</tref>.</p>
-
-<ol class="algorithm">
- <li>If the <tref>key stack</tref> is not empty:
- <ol class="algorithm">
- <li>Pop the <tdef>serialization key info</tdef> off of the
- <tref>key stack</tref>.
- </li>
- <li>For each <tdef>serialization key</tdef> in the
- <tref>serialization key info</tref> array, starting at
- the <tdef>serialization key index</tdef> from the
- <tref>serialization key info</tref>:
- <ol class="algorithm">
- <li>If the <tref>serialization key</tref> is not in the
- <tref>adjacent info map</tref>, push the
- <tref>serialization key info</tref> onto the
- <tref>key stack</tref> and exit from this loop.
- </li>
- <li>If the <tref>serialization key</tref> is a key in
- <tref>serialized keys</tref>, a cycle has been detected. Append
- the concatenation of the <code>_</code> character and the
- <tref>serialization key</tref> to the
- <tref>serialization string</tref>.</li>
- <li>Otherwise, serialize all outgoing and incoming edges in the
- related node by performing the following steps:
- <ol class="algorithm">
- <li>Mark the <tref>serialization key</tref> as having
- been processed by adding a new key-value pair to
- <tref>serialized keys</tref> where the key
- is the <tref>serialization key</tref> and the value is
- <code>true</code>.
- </li>
- <li>Set the <tdef>serialization fragment</tdef> to the value of
- the <tref>serialization key</tref>.</li>
- <li>Set the <tdef>adjacent info</tdef> to the value of the
- <tref>serialization key</tref> in the
- <tref>adjacent info map</tref>.
- </li>
- <li>Set the <tdef>adjacent node label</tdef> to the node
- <tref>label</tref> from the <tref>adjacent info map</tref>.
- </li>
- <li>If a mapping for the <tref>adjacent node label</tref>
- exists in the <tref>map of all labels</tref>:
- <ol class="algorithm">
- <li>Append the result of the
- <a href="">Label Serialization Algorithm</a> to the
- <tref>serialization fragment</tref>.
- </li>
- </ol>
- <span class="issue"><tdef>map of all labels</tdef> referenced but not defined.</span>
- </li>
- <li>Append all of the keys in the <tref>adjacent info map</tref>
- to the <tref>serialization fragment</tref>.
- </li>
- <li>Append the <tref>serialization fragment</tref> to the
- <tref>serialization string</tref>.
- </li>
- <li>Push a new key info object containing the keys from the
- <tref>adjacent info map</tref> and an index of <code>0</code>
- onto the <tref>key stack</tref>.
- </li>
- <li>Recursively update the <tref>serialization string</tref>
- according to the
- <a href="#mapping-serialization-algorithm">Mapping Serialization Algorithm</a>.
- </li>
- </ol>
- </li>
- </ol>
- </li>
- </ol>
- </li>
-</ol>
-
-</section>
-
-<section>
-<h4>Label Serialization Algorithm</h4>
-
-<p>
-The label serialization algorithm serializes information about a node that
-has been assigned a particular <tref>serialization label</tref>.
-</p>
-
-<ol class="algorithm">
- <li>Initialize the <tdef>label serialization</tdef> to an empty string.</li>
- <li>Append the <code>[</code> character to the
- <tref>label serialization</tref>.</li>
- <li>Append all properties to the <tref>label serialization</tref> by
- processing each key-value pair in the <tref>node reference</tref>,
- excluding the
- <code>@id</code> property. The keys should be processed in
- lexicographical order and their associated values should be processed
- in the order produced by the
- <a href="#object-comparison-algorithm">Object Comparison Algorithm</a>:
- <ol class="algorithm">
- <li>Build a string using the pattern <code><</code><strong>KEY</strong><code>></code>
- where <strong>KEY</strong> is the current key. Append string to the
- <tref>label serialization</tref>.</li>
- <li>The value may be a single object or an array of objects.
- Process all of the objects that are associated with the key, building
- an <tdef>object string</tdef> for each item:
- <ol class="algorithm">
- <li>If the object contains an <code>@id</code> key with a
- value that starts
- with <code>_:</code>, set the <tref>object string</tref> to
- the value <code>_:</code>. If the value does not
- start with <code>_:</code>, build the <tref>object string</tref>
- using the pattern
- <code><</code><strong>IRI</strong><code>></code>
- where <strong>IRI</strong> is the value associated with the
- <code>@id</code> key.</li>
- <li>If the object contains a <code>@value</code> key and a
- <code>@type</code> key, build the <tref>object string</tref>
- using the pattern
- <code>"</code><strong>VALUE</strong><code>"^^<</code><strong>DATATYPE</strong><code>></code>
- where <strong>VALUE</strong> is the value associated with the
- <code>@value</code> key and <strong>DATATYPE</strong> is the
- value associated with the <code>@type</code> key.</li>
- <li>If the object contains a <code>@value</code> key and a
- <code>@language</code> key, build the <tref>object string</tref>
- using the pattern
- <code>"</code><strong>VALUE</strong><code>"@</code><strong>LANGUAGE</strong>
- where <strong>VALUE</strong> is the value associated with the
- <code>@value</code> key and <strong>LANGUAGE</strong> is the
- value associated with the <code>@language</code> key.</li>
- <li>Otherwise, the value is a string. Build the
- <tref>object string</tref> using the pattern
- <code>"</code><strong>VALUE</strong><code>"</code>
- where <strong>VALUE</strong> is the value associated with the
- current key.</li>
- <li>If this is the second iteration of the loop,
- append a <code>|</code> separator character to the
- <tref>label serialization</tref>.</li>
- <li>Append the <tref>object string</tref> to the
- <tref>label serialization</tref>.</li>
- </ol>
- </li>
- </ol>
- </li>
- <li>Append the <code>]</code> character to the
- <tref>label serialization</tref>.</li>
- <li>Append the <code>[</code> character to the
- <tref>label serialization</tref>.</li>
- <li>Append all incoming references for the current
- <tref>label</tref> to the <tref>label serialization</tref> by
- processing all of the items associated with the <tref>incoming list</tref>:
- <ol class="algorithm">
- <li>Build a <tdef>reference string</tdef>
- using the pattern <code><</code><strong>PROPERTY</strong><code>></code><code><</code><strong>REFERER</strong><code>></code>
- where <strong>PROPERTY</strong> is the property associated with the
- incoming reference and <strong>REFERER</strong> is either the subject of
- the node referring to the <tref>label</tref> in the incoming reference
- or <code>_:</code> if <strong>REFERER</strong> begins with
- <code>_:</code>.</li>
- <li>If this is the second iteration of the loop,
- append a <code>|</code> separator character to the
- <tref>label serialization</tref>.</li>
- <li>Append the <tref>reference string</tref> to the
- <tref>label serialization</tref>.</li>
- </ol>
- </li>
- <li>Append the <code>]</code> character to the
- <tref>label serialization</tref>.</li>
- <li>Append all <tref>adjacent node labels</tref> to the
- <tref>label serialization</tref> by concatenating the string value
- for all of them, one after the other, to the
- <tref>label serialization</tref>.
- <span class="issue"><tdef>adjacent node labels</tdef> referenced but not defined.</span></li>
- <li>Push the <tref>adjacent node labels</tref> onto the
- <tref>key stack</tref> and append the result of the
- <a href="#mapping-serialization-algorithm">Mapping Serialization Algorithm</a>
- to the <tref>label serialization</tref>.</li>
-</ol>
-
</section>
</section>