Flyology_RDF.Canonicalization

Description

RDF Dataset Canonicalization, RDFC-1.0.

Two datasets that differ only in their blank node labels denote the same thing, and nothing built so far can tell you that: the dataset compares labelled statements, and the round-trip tests deliberately claim less than isomorphism because they had no way to decide it. Canonicalization is what decides it. It assigns every blank node a label derived from its position in the graph rather than from what it was called, so two isomorphic datasets canonicalize to identical bytes.

The algorithm has a documented adversarial case. Distinguishing blank nodes that look alike from every direction requires trying permutations, and a dataset can be built specifically to make that combinatorial. This implementation therefore takes a work bound and reports reaching it as a result rather than running until something else gives out.

Canonicalize

procedure Canonicalize
  (Value        : Datasets.Dataset;
   Output       : out Ada.Strings.Unbounded.Unbounded_String;
   Labels       : out Label_Maps.Map;
   Status       : out Result_Status;
   Maximum_Work : Positive := Default_Maximum_Work;
   Algorithm    : Hash_Algorithm := SHA_256)

Canonicalize, and report which identifier each blank node was issued.

Parameters

Value

Dataset to canonicalize

Output

Canonical N-Quads, meaningful only when Canonicalized

Labels

Input label to issued identifier, empty when not Canonicalized

Status

Whether canonicalization completed

Maximum_Work

Bound on permutation and recursion work

Algorithm

Which digest to use

Canonicalize

procedure Canonicalize
  (Value        : Datasets.Dataset;
   Output       : out Ada.Strings.Unbounded.Unbounded_String;
   Status       : out Result_Status;
   Maximum_Work : Positive := Default_Maximum_Work;
   Algorithm    : Hash_Algorithm := SHA_256)

Canonicalize, reporting rather than raising.

Parameters

Value

Dataset to canonicalize

Output

Canonical N-Quads, meaningful only when Canonicalized

Status

Whether canonicalization completed

Maximum_Work

Bound on permutation and recursion work

Algorithm

Which digest to canonicalize with

Default_Maximum_Work

Default_Maximum_Work : constant := 1_000_000;

Default bound on permutation and recursion work.

Ordinary data does not approach this: the bound exists for datasets designed to be expensive, not for large ones.

Hash_Algorithm

subtype Hash_Algorithm is Digests.Hash_Algorithm;

Which digest to canonicalize with. RDFC-1.0 names SHA-256 and admits SHA-384, and the labels a processor issues differ between them, so this is part of the request rather than a tuning knob.

Is_Isomorphic

function Is_Isomorphic
  (Left, Right  : Datasets.Dataset;
   Maximum_Work : Positive := Default_Maximum_Work;
   Algorithm    : Hash_Algorithm := SHA_256) return Boolean

Report whether two datasets denote the same thing.

This is isomorphism: equal apart from a consistent renaming of blank nodes. It is what a round-trip test wants when the serialization it passed through was entitled to rename them.

Parameters

Left

First dataset

Right

Second dataset

Maximum_Work

Bound applied to each canonicalization

Algorithm

Which digest to canonicalize with

Return value

True when the two canonicalize identically

Raised exceptions

Work_Limit_Error

The bound was reached

Label_Maps

package Label_Maps is new Ada.Containers.Indefinite_Ordered_Maps
  (Key_Type => String, Element_Type => String);

The canonical identifier issued to each blank node, keyed by the label the input used. RDFC-1.0 specifies this map, and it is the only way to say which node in the output was which node in the input.

Result_Status

type Result_Status is (Canonicalized, Work_Limit_Reached);

Outcome of a canonicalization attempt.

Enumeration literals

Canonicalized

The dataset was canonicalized

Work_Limit_Reached

The bound was hit before finishing, so the output is not usable

SHA_256

SHA_256 : constant Hash_Algorithm := Digests.SHA_256;

The digest RDFC-1.0 names.

SHA_384

SHA_384 : constant Hash_Algorithm := Digests.SHA_384;

The one alternative it admits.

To_Canonical_NQuads

function To_Canonical_NQuads
  (Value        : Datasets.Dataset;
   Maximum_Work : Positive := Default_Maximum_Work;
   Algorithm    : Hash_Algorithm := SHA_256) return String

Canonicalize into canonical N-Quads.

Blank nodes are labelled c14n0, c14n1, and so on, in an order derived from the graph rather than from the input.

Parameters

Value

Dataset to canonicalize

Maximum_Work

Bound on permutation and recursion work

Algorithm

Which digest to canonicalize with

Return value

The canonical N-Quads serialization

Raised exceptions

Work_Limit_Error

The bound was reached

Work_Limit_Error

Work_Limit_Error : exception;

Raised by the function form when the work bound is reached.