Algorithm

1. Create the canonicalization state.
2. For every quad in input dataset:
   1. For each blank node that occurs in the quad, add a reference to the quad using the blank node identifier in the blank node to quads map, creating a new entry if necessary.
      It seems that quads must be normalized, so that literals with different syntactic representations but the same semantic representations are merged, and that two graphs differing in the syntactic representation of a literal will produce the same set of blank node identifiers.
3. Create a list of non-normalized blank node identifiers non-normalized identifiers and populate it using the keys from the blank node to quads map.
4. Initialize simple, a boolean flag, to true.
5. While simple is true, issue canonical identifiers for blank nodes:
   1. Set simple to false.
   2. Clear hash to blank nodes map.
   3. For each blank node identifier identifier in non-normalized identifiers:
      1. Create a hash, hash, according to the Hash First Degree Quads algorithm.
      2. Add hash and identifier to hash to blank nodes map, creating a new entry if necessary.
   4. For each hash to identifier list mapping in hash to blank nodes map, lexicographically-sorted by hash:
      1. If the length of identifier list is greater than 1, continue to the next mapping.
      2. Use the Issue Identifier algorithm, passing canonical issuer and the single blank node identifier in identifier list, identifier, to issue a canonical replacement identifier for identifier.
      3. Remove identifier from non-normalized identifiers.
      4. Remove hash from the hash to blank nodes map.
      5. Set simple to true.
6. For each hash to identifier list mapping in hash to blank nodes map, lexicographically-sorted by hash:
   1. Create hash path list where each item will be a result of running the Hash N-Degree Quads algorithm.
   2. For each blank node identifier identifier in identifier list:
      1. If a canonical identifier has already been issued for identifier, continue to the next identifier.
      2. Create temporary issuer, an identifier issuer initialized with the prefix _:b.
      3. Use the Issue Identifier algorithm, passing temporary issuer and identifier, to issue a new temporary blank node identifier for identifier.
      4. Run the Hash N-Degree Quads algorithm, passing temporary issuer, and append the result to the hash path list.
   3. For each result in the hash path list, lexicographically-sorted by the hash in result:
      1. For each blank node identifier, existing identifier, that was issued a temporary identifier by identifier issuer in result, issue a canonical identifier, in the same order, using the Issue Identifier algorithm, passing canonical issuer and existing identifier.
7. For each quad, quad, in input dataset:
   1. Create a copy, quad copy, of quad and replace any existing blank node identifiers using the canonical identifiers previously issued by canonical issuer.
   2. Add quad copy to the normalized dataset.
8. Return the normalized dataset.

Algorithm

Algorithm

This algorithm takes the canonicalization state and a reference blank node identifier as inputs.

1. Initialize nquads to an empty list. It will be used to store quads in N-Quads format.
2. Get the list of quads quads associated with the reference blank node identifier in the blank node to quads map.
3. For each quad quad in quads:
   1. Serialize the quad in N-Quads format with the following special rule:
      1. If any component in quad is an blank node, then serialize it using a special identifier as follows:
         1. If the blank node's existing blank node identifier matches the reference blank node identifier then use the blank node identifier _:a, otherwise, use the blank node identifier _:z.

      Note potential need to normalize literals to their canonical representation here as well, if not done on the original input dataset.

4. Sort nquads in lexicographical order.
5. Return the hash that results from passing the sorted, joined nquads through the hash algorithm.

Algorithm

This algorithm creates a hash to identify how one blank node is related to another. It takes the canonicalization state, a related blank node identifier, a quad, an identifier issuer, issuer, and a string position as inputs.

1. Set the identifier to use for related, preferring first the canonical identifier for related if issued, second the identifier issued by issuer if issued, and last, if necessary, the result of the Hash First Degree Quads algorithm, passing related.
2. Initialize a string input to the value of position.
3. If position is not g, append <, the value of the predicate in quad, and > to input.
4. Append identifier to input.
5. Return the hash that results from passing input through the hash algorithm.

Algorithm

The inputs to this algorithm are the canonicalization state, the identifier for the blank node to recursively hash quads for, and path identifier issuer which is an identifier issuer that issues temporary blank node identifiers. The output from this algorithm will be a hash and the identifier issuer used to help generate it.

1. Create a hash to related blank nodes map for storing hashes that identify related blank nodes.
2. Get a reference, quads, to the list of quads in the blank node to quads map for the key identifier.
3. For each quad in quads:
   1. For each component in quad, where component is the subject, object, or graph name, and it is a blank node that is not identified by identifier:
      1. Set hash to the result of the Hash Related Blank Node algorithm, passing the blank node identifier for component as related, quad, path identifier issuer as issuer, and position as either s, o, or g based on whether component is a subject, object, graph name, respectively.
      2. Add a mapping of hash to the blank node identifier for component to hash to related blank nodes map, adding an entry as necessary.
4. Create an empty string, data to hash.
5. For each related hash to blank node list mapping in hash to related blank nodes map, sorted lexicographically by related hash:
   1. Append the related hash to the data to hash.
   2. Create a string chosen path.
   3. Create an unset chosen issuer variable.
   4. For each permutation of blank node list:
      1. Create a copy of issuer, issuer copy.
      2. Create a string path.
      3. Create a recursion list, to store blank node identifiers that must be recursively processed by this algorithm.
      4. For each related in permutation:
         1. If a canonical identifier has been issued for related, append it to path.
         2. Otherwise:
            1. If issuer copy has not issued an identifier for related, append related to recursion list.
            2. Use the Issue Identifier algorithm, passing issuer copy and related and append the result to path.
         3. If chosen path is not empty and the length of path is greater than or equal to the length of chosen path and path is lexicographically greater than chosen path, then skip to the next permutation.
      5. For each related in recursion list:
         1. Set result to the result of recursively executing the Hash N-Degree Quads algorithm, passing related for identifier and issuer copy for path identifier issuer.
         2. Use the Issue Identifier algorithm, passing issuer copy and related and append the result to path.
         3. Append <, the hash in result, and > to path.
         4. Set issuer copy to the identifier issuer in result.
         5. If chosen path is not empty and the length of path is greater than or equal to the length of chosen path and path is lexicographically greater than chosen path, then skip to the next permutation.
      6. If chosen path is empty or path is lexicographically less than chosen path, set chosen path to path and chosen issuer to issuer copy.
   5. Append chosen path to data to hash.
   6. Replace issuer, by reference, with chosen issuer.
6. Return issuer and the hash that results from passing data to hash through the hash algorithm.