The TREE hypermedia specification

1. Overview

An overview of the TREE specification with the TREE collection, a reference to the first focus node of its members, and the relations to other nodes from the current node.

The TREE specification introduces these core concepts:

a tree:Collection is a set of members. It typically has these properties when described in a node:
- tree:member points at the first focus node from which to retrieve and extract all quads of a member
- tree:view points to the tree:Node you are currently visiting
- tree:shape indicates the [SHACL] shape (exactly one) to which each member in the collection adheres
a tree:Node: is a page in the search tree
- tree:relation points at relations to other node
- a tree:search describes a search form that allows an agent to jump to a specific tree:Node in the (sub)tree from this node
- tree:viewDescription points to an entity with a reusable piece of information relevant to the full search tree. Multiple descriptions MUST be combined.
a tree:Relation is a relation from one node to another. An extension of this class indicates a specific type of relation (e.g., a tree:GreaterThanRelation). A relation typically has these properties:
- a tree:node the URL of the other node
- a tree:path indicating to which of the members' properties this relation applies
- a tree:value indicating a value constraint on the members' values
- a tree:remainingItems defining how many members can be reached when following this relation

A simple collection can be created as illustrated in the following example:

ex:Collection1 a tree:Collection;
            rdfs:label "A Collection of subjects"@en;
            tree:member ex:Subject1, ex:Subject2 .

ex:Subject1 a ex:Subject ;
            rdfs:label "Subject 1" ;
            ex:value 1 .

ex:Subject2 a ex:Subject ;
            rdfs:label "Subject 2" ;
            ex:value 2 .

From the moment this collection of members grows too large for one page, a pagination needs to be created in which an initial set of members can be found through the first tree:Node, and more members can be found by interpreting the TREE hypermedia controls. This is illustrated in the next example:

> HTTP GET https://example.org/Node1

ex:Collection1 a tree:Collection;
            tree:view ex:Node1 ;
            tree:member ex:Subject1, ex:Subject2 .

ex:Node1 a tree:Node ;
        tree:relation ex:R1,ex:R2 .

ex:R1 a tree:GreaterThanOrEqualToRelation ;
    tree:node ex:Node3 ; # This is the URL of another page
    tree:value 3;
    tree:path ex:value .

ex:R1 a tree:LessThanRelation ; # This is useful for a client that is looking for a value 10 or greater
    tree:node ex:Node3 ;
    tree:value 10;
    tree:remainingItems 7 ;
    tree:path ex:value .

ex:R2 a tree:GreaterThanOrEqualToRelation ;
    tree:node ex:Node4 ;
    tree:value 10;
    tree:remainingItems 10 ;
    tree:path ex:value .

ex:Subject1 a ex:Subject ;
            rdfs:label "Subject 1" ;
            ex:value 1 .

ex:Subject2 a ex:Subject ;
            rdfs:label "Subject 2" ;
            ex:value 2 .

2. Definitions

A tree:Collection is a set of tree:Members. The set of members MAY be empty.

A tree:Member is a set of (at least one) quad(s) defined by the member extraction algorithm (see further).

A tree:Node is a dereferenceable resource containing tree:Relations and a subset of (⊆) members of the collection. In a tree:Node, both the set of tree:Relations as the subset of members MAY be empty. The same member MAY be contained in multiple nodes.

A tree:Relation is a function denoting a conditional link to another tree:Node.

A tree:Node is part of a search tree, and apart from the root node, it has exactly one other tree:Node of the search tree linking into it through one or more relations.

A tree:search form is an IRI template, that when filled out with the right parameters becomes a tree:Node IRI, or when dereferenced will redirect to a tree:Node from which all members in the collection that adhere to the described comparator can be found.

A search tree is a set of interlinked tree:Nodes. It will adhere to a certain growth or tree balancing strategy. In one tree, completeness MUST be guaranteed, unless indicated otherwise using a retention policy (as is possible in LDES).

3. Initialization

A client SHOULD be initiated using a URL. The client MUST dereference the URL, which will result in a set of [rdf-concepts] triples or quads. When the URL after all redirects, is used in a triple ?c tree:view <> ., a client MUST assume the URL after redirects is an identifier of the intended root node of the collection in ?c.

Note: Dereferencing in this specification also means parsing the RDF triples or quads from the HTTP response. TREE does not limit the content-types that can be used to represent RDF triples. Client developers should do a best-effort for their community.

If there is no such triple, then the client MUST check whether the URL before redirects (E) has been used in a pattern <E> tree:view ?N. where there’s exactly one ?N, then the algorithm MUST return ?N as the rootnode and E as the collection.

The client then MUST dereference the identified rootnode (if it did not do that already) and merge those quads with the already found quads. It now MUST look for a potential search forms that MAY be linked, either i) on top of the rootnode, or ii) on top of the entity linked through tree:viewDescription, using tree:search.

In case it is not done using an unambiguous URL, clients MAY implement the report on Discovery and Context Information (work in progress). This report also explains how clients MAY implement support for extracting context information such as provenance, contact points, etc.

Note: Having an identifier for the collection has become mandatory: without it you can otherwise not define completeness.

4. The member extraction algorithm

The member extraction algorithm allows a data publisher to define their members in different ways:

As in the examples above: all quads with the object of the tree:member quads as a subject (and recursively the quads of their blank nodes) are by default included (see also [CBD]), except when they would explicitely not be included in case 3, when the shape would be closed.
Out of band / in band:
- when no quads of a member have been found, the member will be dereferenced. This allows to publish the member on a separate page.
- part of the member can be maintained elsewhere when a shape is defined (see 3)
By defining a more complex shape with tree:shape, also nested entities can be included in the member
By putting the triples in a named graph of the object of tree:member, all these triples will be matched.

Depending on the goals of the client, it MAY implement the member extraction algorithm to fetch all triples about the entity as intended by the server. The method used withun TREE is combination of Concise Bounded Descriptions [CBD], named graphs and the topology of a shape (deducted from the tree:shape). The full algorithm is specificied in the shape topologies report.

5. Traversing the search tree

After dereferencing a tree:Node, a client MUST extract all (zero or more) tree:Relation descriptions from the page. This can be done by searching for <> tree:relation ?R triples.

A client MUST follow the object of the relation’s ?R tree:node ?object triple, unless the client is able to prune the branch reachable from that node (see further).

A client MAY also extract the tree:Relation’s tree:remainingItems if it exists. If it does, it will be an integer indicating the remaining items to be found after dereferencing the node.

When traversing, a client SHOULD detect faulty search trees by keeping a list of already visited pages.

When dereferencing the object of a tree:node triple, the client MUST follow redirects.

Note: Allowing redirects allows servers to rebalance their search trees over time.

A client MAY assume completeness of members intended by the search tree when it derefenced all node links.

6. Pruning branches

In search trees, a tree:Relation will likely be typed using one of its subclasses. For partial string matching, tree:PrefixRelation, tree:SubstringRelation, and tree:SuffixRelation exist. For comparing various datatypes, tree:GreaterThanRelation, tree:GreaterThanOrEqualToRelation, tree:LessThanRelation, tree:LessThanOrEqualToRelation, tree:EqualToRelation, and tree:NotEqualToRelation exist. Finally, for geospatial trees, tree:GeospatiallyContainsRelation exists.

A client decides, based on their own tasks, what type of relations are important to implement. Each relation is a comparator function that helps deciding whether or not the subtree reachable from the tree:node link can be pruned. A relation can be interpreted as a comparator as follows:

The left-hand: what the members in the substree reachable from the linked node will contain w.r.t. the objects reachable from the tree:path.
The operator: decided by the type of the relation and the datatype or node type of the tree:value triple’s object.
The right-hand: the tree:value triple’s object.

The client MUST combine all relations to the same tree:node using a logical AND.

<> tree:relation [
      a tree:GreaterThanRelation ;
        tree:node ex:Node2 ;
        tree:path dct:created ;
        tree:value "2024-12-16T12:00:00Z"^^xsd:dateTime
  ],[
    a tree:SubstringRelation ;
    tree:node ex:Node2 ;
    tree:path dct:title ;
    tree:value "osa"
  ] .

In the example above the subtree reachable from ex:Node2 will contain all remaining members that are both created later in time than the given timestamp _and_ will have the provided substring in the title. The client MAY thus choose to prune all links to other nodes if this is the only thing it is interested in. The client SHOULD prune the subtree reachable from ex:Node if it is specifically not looking for members with the given substring, _or_ when it is not interested in members created later in time than the given timestamp. Alternatively, it MAY score the relation based on the likelihood of returning useful results and created a priority queue that is processed until a top K of results have been found.

Note: If the client comes across a relation subclass it did not code against or did not formulate a condition against, it can ignore this relation when assessing whether pruning is possible. I.e., in the example above, when the client is specifically not interested in members created later than the given creation time, but does not understand the SubstringRelation, the client MUST still prune the relation.

While each type of relation can decide on their own properties, relations will often use the tree:path to indicate 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., sh:alternativePath or sh:inversePath in the SHACL spec can be used. The resulting values of the evaluation of the tree:path, are the values that must be compared to the tree:value object. When multiple results from the path are found, they need to be interpreted as a logical OR: at least one of these values will fulfill the comparator.

A client, in case it wants to process relations that use the tree:path property, MUST implement a matching algorithm to check whether the relation is relevant. I.e., a tree:path on (rdfs:label [sh:alternativePath rdfs:comment ] ) will be useful when the client is tasked to filter on rdfs:comment.

Note: A server MAY link the tree:path to a property that is not materialized in the current response. For the client, if it also needs those triples, we assume in this spec that the client has another way of retrieving those, or already retrieved them from another source.

6.1. Comparing strings

String values have three specific type of relations: the tree:PrefixRelation, the tree:SubstringRelation and the tree:SuffixRelation. The string comparison happens using the unicode canonical equivalence.

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 using case sensitive unicode ordering.

When a language is set on the tree:value, the relation only refers to these language strings. If no language is indicated, it refers to all (including those without).

Particular to the tree:SubstringRelation, is that multiple tree:value properties can be set. This means the members properties will contain all of the given substrings.

We need a flag for setting case insensitiveness: what will we use? In previous implementations sh:flags "i" was used.

6.2. Comparing named nodes

When using comparator relations such as tree:GreaterThanRelation, named nodes MUST be compared as defined in the ORDER BY section of the SPARQL specification.

6.3. Comparing geospatial features

The tree:GeospatiallyContainsRelation is the relation that can be used to express all further members will be contained within a geospatial region defined by the WKT String in the tree:value. The client MUST consider the relation when it overlaps with the region of interest.

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

6.4. Comparing time literals

When using relations such as tree:LessThanRelation or tree:GreaterThanRelation, the time literals MUST to be compared according to these 3 possible data types: xsd:date, xsd:dateTime or xsd:dateTimeStamp. It is highly recommended to server developers to provide a timezone in the tree:value, which can be done in these datatypes themself.

When no timezone is specified, the comparison needs to take place on the worst-case bound. For example a date 2022-01-01 without timezone thus represents a period of time of 48 hours from ([) 2021-12-31T12:00:00Z until 2022-01-02T12:00:00Z ([).

7. Search forms

Searching through a TREE will allow you to immediately jump to the right tree:Node in a subtree. 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 specific 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:

7.1. Geospatial XYZ tiles search form

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

tree:longitudeTile describes the X value
tree:latitudeTile descrbes the Y value
tree:zoom describes the zoom level

All properties expect positive integers.

<https://tiles.openplanner.team/#LatestCollection> a tree:Collection ;
    dcterms:title "A prototype tree:Collection for Linked OpenStreetMap’s roads"@en .
<https://tiles.openplanner.team/planet/> a tree:Node ;
    
    tree:search [
        a hydra:IriTemplate ;
        hydra:template "https://tiles.openplanner.team/planet/20201103-095900/{z}/{x}/{y}" ;
        hydra:variableRepresentation hydra:BasicRepresentation ;
        hydra:mapping [
            a hydra:IriTemplateMapping ;
            hydra:variable "x";
            hydra:property tree:longitudeTile;
            hydra:required true
        ],[
            a hydra:IriTemplateMapping ;
            hydra:variable "y";
            hydra:property tree:latitudeTile;
            hydra:required true
        ],[
            a 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 pagination. (e.g., on zoom level 0, there’s 1 tile, on zoom level 1, there are 4 tiles, etc.).

7.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.

<https://example.org/#Collection> a tree:Collection ;
    dcterms:title "An example collection with a time search view"@en ;
    tree:view <https://example.org/Node1> .

<https://example.org/Node1> a tree:Node ;
    tree:search [
        a hydra:IriTemplate ;
        hydra:template "https://example.org/{generatedAt}" ;
        hydra:variableRepresentation hydra:BasicRepresentation ;
        hydra:mapping [
            a hydra:IriTemplateMapping ;
            hydra:variable "generatedAt";
            tree:path prov:generatedAtTime;
            hydra:property tree:timeQuery;
            hydra:required true
        ]
    ] .

The TREE hypermedia specification

Abstract

Status of this document