The TREE hypermedia specification

Living Standard,

This version:
https://w3id.org/tree/specification
Issue Tracking:
GitHub
Editor:
Pieter Colpaert

Abstract

The TREE specification enables API developers to define relations between HTTP resources. A collection of items can be fragmented, and these fragments can be interlinked. It is an alternative to one-dimensional HTTP pagination. Instead of linking to the next or previous page, the relation describes what elements can be found by following the link to another page. Multiple links can be specified, enabling parallelization when traversing the search space.

1. Collections

The TREE specification introduces these core concepts:

2. Core Concepts

The root node from which all members of a collection can be discovered through the predicate tree:view. The object of the tree:view triple will contain a root node from which all elements in the collection can be retrieved.

When the current page is a tree:Node, there MUST be a property linking the current page URL to the URI of the tree:Collection. Three properties may be used:

  1. <collection> tree:view <currentPageUrl> .
    May be used only in the case when the entire tree:Collection can be found starting from the current node.

  2. <collection> void:subset <currentPageUrl> .
    When the node is not a root node, but still a subset of the collection.

  3. <currentPageUrl> dcterms:isPartOf <collection> .
    The reverse property of 2.

2.1. Multiple Collections

When multiple collections are found by a client, it can choose to prune the collections based on the tree:shape property. Therefore a data publisher SHOULD annotate a tree:Collection instance with a SHACL shape. The tree:shape points to a SHACL description of the shape (sh:NodeShape).

Note: the shape can be a blank node, or a named node on which you should follow your nose when it is defined at a different HTTP URL.

2.2. Multiple views

Multiple views MAY be provided, and a TREE client MUST traverse all objects of tree:view linked to this particular collection. Every entity linked from tree:view MUST be an entry point to retrieve all members of the collection.

Note: How a client picks the right view is use-case specific. In order to fetch all members, one can be chosen at random. In order to prioritize a specific view, the relations and search forms in the root nodes can be studied for their relation types, path or remaining items.

2.3. Compatibility

2.3.1. DCAT

[VOCAB-DCAT-2] is the standard for Open Data Portals by W3C. In order to find TREE compliant datasets in data portals, there SHOULD be a dcat:accessURL from the dcat:Distribution to the entrypoint where the tree:Collections are described. Furthermore, there SHOULD be a dct:conformsTo this URI: https://w3id.org/tree.

2.3.2. Hydra

A tree:Collection is compatible with the Hydra Collections specification. However, instead of hydra:view, we use tree:view and do not link to a hydra:PartialCollectionView but to a tree:Node. A hydra:Collection can thus also be extended with a tree:shape and tree:view. When this is done, also hydra:member can be used instead of tree:member.

hydra:totalItems can be used to indicate the total amount of elements in the collection.

Hydra paging controls such as hydra:nextand hydra:previousare semantically equivalent to a tree:Relation element that only contains a tree:node property. These do not provide any additional information to a client traversing a collection; the discovered node retains the value constraints from the current node.

2.3.3. Activity Streams 2.0

A tree:Collection is also compatible with [activitystreams-core]’s specification of paged collections. Instead of dcterms:isPartOf, also as:partOf can be used to indicate that the current page is part of the full collection. While Hydra and TREE link to the members of the collection by using the specific collection as a subject, Activity Streams 2.0 (AS) indicates a member starting from the page URL. Therefore, when using AS collections, a client implementation should gather the members from the tree:Node or as:CollectionPage instead.

as:totalItems can be used to indicate the total amount of elements in the collection.

AS paging controls such as as:nextand as:previous are semantically equivalent to a tree:Relation element that only contains a tree:node property. These do not add provide any additional information to a client traversing a collection; the discovered node retains the value constraints from the current node.

2.3.4. LDP Containers

Another relevant spec is [LDP]. There, the tree:view can be applied on top of the ldp:Container instance. Members can be found through ldp:contains, and/or through the indirect ldp:membershipResource and ldp:hasMemberRelation or ldp:isMemberOfRelation construct.

If this container is paged by the [ldp-paging] (chapter 7) spec, then this MUST be ignored.

If there is an ordering, this MUST be ignored by TREE clients (the relations contain all necessary information for pruning).

2.3.5. Shape trees

The Shape Trees specification is specifically built to work within existing ecosystems. As it was conceived to interoperate with LDP, the term Container in the Shape Trees spec can also be interpreted as a tree:Collection. Shape Trees can help in the source selection of what specific tree:Collection to pick for your goal, and may add hierarchies to a set of tree:Collections. A client MAY infer a tree:shape of the collection through the st:validatedBy property of the Shapes Tree.

An example of a collection using Shape Tree terms. In this example a sensor with some observations is validated by using a Shape Expressions (ShEx) file.

@prefix sosa: <http://www.w3.org/ns/sosa/> .
@prefix om: <http://www.ontology-of-units-of-measure.org/resource/om-2/> .
@prefix ldp: <http://www.w3.org/ns/ldp#> .

<2021.ttl#Collection> a ldp:Container; 
    st:validatedBy <Sensor.shex#Sensor>;
    tree:member <sensor1>, <sensor2> .

<sensor1>
    a sosa:Sensor;
    sosa:madeObservation
        <sensor1-observation1>,
        <sensor1-observation2>;
    sosa:observes om:Temperature .

<sensor1-observation1>
    a sosa:Observation;
    sosa:observedProperty om:Temperature;
    sosa:madeBySensor <sensor1>;
    sosa:hasResult <result1>;
    sosa:resultTime "2020-08-25T07:05:31Z"^^xsd:dateTime .

<result1> a om:Measure; 
    om:hasValue "22"^^xsd:float; 
    om:hasUnit om:degreeCelsius .

<sensor1-observation2>
    a sosa:Observation;
    sosa:observedProperty om:Temperature;
    sosa:madeBySensor <sensor1>;
    sosa:hasResult <result2>;
    sosa:resultTime "2020-08-25T07:05:32Z"^^xsd:dateTime .

<result2> a om:Measure; 
    om:hasValue "22"^^xsd:float; 
    om:hasUnit om:degreeCelsius .

<sensor2>
    a sosa:Sensor;
    sosa:observes om:Temperature .

And its corresponding ShEx file (called Sensor.shex)

PREFIX sosa: <http://www.w3.org/ns/sosa/>
PREFIX xsd: <http://www.w3.org/2001/XMLSchema#>
PREFIX om: <http://www.ontology-of-units-of-measure.org/resource/om-2/>
PREFIX rdfs: <http://www.w3.org/2000/01/rdf-schema#>

<#Sensor> {
    a [sosa:Sensor] ;
    sosa:observes [om:Temperature]  ; 
    sosa:madeObservation @<#TemperatureObservation> * 
}

<#TemperatureObservation> {
    a [sosa:Observation] ;
    sosa:resultTime xsd:dateTime ;
    sosa:madeBySensor @<#Sensor> ? ;
    sosa:observedProperty [om:Temperature];
    sosa:hasResult @<#TemperatureResult> 
}

<#TemperatureResult> { 
    a [om:Measure];
    om:hasValue xsd:float ;
    om:hasUnit [om:degreeCelsius]
}

3. Relations

3.1. Traversing relations

A tree:Node element MAY have one or more tree:relation properties. A relation is an entity of the type tree:Relation, and MAY have a more specific type. A tree:Relation MUST have one tree:node object of the type tree:Node. By default, all nodes need to be followed, unless the client is able to select this relation for pruning (see next section).

The tree:Relation’s tree:value SHOULD be set. The object of tree:value SHOULD be accompanied by a data type when it is a literal value.

Every tree:Relation SHOULD have a tree:path, indicating the path from the member to the object on which the tree:Relation applies. For the different ways to express or handle a tree:path, we refer to 2.3.1 in the shacl specification. All possible combinations of e.g., shacl:alternativePath, shacl:inversePath or shacl:inLanguage in the SHACL spec can be used. When shacl:alternativePath is used, the order in the list will define the importance of the order when evaluating the tree:Relation. A wildcard in the path is limited to the tree:shape of the tree:Collection. The result of the evaluation of the tree:path, is the value that must be compared to the tree:value.

Every tree:Relation MAY provide a tree:remainingItems. A client MAY use tree:remainingItems to estimate the completeness of the downloaded elements to the end-user.

Note: When traversing, a client SHOULD keep a list of already visited pages, as despite this being the TREE spec, circular references and back-links are not explicitly prohibited.

A tree:import MAY be defined in the tree:Relation instance. When there is a tree:path defined, and when the relation is flagged interesting to follow, the import link needs to be downloaded in order to find the necessary literals to be compared (it is thus already a tree:ConditionalImport.

Note: An example of a tree:import is given in the repository.

3.2. Fallbacks

When there are no tree:members and/or no tree:Collection defined, then the tree:path refers to a pattern that can start from every triple in the page.

Note: This may enable server developers to indicate an index on all literals of the members (e.g., a prefix relation on title, description and body text) without having to indicate all of the alternative paths in the tree:path.

When no tree:path is defined, the tree:value MUST be compared to all members’ triples that can be compared to the tree:value as defined by the type of the relation (or when no members or collection are defined, on every triple in the page). When due to rdfs:range incompatibility, the object cannot be compared, the object will not be considered for comparison.

When there is no tree:shape given, then this collection may contain any kind of triple and can not be automatically pruned in the source selection. This may however still be useful in triple-based collections.

Note: Not having a tree:member nor tree:path may also be useful for triple-based indexes such as Triple Pattern Fragments. In order to support metadata about the triples itself, something like RDF* would otherwise be needed, or a triple indicating whether we should look at the page as a “page of triples” or a “page of members”.

The target object SHOULD be materialized in the current Node document, but when it is not, the object MAY be considered implicit on the condition both tree:path and tree:member are defined. In contrast to shacl:path, a tree:path MAY refer to an implicit property and may not materialized in the current response. This may break SPARQL processors that did not yet come across the object before in their query plan. However, the tree may still be useful for query processors that, for example, prioritize queries according to the user’s location, and first download nodes that are nearby the user. Therefore, the materialized location of the object is not needed. While not recommended, possible heuristics could try to infer the data, could try to fetch it through another tree:Collection, or retrieve it using URI dereferencing.

3.3. Specific relations

When the only type given for a certain Relation is tree:Relation, then the client must dereference all of the nodes. While this may seem useless, it can be used for the same use case as a hydra:PartialCollectionView.

For other types check the chapter on relation types in the vocabulary § 6.1.3 tree:Relation.

3.3.1. Comparing strings

String values have three specific type of relations: the tree:PrefixRelation, the tree:SubstringRelation and the tree:SuffixRelation.

Note: We experimented with server-chosen locales such that ça suffit can also be found when following a tree:PrefixRelation with a tree:value "c" (which at this moment is not supported). That would require an understanding of locales, and browser/JavaScript support for locales is too low to be useful at this point.

Also the comparator relations such as tree:GreaterThanRelation can be used. The strings MUST then be compared according to case sensitive unicode ordering.

When a tree:path is defined, mind that you also may have to check the language of the element using the property shacl:inLanguage More languages MAY be set. When no language is set, all strings are compared.

Note: If you want to have one resource containing both e and é as a prefix, you will have to create multiple relations to the same tree:Node.

3.3.2. Comparing geospatial features

The tree:GeospatiallyContainsRelation is the relation than can be used to express all further members will be contained within a geospatial region defined by the WKT String in the tree:value.

When using tree:GeospatiallyContainsRelation, the tree:path MUST refer to a literal containing a WKT string, such as geosparql:asWKT.

3.3.3. Comparing time literals

When using relations such as tree:LessThanRelation or tree:GreaterThanRelation, the time literals need to be compared according to these 3 possible data types: xsd:date, xsd:dateTime or xsd:dateTimeStamp.

4. Searching through the collection

Searching through a TREE will allow you to immediately jump to the right tree:Node. TREE relies on the Hydra search specification for its search forms. It does however extend Hydra with specific search properties (hydra:IriTemplate) for different types of search forms, and searches starting from a tree:Node, to which the search form is linked with tree:search. The behaviour of the search form fully depends on the specific property, for which TREE introduces a couple of specific properties:

4.1. Geospatial XYZ tiles search form

Three properties allow to specify a geospatial XYZ tiles template (also known as slippy maps).

  1. tree:longitudeTile describes the X value

  2. tree:latitudeTile descrbes the Y value

  3. tree:zoom describes the zoom level

All properties expect positive integers.

{
   "@context": {
     "viewOf" : {
       "@reverse": "tree:view",
       "@type": "@id"
     },
     ...
   },
  "viewOf": {
    "@id": "https://tiles.openplanner.team/planet/",
    "@type": "tree:Collection",
    "dcterms:license": "http://opendatacommons.org/licenses/odbl/1-0/",
    "dcterms:rights": "http://www.openstreetmap.org/copyright",
    "tree:member": [ ..., ... ]
  },
  "tree:search": {
    "@type": "hydra:IriTemplate",
    "hydra:template": "https://tiles.openplanner.team/planet/{z}/{x}/{y}",
    "hydra:variableRepresentation": "hydra:BasicRepresentation",
    "hydra:mapping": [
      {
        "@type": "hydra:IriTemplateMapping",
        "hydra:variable": "x",
        "hydra:property": "tree:longitudeTile",
        "hydra:required": true
      },
      {
        "@type": "hydra:IriTemplateMapping",
        "hydra:variable": "y",
        "hydra:property": "tree:latitudeTile",
        "hydra:required": true
      },
      {
        "@type": "hydra:IriTemplateMapping",
        "hydra:variable": "z",
        "hydra:property": "tree:zoom",
        "hydra:required": true
      }
    ]
  }
}

This search form describes a specific search form that uses a quad tree. The zoom level describes the depth, the longitudeTile and latitudeTile describe the x and y index of the fragmentation. (e.g., on zoom level 0, there’s 1 tile, on zoom level 1, there are 4 tiles, etc.).

4.2. Searching through a list of objects ordered by time

Same as the previous example but with the predicate tree:timeQuery expecting an xsd:dateTime. This time however, when the page itself does not exist, a redirect is doing to happen to the page containing the timestamp. A tree:path can indicate the time predicate which is intended.

{
   "@context": {
     ...
   },
  "dcterms:isPartOf": {
    "@id": "#coll",
    "@type": "tree:Collection",
    "tree:member": [ ..., ... ]
  },
  "tree:search": {
    "@type": "hydra:IriTemplate",
    "hydra:template": "https://example.org/{t}",
    "hydra:variableRepresentation": "hydra:BasicRepresentation",
    "hydra:mapping": [
      {
        "@type": "hydra:IriTemplateMapping",
        "hydra:variable": "t",
        "tree:path": "prov:generatedAtTime",
        "hydra:property": "tree:timeQuery",
        "hydra:required": true
      }
    ]
  }
}

5. Imports

A tree:import can be defined on multiple levels. When defined as part of a tree:Node, this document always needs to be fetched when processing this Node. When defined as part of the tree:Relation, one MUST fetch the import when the relation needs to be correctly evaluated (e.g., the resulting page contains elements without materialized WKT strings, which however can be fetched from the import). When importing a file, no hypermedia relations will be followed from that import in order to get more data.

A tree:importStream can also be defined for providing a pubsub interface for subscribing to real-time updates. The object SHOULD be a [websockets] or Server-Sent Events ([eventsource]).

Instead of tree:import, one can also use tree:conditionalImport which links to an object of the type tree:ConditionalImport with these properties:

Note: imports are powerful to keep recurring objects in a separate, more cacheable, resource.

No hypermedia controls in the body MUST be interpreted in the imported resource and the object must be fully contained within that information resource.

On the resources to import, Memento [RFC7089] controls MAY be provided for historic versions.

6. Vocabulary

Namespace: https://w3id.org/tree#

Prefixes:

@prefix tree: <https://w3id.org/tree#>.
@prefix hydra: <http://www.w3.org/ns/hydra/core#>.
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>.
@prefix sh: <http://www.w3.org/ns/shacl#> .
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .

6.1. Classes

6.1.1. tree:Collection

A collection has members that may adhere to a certain shape.

6.1.2. tree:Node

A tree:Node is a node that may contain links to other dereferenceable resources that lead to a full overview of a tree:Collection.

6.1.3. tree:Relation

An entity that describes a relation between two tree:Nodes.

The tree:Relation has specific sub-classes that implement a more specific type between the values. These types are described in the ontology (all classes are rdf:subClassOf tree:Relation):

6.1.4. tree:ConditionalImport

A class to import a file or a stream based on a tree:path of properties. This way it can import the necessary data for complying to the SHACL shape, or evaluating a relation type.

6.2. Properties

6.2.1. tree:relation

Links a node to a relation

Domain: tree:Node

Range: tree:Relation

6.2.2. tree:remainingItems

Remaining number of items of this node, the items in its children included.

Domain: tree:Node

Range: xsd:integer

6.2.3. tree:node

The URL to be derefenced when this relation cannot be pruned.

Domain: tree:Relation

Range: tree:Node

6.2.4. tree:value

The contextual value of this node: may contain e.g., a WKT-string with the bound of a rectangle, may contain a string, an integer, or even link to another resource where clear comparison rules apply.

Domain: tree:Relation

6.2.5. tree:path

A property path, as defined by SHACL, that indicates what resource the tree:value affects.

See § 3 Relations

Domain: tree:Relation

6.2.6. tree:view

Links the collection to a tree:Node from which all members can be found. If only a part of the collection’s members can be found from that point on, only use dcterms:isPartOf or void:subset.

Domain: tree:Collection

Range: tree:Node

Links a tree:Node to a hydra:IriTemplate. The search form will search the remaining items of the node.

Domain: tree:Node

Range: hydra:IriTemplate

6.2.8. tree:shape

The SHACL shape the members of the collection adhere to.

Domain: tree:Collection

Range: sh:NodeShape

6.2.9. tree:member

Links to the collection’s items that are the sh:targetNodes of the SHACL shape defined with tree:shape.

Domain: tree:Collection

6.2.10. tree:import

Imports a document containing triples needed for complying to the SHACL shape, or for evaluating the relation.

6.2.11. tree:conditionalImport

Imports a document only when the client is interesting in a specific tree:path.

6.2.12. tree:zoom

A search form parameter: the zoom level of the tile cfr. OSM convention.

As defined by Slippy Map Tilenames in OpenStreetMap

6.2.13. tree:longitudeTile

A search form parameter: the X tile number from longitude cfr. OSM convention.

As defined by Slippy Map Tilenames in OpenStreetMap

6.2.14. tree:latitudeTile

A search form parameter: the Y tile number from latitude cfr. OSM convention.

As defined by Slippy Map Tilenames in OpenStreetMap

6.2.15. tree:timeQuery

A search form parameter: accompagnied by a tree:path, it indicates the property on which a time search can be done

Conformance

Conformance requirements are expressed with a combination of descriptive assertions and RFC 2119 terminology. The key words “MUST”, “MUST NOT”, “REQUIRED”, “SHALL”, “SHALL NOT”, “SHOULD”, “SHOULD NOT”, “RECOMMENDED”, “MAY”, and “OPTIONAL” in the normative parts of this document are to be interpreted as described in RFC 2119. However, for readability, these words do not appear in all uppercase letters in this specification.

All of the text of this specification is normative except sections explicitly marked as non-normative, examples, and notes. [RFC2119]

Examples in this specification are introduced with the words “for example” or are set apart from the normative text with class="example", like this:

This is an example of an informative example.

Informative notes begin with the word “Note” and are set apart from the normative text with class="note", like this:

Note, this is an informative note.

References

Normative References

[ACTIVITYSTREAMS-CORE]
James Snell; Evan Prodromou. Activity Streams 2.0. 23 May 2017. REC. URL: https://www.w3.org/TR/activitystreams-core/
[EVENTSOURCE]
Ian Hickson. Server-Sent Events. 28 January 2021. REC. URL: https://www.w3.org/TR/eventsource/
[LDP]
Steve Speicher; John Arwe; Ashok Malhotra. Linked Data Platform 1.0. 26 February 2015. REC. URL: https://www.w3.org/TR/ldp/
[LDP-PAGING]
Steve Speicher; John Arwe; Ashok Malhotra. Linked Data Platform Paging 1.0. 30 June 2015. NOTE. URL: https://www.w3.org/TR/ldp-paging/
[RFC2119]
S. Bradner. Key words for use in RFCs to Indicate Requirement Levels. March 1997. Best Current Practice. URL: https://tools.ietf.org/html/rfc2119
[RFC7089]
H. Van de Sompel; M. Nelson; R. Sanderson. HTTP Framework for Time-Based Access to Resource States -- Memento. December 2013. Informational. URL: https://datatracker.ietf.org/doc/html/rfc7089
[SHACL]
Holger Knublauch; Dimitris Kontokostas. Shapes Constraint Language (SHACL). 20 July 2017. REC. URL: https://www.w3.org/TR/shacl/
[VOCAB-DCAT-2]
Riccardo Albertoni; et al. Data Catalog Vocabulary (DCAT) - Version 2. 4 February 2020. REC. URL: https://www.w3.org/TR/vocab-dcat-2/
[WEBSOCKETS]
Ian Hickson. The WebSocket API. 28 January 2021. NOTE. URL: https://www.w3.org/TR/websockets/