CBOR is a compact binary data serialization and messaging format. This specification defines CBOR-LD 1.0, a CBOR-based format to serialize Linked Data. The encoding is designed to leverage the existing JSON-LD ecosystem, which is deployed on hundreds of millions of systems today, to provide a compact serialization format for those seeking efficient encoding schemes for Linked Data. By utilizing semantic compression schemes, compression ratios in excess of 60% better than generalized compression schemes are possible. This format is primarily intended to be a way to use Linked Data in storage and bandwidth constrained programming environments, to build interoperable semantic wire-level protocols, and to efficiently store Linked Data in CBOR-based storage engines.

This document is experimental.

There is a reference implementation that is capable of demonstrating the features described in this document.

Introduction

CBOR is a compact binary data serialization and messaging format. This specification defines CBOR-LD 1.0, a CBOR-based format to serialize Linked Data. The encoding is designed to leverage the existing JSON-LD ecosystem, which is deployed on hundreds of millions of systems today, to provide a compact serialization format for those seeking efficient encoding schemes for Linked Data. By utilizing semantic compression schemes, compression ratios in excess of 60% better than generalized compression schemes are possible. This format is primarily intended to be a way to use Linked Data in storage and bandwidth constrained programming environments, to build interoperable semantic wire-level protocols, and to efficiently store Linked Data in CBOR-based storage engines.

How to Read this Document

This document is a detailed specification for a serialization of Linked Data in CBOR. The document is primarily intended for the following audiences:

Contributing

There are a number of ways that one may participate in the development of this specification:

Design Goals and Rationale

CBOR-LD satisfies the following design goals:

Simplicity
Implementations should be simple to implement given an existing JSON-LD implementation.
Efficient Storage
The encoding process should generate an aggressively compact Linked Data binary format.
Generalized Algorithm
The encoding algorithm must be generalized.
Semantic Compression
The encoding format should maximize compression of Linked Data URLs (terms and values). Focusing here ensures that the algorithms can achieve compression ratios better than generalized compression algorithms.
Raw Binary
Base-encoded binary values, and other compressible data types, should be translated to their raw binary forms from base-encoded formats when possible without sacrificing generality.

Similarly, the following are non-goals.

The following minefields have been identified while working on this specification:

Basic Concept

At a high level, CBOR-LD is a compact, binary serialization for JSON-LD that allows the following mechanisms for additional compression:

Codecs are the basic primitive for compressing typed values in a generic way. Semantic compression is for compressing JSON-LD terms. Registry dictionaries are for compressing typed values in a use-case-specific way. Each of these is optional — CBOR-LD can be used with any, all, or none of these compression strategies. Taken together, the set of these strategies that is used for a particular use case is known as a processing model.

Semantic Compression

Semantic compression is a powerful tool for creating compact CBOR-LD payloads. The core idea is to use the information content of external JSON-LD context objects to compress JSON-LD terms. These context objects are available to both the creator and the consumer of the payload, so this is done in an invertible way.

The general semantic compression process is to take a JSON-LD Document and do the following:

  1. Determine whether JSON-LD can be compressed (find `@context` values in JSON-LD document that reference contexts via URIs; embedded context values cannot be compressed)
  2. Process the JSON-LD contexts, building a CBOR-LD term codec map — a list of all terms that can be compressed. Sort the list. Associate byte values with each term, starting at 0 and counting up.
  3. Encode the JSON-LD Document as CBOR-LD. This consists of replacing every key with the byte value associated with the term from the term codec map.
  4. Decode the CBOR-LD bytes to JSON-LD. This consists of replacing every CBOR byte value with the associated key from the term codec map.

CBOR Tags for CBOR-LD

CBOR-LD payloads need to be identifiable as such at the binary level. CBOR natively supports this via its "tag" feature — a header value in the binary data that describes the rest of the payload via a global registry.

To this end, the CBOR tag `0xCB1D` (tag value `51997`) has been registered at the IANA CBOR tag registry to be used for CBOR-LD. The data that immediately follows this tag value identifies the use-case-specific registry entry (if any) that was used to create the compressed payload.

CBOR-LD payloads MUST be structured such that the item tagged with tag `0xCB1D` is a two-element array, and the first element MUST be a major type 0 integer. This integer is a CBOR-LD Registry Entry ID. The binary structure is `tag([registryEntryId, payload])`.

The value of the CBOR-LD Registry Entry ID is then used to look up a CBOR-LD Registry Entry in the CBOR-LD Registry.

CBOR-LD Registry

To enable unbounded extension on possible use cases for CBOR-LD that require different compression table material for consumption while working with a single CBOR tag value, we define the following.

The CBOR-LD Registry is a global list that provides consumers of CBOR-LD payloads the information they need to reconstruct the term codec map required for decompression. A CBOR-LD Registry Entry contains the following:

  1. `Registry Entry ID`: a positive integer.
  2. `Use Case`: what type of CBOR-LD payload this entry is used for.
  3. `typeTables`: an array containing what `Type Tables` (use-case-specific compression tables for compressing typed values rather than JSON-LD terms) are to be used for this registry entry.
  4. `processingModel`: what processing model is used for this registry entry. A processing model specifies the following:
    1. Whether or not semantic compression is used for dynamic JSON-LD term compression,
    2. What codecs are used for dynamic typed value compression.
    The `default` processing model uses semantic compression and includes the codecs specified in this document.
  5. Provisional: a yes/no flag indicating whether the entry is provisional. Provisional entries may change or be removed.

The `typeTables` associated with a CBOR-LD Registry Entry MUST be an array of or JSON objects. The only exception is the string "callerProvidedTable", which may appear in this array, denoting that for this use case, a `Type Table` is required which is not globally defined.

Dereferencing one of these URLs MUST result in a JSON object with the following properties:

  1. `type`: a JSON-LD type.
  2. `table`: a JSON object that maps values of the above type to integers.

If a JSON object is present in the `typeTables` array, it MUST be in the above format.

Registry

The current CBOR-LD Registry can be found here.

To register an entry, follow the instructions in the README. The registry is owned by the W3C JSON-LD Community Group.

Algorithms

In this section, we specify the algorithms required to convert JSON-LD to CBOR-LD and vice versa. The majority of the algorithms in this section relate to the semantic compression feature and are not used in conversions between CBOR-LD and JSON-LD where the CBOR-LD payload does not use semantic compression.

Encoding and Decoding

JSON-LD to CBOR-LD Encoding Algorithm

This algorithm takes a map `typeTable`, an integer `registryEntryId`, and a JSON-LD document `jsonldDocument` as inputs, and returns a hexadecimal string `cborldBytes`.

  1. Set `prefix` to the result of passing `registryEntryId` to .
  2. Set `state` to an empty map.
  3. If the registry entry associated with `registryEntryId` requires semantic compression:
    1. Set `state.strategy` to "compression".
    2. Set `state.typeTable` to `typeTable`.
    3. Set `state.registryEntryId` to `registryEntryId`.
    4. Set `state` to the result of passing `state` to .
    5. Set `output` to the result of passing `state` and `jsonldDocument` as `inputDocument` to .
    6. Set `suffix` to the CBOR encoding of `output`.
  4. Otherwise, set `suffix` to the CBOR encoding of `jsonldDocument`.
  5. Set `cborldBytes` to a hexidecimal encoding of `prefix` prepended to `suffix`.
  6. Return `cborldBytes`.

CBOR-LD to JSON-LD Decoding Algorithm

This algorithm takes a CBOR-LD payload `cborldBytes`, and returns a JSON-LD document `jsonldDocument`.

  1. Set `result` to the result of passing `cborldBytes` to .
  2. Set `state`.`registryEntryId` to `result`.`registryEntryId` and `suffix` to `result`.`suffix`.
  3. Set `state` to an empty map.
  4. If the registry entry associated with `state`.`registryEntryId` uses semantic compression:
    1. Set `state.strategy` to "decompression".
    2. For each entry `type`: `map` in the `typeTables` array in the CBOR-LD Varint Registry Entry associated with `registryEntryId`, add that entry to `state`.`typeTable`, and set the value of `type` in `state`.`reverseTypeTable` to `inverseMap`, where `inverseMap` is `map` with the mapping inverted.
    3. Set `state` to the result of passing `state` to .
    4. Set `input` to the result of decoding `suffix` from bytes to a map.
    5. Set `jsonldDocument` to the result of passing `state` and `input` as `inputDocuments` to .
  5. Otherwise, set `jsonldDocument` to the result of parsing `cborldBytes`.
  6. Return `jsonldDocument`.

Conversion Algorithms

The algorithms in this section describe the behavior of a "converter" for abstractly converting inputs between data forms. When used in conjunction with a "strategy", such as the "compression" and "decompression" strategies defined later in this section, these algorithms can be instantiated to convert between concrete data forms. The "compression" strategy converts from JSON-LD to CBOR-LD, while the "decompression" strategy converts from CBOR-LD to JSON-LD.

Initialize Conversion Algorithm

This algorithm takes and returns a map `state`.

  1. Set `state` to the result of passing `state` to .
  2. Set `state.initialActiveContext` to the result of passing empty maps `termMap` and `previousActiveContext` to .
  3. Set `state.typesEncodedAsBytes` to an empty set.
  4. Add "none", "http://www.w3.org/2001/XMLSchema#date", "http://www.w3.org/2001/XMLSchema#dateTime", and "url" to `state.typesEncodedAsBytes`.
  5. Return `state`.

Convert Document Algorithm

This algorithm takes a map `state` and a map or array of maps `inputDocuments`, and returns a map containing a map `state` and a map or array of maps `outputMaps`.

  1. If `inputDocuments` is an array, set `inputs` to `inputDocuments`. Otherwise, set `inputs` to `[inputDocuments]`.
  2. Set `outputMaps` to an empty array.
  3. For `input` in `inputs`:
    1. Set `output` to an empty map.
    2. Set `result` to the result of passing `state`, `input`, `output`, and `state.initialActiveContext` as `activeContext` to .
    3. Add `result.output` to `outputMaps`.
    4. Set `state` to `result.state`.
  4. If `inputDocuments` is an array, return `outputMaps`. Otherwise, return the first element of `outputMaps`.

General Conversion Algorithm

This algorithm takes maps `input`, `output`, `state`, and `activeContext` as inputs, and returns a map containing maps `state` and `output`.

  1. If `state.strategy` is set to "compression":
    1. Set `contextConversionResult` to the result of , passing `state`, `activeContext`, `input`, and `output`.
    2. Set `activeContext` to `contextConversionResult.activeContext`, `output` to `contextConversionResult.output`, and `state` to `contextConversionResult.state`.
  2. Otherwise, set `activeContext` to `result.activeContext` and `state` to `result.state` of `result` resulting from , passing `state`, `activeContext`, `input`, and `output`.
  3. If `state.strategy` is set to "compression", set `state` to `result.state` and `objectTypes` to `result.objectTypes` for `result` resulting from , passing `state`, `activeContext`, `input`, and `output`.
  4. Otherwise, set `state` to `result.state` and `objectTypes` to `result.objectTypes` for `result` resulting from , passing `state`, `activeContext`, `input`, and `output`.
  5. Set `activeContext` to the result of passing `activeContext` and `objectTypes` to .
  6. If `state.strategy` is set to "compression", set `state` to `result.state` and `termEntries` to `result.termEntries` for `result` resulting from , passing `state`, `input`, and `activeContext`.
  7. Otherwise, set `state` to `result.state`, `output` to `result.output`, and `termEntries` to `result.termEntries` for `result` resulting from , passing `state`, `input`, output, and `activeContext`.
  8. For `[termInfo, value]` in `termEntries`:
    1. Set `term` to `termInfo.term`.
    2. Set `valueActiveContext` to the result of passing `activeContext` and `term` to .
    3. Set `plural` to the value of `termInfo.plural` and `termType` to the value of `@type` in `termInfo.def`.
    4. If `plural` is set to `true`, set `values` to the value of `value`. Otherwise, set `values` to an array containing the value of `value` as a single element.
    5. Set `outputs` to an empty array.
    6. For `unconvertedValue` in `values`:
      1. Set `result` to the result of , passing `state`, `termType`, `unconvertedValue` as `value`, and `valueActiveContext` as `activeContext`.
      2. Set `state` to `result.state` and add `result.output` to `outputs`.
    7. If `plural` is set to `true`, set `outputValues` to `outputs`. Otherwise, set `outputValues` to the first element of `outputs`.
    8. If `state.strategy` is set to "compression", set the value of `termInfo.termId` to map to `outputValues` in `output`. Otherwise, set the value of `termInfo.term` to map to `outputValues` in `output`.
  9. Set `result` to be an empty map.
  10. Set `result.state` to `state` and `result.output` to `output`.
  11. Return `result`.

Convert Value Algorithm

This algorithm takes maps `state`, `activeContext`, `termInfo`, and values `value` and `termType`. It returns a `result` object containing maps `state` and `output`.

  1. If `value` is `null`, return `null`.
  2. If `state`.`strategy` is set to "compression", set `output` to the result of passing `state`, `termType`, `termInfo`, and `value` to .
  3. Otherwise, set `output` to the result of passing `state`, `termType`, `termInfo`, and `value` to .
  4. If `output` is defined, return `result`, a map contatining `state` and `output`.
  5. If `value` is an array:
    1. Set `outputs` to be an empty array.
    2. For `element` of `value`:
      1. Let `result` be the result of , passing `activeContext`, `state`, `termInfo`, `termType`, and `element` as `value`. Set `state` to `result`.`state` and add `result`.`output` to `outputs`.
    3. Set `result` to be an empty map. Set `result`.`state` to `state` and `result`.`output` to `outputs`.
    4. Return `result`.
  6. Set `output` to an empty map.
  7. Set `result` to the result of , passing `state`, `activeContext`, `value` as `input`, and `output`.
  8. Return `result`.

Compression Strategy Algorithms

The algorithms in this section define the "compression" strategy to be used with the "conversion" algorithms defined previously to convert JSON-LD to CBOR-LD.

Convert Contexts for Compression Algorithm

This algorithm takes maps `state`, `activeContext`, `input`, and `output`, and returns a map `result` containing maps `output`, `state`, and `activeContext`.

  1. Set `applyEmbeddedResult` to the result of , passing `state`, `activeContext`, and `input`.
  2. Set `activeContext` to `applyEmbeddedResult.activeContext` and `state` to `applyEmbeddedResult.state`.
  3. If "@context" does not have an entry in `input`:
    1. Set `result` to an empty map.
    2. Set `result.state` to `state` and `result.activeContext` to `activeContext`.
    3. Return `result`.
  4. Set `context` to the value of "@context" in `input`.
  5. Set `encodedContexts` to an empty array.
  6. If `context` is an array, set `isArray` to `true` and `contexts` to `context`. Otherwise, set `isArray` to `false` and `contexts` to `[context]`.
  7. For `contextValue` in `contexts`:
    1. Set `encoderData` to the result of , passing `state.typeTable` and `contextValue`.
    2. If `encoderData` is an empty map, add `contextValue` to `encodedContexts`.
    3. Otherwise, add the value of `encoderData` to `encodedContexts`.
  8. If `isArray` is `true`, set `id` to the value of "@context" in `state.keywordsMap` plus 1 and set the value of `id` in `output` to `encodedContexts`.
  9. Otherwise, set `id` to the value of "@context" in `state.keywordMap` and set the value of `id` in `output` to the first element of `encodedContexts`.
  10. Set `result.output` to `output`, `result.state` to `state`, and `result.activeContext` to `activeContext`.
  11. Return `result`.

Convert Value for Compression Algorithm

This algorithm takes maps `state` and `termInfo`, and values `valueToEncode` and `termType`, and returns a map `encoderData`.

  1. If `valueToEncode` is an object, return.
  2. Otherwise, set `result` to the result of , passing `state`, `termInfo`, `valueToToEncode`, and `termType`.
  3. Return `result`.

Get Input Entries for Compression Algorithm

This algorithm takes maps `state`, `activeContext`, and `input`, and returns a map `state` and an array `entries`.

  1. Initialize `entries` as an empty array.
  2. Set an array `keys` to the keys of `input`, sorted lexicographically.
  3. For `key` in `keys`:
    1. If `key` is "@context", continue.
    2. Set `value` to the value of `key` in `input`.
    3. If `value` is an array, set `plural` to `true`. Otherwise, set `plural` to `false`.
    4. If `key` does not have an entry in `state`.`termToId`, set `termId` to `key`.
    5. Otherwise, if `plural` is `true`, set `termId` to the value of `key` in `state`.`termToId` plus 1.
    6. Otherwise, set `termId` to the value of `key` in `state`.`termToId`.
    7. If `activeContext`.`termMap` has an entry for `key`, set `definition` to the value of `key` in `activeContext`.`termMap`. Otherwise, set `definition` to an empty map.
    8. Set `entryTerm` to be a new map.
    9. Set the value of "term" in `entryTerm` to be the value of `key`. Add `termId`, `plural`, and `definition` to `entryTerm`.
    10. Create an array `entry` with two elements, `entryTerm` and `value`.
    11. Add `entry` to `entries`.
  4. Return a map `result` containing `entries` and `state`.

Get Object Types for Compression Algorithm

This algorithm takes maps `activeContext` and `input`, and returns a set `objectTypes`.

  1. Set `objectTypes` to be an empty set.
  2. For `term` in `activeContext`.`typeTerms`:
    1. If `term` has an entry in `input`:
      1. Set `types` to the value of `term` in `input`.
      2. Add each value in `types` to `objectTypes`.
  3. Return `objectTypes`.

Decompression Strategy Algorithms

The algorithms in this section define the "decompression" strategy to be used with the "conversion" algorithms defined previously to convert CBOR-LD to JSON-LD.

Convert Contexts for Decompression Algorithm

This algorithm takes maps `state`, `activeContext`, `input`, and `output`, and returns a map `result` containing maps `output`, `state`, and `activeContext`.

  1. Set `decoderData` to the result of , passing `state`.`reverseTypeTable`.
  2. Set `contextTermId` to the value of "@context" in `state`.`keywordsMap`.
  3. If `contextTermId` has an entry in `input`, set the value of "@context" in `output` to the result of , passing `decoderData` and the value of `contextTermId` in `input` as `value`.
  4. Set `contextTermIdPlural` to the value of `contextTermId` plus 1.
  5. If `contextTermIdPlural` has an entry in `input`:
    1. If `contextTermId` also had an entry in `input` during the previous check, throw an `ERR_INVALID_ENCODED_CONTEXT` error.
    2. Set `encodedContexts` to be the value of `contextTermIdPlural` in `input`. If `encodedContexts` is not an array, throw an `ERR_INVALID_ENCODED_CONTEXT` error.
    3. Set `contexts` to be an empty array.
    4. For each `valueToDecode` in `encodedContexts`, add the result of passing `decoderData` and `valueToDecode` as `value` to to `contexts`.
    5. Set the value of "@context" in `output` to `contexts`.
  6. Set `embeddedContextResult` to the result of , passing `activeContext`, `output` as `input`, and `state`.
  7. Set `result` to an empty map.
  8. Set `result`.`state` to `embeddedContextResult`.`state` and `result.activeContext` to `embeddedContextResult`.`activeContext`.
  9. Return `result`.

Convert Value for Decompression Algorithm

This algorithm takes maps `state` and `termInfo`, and values `termType` and `valueToDecode`, and returns a value `decodedValue`.

  1. If `value` is a map, return.
  2. Set `decoderData` to the result of , passing `valueToDecode`, `state`, `termInfo`, and `termType`.
  3. Set `decodedValue` to the result of , passing `decoderData`.
  4. Return `decodedValue`.

Get Input Entries for Decompression Algorithm

This algorithm takes maps `state`, `activeContext`, and `input`, and returns a map `state` and an array `entries`.

  1. Initialize `entries` to an empty array.
  2. For key-value pair `key` and `value` in `input`:
    1. If `key` is the value of "@context" in `state`.`keywordsMap` or that value plus 1, continue.
    2. Otherwise, if `key` is a string, set `plural` to false and `term` to `key`.
    3. Otherwise:
      1. If `key` is odd, set `plural` to true. Otherwise, set `plural` to false.
      2. If `plural` is `true`, set `term` to the value of `id` minus 1 in `state`.`idToTerm`. If that value does not have an entry, throw an error ERR_UNKNOWN_CBORLD_TERM_ID.
      3. Otherwise, set `term` to the value of `id` in `state`.`idToTerm`. If that value does not have an entry, throw an error ERR_UNKNOWN_CBORLD_TERM_ID.
    4. Set `definition` to the value of `term` in `activeContext`.`termMap`.
    5. Set `entryTerm` to be a new map.
    6. Set the value of "termId" in `entryTerm` to be the value of `key`. Add `term`, `plural`, and `definition` to `entryTerm`.
    7. Create an array `entry` with two elements, `entryTerm` and `value`.
    8. Add `entry` to `entries`.
  3. Sort `entries` by the value of `term` in each element of `entries`.
  4. Return a map `result` containing `entries` and `state`.

Get Object Types for Decompression Algorithm

This algorithm takes maps `state`, `activeContext`, `input` as inputs, and returns a map `state` and a set `objectTypes`.

  1. Set `objectTypes` to be an empty set.
  2. For `term` in `activeContext`.`typeTerms`:
    1. If `term` does not have an entry in `state`.`termToId`, set `termId` to `term`.
    2. Otherwise, set `termId` to the value of `term` in `state`.`termToId`.
    3. If neither `termId` nor `termId` plus 1 are present in `input`, continue.
    4. Otherwise, if `termId` is present in `input`, set `value` to the value of `termId` in `input`.
    5. Otherwise, set `value` to the value of `termId` plus 1 in `input`.
    6. If `key` is a string, set `plural` to false and `term` to `key`.
    7. Otherwise:
      1. If `key` is odd, set `plural` to true. Otherwise, set `plural` to false.
      2. If `plural` is `true`, set `term` to the value of `id` minus 1 in `state`.`idToTerm`. If that value does not have an entry, throw an error ERR_UNKNOWN_CBORLD_TERM_ID.
      3. Otherwise, set `term` to the value of `id` in `state`.`idToTerm`. If that value does not have an entry, throw an error ERR_UNKNOWN_CBORLD_TERM_ID.
    8. Set `definition` to the value of `term` in `activeContext`.`termMap`.
    9. Set `termInfo` to be a new map.
    10. Add `term`, `termId`, `plural`, and `definition` to `termInfo`.
    11. If `value` is not an array, set `values` to be an array containing as a single element `value`. Otherwise, set `values` to the value of `value`.
    12. For each `value` in `values`:
      1. Set `decoderData` to the result of , passing `value`, `termInfo`, `state`, and "@vocab" as `termType`.
      2. If `decoderData` exists, add the result of , passing `decoderData`, to `objectTypes.
      3. Otherwise, add `value` to `objectTypes`.
  3. Return `objectTypes`.

Active Context Processing

The algorithms in this section describe how to determine what components of the context documents associated with a JSON-LD document are in use at any point during compression or decompression. These algorithms include how to apply embedded, type-scoped, and property-scoped contexts with CBOR-LD. This is in contrast to the Context Loading algorithms defined later in this specification, which describe how to construct the mappings from terms to integers that are the core CBOR-LD compression technique. Together, the Active Context Processing and Context Loading algorithms specify how JSON-LD context documents should be processed when converting to and from CBOR-LD.

Initialize Active Context Algorithm

This algorithm takes maps `previousActiveContext` and `termMap`, and returns a map `activeContext`. It updates the active context in use and finds all aliases for `'@type'`.

  1. Set `activeContext` to a new map.
  2. Set `activeContext.previousActiveContext` to `previousActiveContext`.
  3. Set `activeContext.termMap` to `termMap`.
  4. Set `activeContext.typeTerms` to the array `['@type']`.
  5. For `[term, def]` in `termMap`:
    1. If the value of "@id" in `def` is "@type", add `term` to `activeContext.typeTerms`.
  6. Return `activeContext`.

Apply Embedded Contexts Algorithm

This algorithm takes maps `state`, `activeContext`, and `input` as inputs, and returns a map `result` containing maps `state` and `activeContext`.

  1. Set `termMapUpdateResult` to the result of passing `state`, `activeContext.termMap` as `activeTermMap`, and the value of '@context' in `input` as `contexts` to .
  2. Set `state` to `termMapUpdateResult.state`.
  3. Set `termMap` to `termMapUpdateResult.activeTermMap`.
  4. Set `newActiveContext` to the result of , passing `termMap` and `activeContext` as `previousActiveContext`.
  5. Set `result` to be a new map, and set `result.activeContext` to `newActiveContext` and `result.state` to `state`.
  6. Return `result`.

Apply Property Scoped Contexts Algorithm

This algorithm takes maps `state`, `activeContext`, and a string `term` as inputs and returns a map `result` containing maps `state` and `activeContext`.

  1. Set `revertedTermMap` to the result of , passing `activeContext`.
  2. Set `termDef` to the value of `term` in `activeContext.termMap`. Set `contexts` to the value of "@context" in `termDef`.
  3. Set `termMapUpdateResult` to the result of passing `state`, `revertedTermMap` as `activeTermMap`, `true` as `propertyScope`, and `contexts` to .
  4. Set `state` to `termMapUpdateResult.state`.
  5. Set `termMap` to `termMapUpdateResult.activeTermMap`.
  6. Set `newActiveContext` to the result of , passing `termMap` and `activeContext` as `previousActiveContext`.
  7. Set `result` to be a new map, and set `result.activeContext` to `newActiveContext` and `result.state` to `state`.
  8. Return `result`.

Apply Type Scoped Contexts Algorithm

This algorithm takes maps `state`, `activeContext` ,and a set `objectTypes` as inputs, and returns a map `result` containing maps `state` and `activeContext`.

  1. Set `objectTypesSorted` to an empty array.
  2. Lexicographically sort the elements of `objectTypes` and add the elements to `objectTypesSorted` in order.
  3. Set `newTermMap` to `activeContext.termMap`.
  4. For `type` in `objectTypesSorted`:
    1. Set `typeDef` to the value of `type` in `newTermMap`. Set `contexts` to the value of "@context" in `typeDef`.
    2. Set `termMapUpdateResult` to the result of passing `state`, `newTermMap` as `activeTermMap`, `contexts`, and `true` as `typeScope` to .
    3. Set `state` to `termMapUpdateResult.state` and `newTermMap` to `termMapUpdateResult.activeTermMap`.
  5. Set `newActiveContext` to the result of , passing `newTermMap` as `termMap` and `activeContext` as `previousActiveContext`.
  6. Set `result` to be a new map, and set `result.activeContext` to `newActiveContext` and `result.state` to `state`.
  7. Return `result`.

Update Term Map Algorithm

This algorithm takes maps `state`, `activeTermMap`, and map or array `contexts` as well as booleans `typeScope` and `propertyScope`, both of which default to `false` if not provided, as inputs. It returns maps `state` and `activeTermMap`.

  1. If `contexts` is not an array, set `contexts` to be an array with the previous value of `contexts` as its sole element.
  2. Set `allowProtectedOverride` to the value of `propertyScope`.
  3. Set `propagateDefault` to the negation of the value of `typeScope`.
  4. For `contextIdentifier` in `contexts`:
    1. Set `loadResult` to the result of , passing `state` and `contextIdentifier`.
    2. Set `entry` to `loadResult`.`entry`, `context` to `entry`.`context`, and `state` to `loadResult`.`state`.
    3. If `@propagate` appears in `context`, set `propagate` to the value of `@propagate` in `context`. Otherwise, set `propagate` to the value of `propagateDefault`.
    4. Set `newTermMap` to be an empty map. For [`key`, `value`] in `entry`.`termMap`:
      1. Shallow copy the contents of `value` into a new map `newValue` and add `propagate` to `newValue`.
      2. Set the value of `key` in `newTermMap` to `newValue`.
    5. For [`term`, `activeDef`] in `activeTermMap`:
      1. Let `def` be the value of `term` in `newTermMap`.
      2. If `def` is defined:
        1. If the value of `protected` in `activeDef` is `true`:
          1. If `allowProtectedOverride` is set to `false` and `def` is not identical to `activeDef`, throw an error ERR_PROTECTED_TERM_REDEFINITION.
          2. Otherwise, set the value of `term` in `newTermMap` to a map containing the values from `activeDef` and `propagate` set to the value of `def`.`propagate`.
      3. Otherwise, if `term` appears in `context`, set the value of `term` in `newTermMap` to a map containing all values from `activeDef`.
    6. Set the value of `activeTermMap` to the value of `newTermMap`.
  5. Set `result` to be an empty map.
  6. Set `result`.`state` to `state` and `result`.`activeTermMap` to `activeTermMap`.
  7. Return `result`.

Revert Term Map Algorithm

This algorithm takes as input a map `activeContext`, and returns a map `newTermMap`.

  1. Set `newTermMap` to an empty map.
  2. Set `nonPropagatingTerms` to an empty array.
  3. For `[term, def]` in `activeContext`:
    1. If `def.propagate` is set to `false`, add `term` to `nonPropagatingTerms` and proceed to the next iteration of this loop.
    2. Otherwise, set the value of `term` in `newTermMap` to `def`.
  4. For `term` in `nonPropagatingTerms`:
    1. Set `currentContext` to `activeContext.previousActiveContext`.
    2. Set `def` to the value of `term` in `currentContext.termMap`.
    3. While `def` is not undefined and `def.propagate` is set to `false`:
      1. Set `currentContext` to `activeContext.previousActiveContext`.
      2. Set `def` to the value of `term` in `currentContext.termMap`.
    4. If `def` is not undefined, set the value of `term` in `newTermMap` to `def`.
  5. Return `newTermMap`.

Context Loading

The algorithms in this section define how to construct the mappings between terms and integers that are used as the core CBOR-LD compression technique.

Initialize Context Loader Algorithm

This algorithm takes and returns a map `state`.

  1. Set `state.contextMap` to a new map.
  2. Set `state.nextTermId` to 100.
  3. Set `state.keywordsMap` to the following map of JSON-LD keywords to their associated integer values: 
    {
  '@context' => 0,
  '@type' => 2,
  '@id' => 4,
  '@value' => 6,
  '@direction' => 8,
  '@graph' => 10,
  '@included' => 12,
  '@index' => 14,
  '@json' => 16,
  '@language' => 18,
  '@list' => 20,
  '@nest' => 22,
  '@reverse' => 24,
  '@base' => 26,
  '@container' => 28,
  '@default' => 30,
  '@embed' => 32,
  '@explicit' => 34,
  '@none' => 36,
  '@omitDefault' => 38,
  '@prefix' => 40,
  '@preserve' => 42,
  '@protected' => 44,
  '@requireAll' => 46,
  '@set' => 48,
  '@version' => 50,
  '@vocab' => 52,
  '@propagate' => 54
}
  4. Add each entry in `state.keywordsMap` to `state.termToId`.
  5. If `state.strategy` is set to "decompression", set `state.idToTerm` to the reverse map of `state.termToId` (i.e., a map from integers to JSON-LD keywords).
  6. Return `state`.

Load Context Algorithm

This algorithm takes a map `state` and a context map or URL `contextIdentifier`, and returns `result`, a map containing maps `state` and `entry`.

  1. If `state.contextMap` has an entry for `contextIdentifier`:
    1. Initialize `result` to an empty map.
    2. Set `result.state` to `state`.
    3. Set `result.entry` to the value of `contextIdentifier` in `state.contextMap`.
    4. Return `result`.
  2. If `context` is a string:
    1. Fetch the associated context object and set `context` to the value of "@context" in that object.
    2. Set `contextUrl` to the value of `contextIdentifier`.
  3. Otherwise, set `context` to `contextIdentifier`.
  4. Set `result` to the result of , passing `state`, `context`, and `contextUrl` if set.
  5. Return `result`.

Add Context Algorithm

This algorithm takes a map `state`, a context object `context`, and a context URL `contextUrl`, and returns `result`, a map containing maps `state` and `entry`.

  1. If `context` has an entry "@import":
    1. Set `importUrl` to the value of "@import" in `context.
    2. If `state.contextMap` does not have an entry for `importUrl`:
      1. Fetch the context object associated with `importUrl` and set `importContext` to the value of "@context" in that object.
      2. Set `importedContextAdditionResult` to the result of , passing `state`, `importContext` as `context`, and `importUrl` as `contextUrl`.
      3. Set `state` to `importedContextAdditionResult.state` and `importEntry` to `importedContextAdditionResult.entry`.
    3. Otherwise, set `importEntry` to the value of `importUrl` in `state.contextMap`.
    4. Set `context` to a map containing all entries from `context` as well as `importEntry.context`.
  2. Set `termMap` to an empty map.
  3. Set `entry` to be an object containing `context` and `termMap`.
  4. Set `sortedTerms` to the result of sorting the keys in `context` in lexicographic order.
  5. Set `isProtected` to `true` if "@protected" has an entry in `context` and `false` otherwise.
  6. For `term` in `sortedTerms`:
    1. If `term` has an entry in `state.keywordsMap`, proceed to the next iteration of this loop.
    2. Set `definition` to the value of `term` in `context`.
    3. If `definition` is `null`, proceed to the next iteration of this loop.
    4. If `definition` is a string:
      1. Set `newDefinition` to an empty map.
      2. Set the value of "@id" in `newDefinition` to `definition`.
      3. Set the value of `definition` to `newDefinition`.
    5. Set the value of `protected` in `definition` to `isProtected`.
    6. Set the value of `term` in `termMap` to `definition`.
    7. If `term` does not have an entry in `state.termToId`:
      1. Set `termId` to `state.nextTermId`.
      2. Increment `state.nextTermId` by 2.
      3. Set the value of `term` in `state.termToId` to `termId`.
      4. Set the value of `termId` in `state.idToTerm` to `term`.
  7. If `contextUrl` is defined, set the value of `contextUrl` in `state.contextMap` to `entry`.
  8. Otherwise, set the value of `context` in `state.contextMap` to `entry`.
  9. Set `result` to be an empty map.
  10. Set `result.state` to `state` and `result.entry` to `entry`.
  11. Return `result`.

Codecs

The codecs in this section specify exactly how individual values in JSON-LD should be converted to CBOR and vice versa. They are used by the algorithms in the previous section, and allow CBOR-LD to efficiently encode both primitive and non-primitive types as CBOR.

Context Codec

Create Context Encoder

This algorithm takes a map `typeTable` and a value `contextValue` and returns a map `encoderData`.

  1. Initialize `encoderData` to an empty map.
  2. If `contextValue` is not a string, return.
  3. Otherwise, set `contextTable` to the value of "context" in `typeTable`.
  4. Set `encoderData.context` to `contextValue` and `encoderData.contextTable` to `contextTable`.
  5. Return `encoderData`.

Encode Context

This algorithm takes a map `encoderData`, and returns CBOR binary data.

  1. If `encoderData`.`context` has an entry in `encoderData`.`contextTable`, return a CBOR encoding of the value of `encoderData`.`context` in `encoderData` as a Major Type 0 (unsigned integer) object.
  2. Otherwise, return a CBOR encoding of the value of `encoderData`.`context` as a Major Type 3 (text string) object.

Create Context Decoder

This algorithm takes a map `reverseTypeTable`, and returns a map `encoderData`.

  1. Set `reverseContextTable` to the value of "context" in `reverseTypeTable`.
  2. Initialize `decoderData` to an empty map.
  3. Set `decoderData`.`reverseContextTable` to the value of `reverseContextTable` and return `decoderData`.

Decode Context

This algorithm takes a map `decoderData` and a value `value`, and returns a value.

  1. If `value` is not a number, return `value`.
  2. Otherwise, if `decoderData`.`reverseContextTable` has an entry for `value`, return the value of that entry.
  3. Otherwise, throw an error ERR_UNDEFINED_COMPRESSED_CONTEXT.

Value Codec

Create Value Encoder

This algorithm takes maps `state` and `termInfo`, and values `termType` and `valueToEncode`, and returns a map `encoderData` or `valueToEncode`.

  1. Set `isUrl` to `false`.
  2. If `termInfo.term` is "@id" or "@type", set `isUrl` to `true`.
  3. If the value of "@id" in `termInfo.def` is "@id" or "@type", set `isUrl` to true.
  4. If `termType` is "@id" or "@vocab", set `isUrl` to `true`.
  5. If `isUrl` is `true`, set `tableType` to "url".
  6. Otherwise, if `termType` is defined, set `tableType` to `termType`.
  7. Otherwise, set `tableType` to "none".
  8. If `state.typeTable` has an entry for `tableType`:
    1. Set `subTable` to the value of `tableType` in `state.typeTable`.
    2. If `subTable` has an entry for `valueToEncode`:
      1. Set `intValue` to the value of `valueToEncode` in `subTable`. Set `includeSign` to `false`.
      2. If `state`.`typesEncodedAsBytes` has an entry for `tableType`, set `convertToBytes` to `true`. Otherwise, set `convertToBytes` to `false`.
    3. Otherwise, if `tableType` is not "none" and `valueToEncode` is an integer:
      1. Set `intValue` to the value of `valueToEncode`.
      2. Set `convertToBytes` and `includeSign` to `true`.
    4. If `intValue` is defined:
      1. Initialize `encoderData` to an empty map.
      2. Set `encoderData`.`intValue` to the value of `intValue`, `encoderData`.`convertToBytes` to the value of `convertToBytes`, and `encoderData`.`includeSign` to the value of `includeSign`.
      3. Return `encoderData`.
  9. If `tableType` has an entry in `state.processingModeTypeEncoders`, set `encoderData` to the result of calling the `Create Encoder` algorithm associated with that entry's codec.
  10. If `encoderData` is defined, return `encoderData`.
  11. Return `valueToEncode`.

Encode Value

This algorithm takes a map `encoderData`, and returns CBOR binary data.

  1. If `encoderData`.`convertToBytes` is `true`:
    1. Set `bytes` to the result of converting `intValue` to bytes, using the value of `includeSign` to determine whether the binary representation of the integer should be signed or unsigned.
    2. Return a CBOR encoding of `bytes` as a Major Type 2 (byte string) object.
  2. Otherwise, return a CBOR encoding of `intValue` as a Major Type 0 (unsigned integer) object.

Create Value Decoder

This algorithm takes maps `state` and `termInfo`, and values `termType` and `valueToDecode`, and returns a map `decoderData`.

  1. Set `isUrl` to `false`.
  2. If `termInfo.term` is "@id" or "@type", set `isUrl` to `true`.
  3. If the value of "@id" in `termInfo.def` is "@id" or "@type", set `isUrl` to `true`.
  4. If `termType` is "@id" or "@vocab", set `isUrl` to `true`.
  5. If `isUrl` is `true`, set `tableType` to "url".
  6. Otherwise, if `termType` is defined, set `tableType` to `termType`.
  7. Otherwise, set `tableType` to "none".
  8. If `state.reverseTypeTable` has an entry for `tableType`:
    1. Set `subTable` to the value of `tableType` in `state.reverseTypeTable`.
    2. Set `useTable` to `false`.
    3. If `valueToDecode` is a byte array and `state`.`typesEncodedAsBytes` has an entry for `tableType`:
      1. Set `useTable` to `true`.
      2. Set `intValue` to the unsigned integer conversion of the `valueToDecode` bytes.
    4. Otherwise, if `valueToDecode` is an integer and `state`.`typesEncodedAsBytes` does not have an entry for `tableType`:
      1. Set `useTable` to `true`.
      2. Set `intValue` to `valueToDecode`.
    5. If `useTable` is `true`:
      1. If `intValue` is not in `subTable`, throw an error ERR_UNKNOWN_COMPRESSED_VALUE.
      2. Otherwise, set `decoded` to the value of `intValue` in `subTable`.
    6. Otherwise, if `valueToDecode` is a byte array and `tableType` is not "none", set `decoded` to the integer conversion of `valueToDecode`.
    7. If `decoded` is defined, initialize `decoderData` to an empty map, set `decoderData`.`decoded` to the value of `decoded`, and return `decoderData`.
  9. If `tableType` has an entry in `state.processingModeTypeDecoders`, set `DecoderData` to the result of calling the `Create Decoder` algorithm associated with that entry's codec.
  10. If `decoderData` is defined, return `decoderData`.
  11. Otherwise, if `valueToDecode` is not an array, initialize `decoderData` to an empty map, set `decoderData`.`decoded` to `valueToDecode`, and return `decoderData`.

Decode Value

This algorithm takes a map `decoderData`, and returns a value.

  1. Return `decoderData`.`decoded`.

CBOR Tag Processing

Get CBOR Tag Structure Algorithm

This algorithm takes as input an integer `registryEntryId`, and returns a byte string `prefix`.
  1. Set `registryEntryBytes` to the CBOR encoding of `registryEntryID`
  2. Set `prefix` to the result of appending `registryEntryBytes` to the end of the bytestring `0xD9CB1D82`.
  3. Return `prefix`.

Get Registry Entry ID Algorithm

This algorithm takes an encoded CBOR-LD payload `cborldBytes` as input, and returns `suffix`, the main data to be decoded, as well as the `registryEntryId` value that should be used to decompress `suffix`.

  1. If the CBOR tag on `cborldbytes` is not `0xCB1D` (tag value 51997), throw an `ERR_NON_CBOR_LD_TAG` error.
  2. If the tagged item is not an array of two elements where the first is a CBOR integer, throw an `ERR_INVALID_PAYLOAD_STRUCTURE` error.
  3. Set the value of `registryEntryId` to the value of the integer at index 0 of the tagged array.
  4. Set the value of `suffix` to the value of the second element of the array.
  5. Set `result` to be an empty map.
  6. Set `result`.`suffix` to the value of `suffix` and `result`.`registryEntryId` to the value of `registryEntryId`.
  7. Return `result`.

IANA Considerations

CBOR Tag

This specification registers a CBOR tag to allow consumers to identify CBOR-LD payloads. The following is provisional, and has not yet been ratified by IANA.

Tag: 51997

Registry: https://www.iana.org/assignments/cbor-tags/cbor-tags.xhtml

Data item: array

Semantics: a tag value of 51997 indicates that the payload is CBOR-LD.

Description of semantics: https://w3c.github.io/cbor-ld/#cbor-tags-for-cbor-ld

Point of contact: Wesley Smith (wsmith@digitalbazaar.com)