Ever since the Web was introduced to access representations of resources via URLs, Web developers have been coming up with ways to make available more specific HTTP responses via more complex URL patterns. Complex URL patterns with features such as the SPARQL query language, GraphQL, OGC Web Feature Services, or free text queries, also come with limitations: i) you can only query the data integrated on the machine you query, ii) coding against a fixed protocol lowers potential evolvability, iii) relying on dynamic server functionality raises challenges in long-term preservation, and iv) sending the full query to a third party server lowers query privacy. Linked Data Fragments puts forward the idea that there is a false dichotomy between solving the full query on the server of the data publisher and solving it fully on the infrastructure of the consumers: when publishing data in fragments of triples in a dataset with a certain locality into an interlinked resource-structure, data consumers can speed up their own query processing. In this paper, we build evolvable and preservable Web APIs using “materializable interfaces” with the TREE hypermedia specification. For use cases such as route planning, full-text search, geospatial look-ups or replication and synchronization, we show how to build a fragmentation by qualifying the relation from one fragment to another. This way, the TREE hypermedia specification helps to overcome the four drawbacks of URL-based query protocols. The specification will be further developed as part of a W3C community group for which we are now seeking support.
Fragments
The Web is a global information system that makes representations of resources addressable using URLs. While the most visible use case to end-users is using URLs to address websites and their pages in their browser, developers also use exactly the same technique in what they call Web APIs to share data between user agents. Just like a website, not all content or data that is managed through one server is exposed via only one resource. Instead, a Web API is a resource structure that exposes one or more views over the collection of data.
Depending on how tightly coupled the user-agent application and the Web API are, designing https://pietercolpaert.be/#me (P. Colpaert) © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). the resource structure of the Web API becomes more or less straightforward. I.e. if there is only one app that needs the data the API exposes, and both are controlled by the same developer, the resource structure can be driven by exactly the user stories of the app itself. However, if an unknown number of potential systems need to be able to reuse the data, such as it is the case when designing APIs for Open Data publishing, or resource structures within the Solid project1, it becomes guess-work on what API will work best.
The Linked Data Fragments (LDF) axis [
against a purpose-built protocol lowers the potential evolvability of that API. Turning of this API in favour of a diferent specific Web API with ad-hoc resources built based on a specific language will require applications to be recoded towards that novel specification. 4. It leaks query privacy Sending the full query to a third party server shares the full questions your users are interested in to that server.
These two extremes are positioned as a false dichotomy by LDF. If the user agent and the initial server can take up more responsibility in the query processing, then more options come to exist. A dataset that is too big for one page can be fragmented according to a certain property in the data, and therefore, by documenting the property, can help the user agent in pruning what fragments it needs to download in order to answer a certain query.
The idea is further extended by Linked Data Event Streams (LDES) [
Server 2
In this paper, we look into making these event sources and derived Web APIs evolvable and preservable, and mitigate the four limitations mentioned above. Even when a service or dataset is decommissioned, user agents that were once built on top of it, will still be able to resolve queries against archived data. In Section 3, we sketch our first steps into designing the TREE specification for guiding user agents through a fragmented dataset. In Section 4, we then show using a couple of examples how to build what we will call materializable Web APIs. Finally, in the Section 5, we reiterate the limitations and discuss how these materializable Web APIs tackle them.
Hartig et al. looked into Link Traversal Query Processing by following the HTTP identifiers it
encounters in the triples of Linked Data documents [
Hydra [
Another specification that includes hypermedia controls as part of a broaded protocols is
Activity Streams 2.07. This specification does allow to indicate pages are ordered, yet the
description of the ordering itself is left out of scope. Linked Data Platform (LDP) 8 is a World
Wide Web (W3C) specification that in an extension also puts forward a paging specification 9.
Despite its conflicts with Hydra and Activity Streams 2.0 [
In order to enable clients to prune their search space based on hypermedia descriptions
beyond simple pagination, we need to come up with a comprehensible specification, as well as
describe the client-side algorithm. An early attempt at making a client detect automatically how
to navigate further through a list or things in an ordinal range was with the multidimensional
interface specification [
In contrast to the state of the art, we want the specification to describe precisely how the index works, so any client-side query algorithm can benefit without a human developer having to explain how to interpret the responses.
We introduce the TREE hypermedia specification to fragment a collection of members in more interesting ways than only simple pagination. It allows to qualify relations from the current tree:Node—a page or fragment that can be requested using HTTP GET—to multiple other pages, similar to search trees. The description allows for a user agent to understand that, when following the link, all members of the collection from that page on will respect a certain condition, such as the fact that the name contains a certain prefix, a value from a literal will be greater or less than a certain value, or is contained in a certain geospatial area. The full specification can be found in the TREE specification 10. A concise overview of the specification is depicted in treespec.
The core collection design is largely inspired by and in line with Hydra. An instance of a tree:Collection links using the tree:member to the entities it contains.
As a collection will grow too large for one page, a predicate needs to indicate the current page is a subset of the collection, and only one way through which the collection can be viewed. When all members starting from this tree:Node can be found, the property tree:view can be used, meaning this node can be a starting point for viewing all members of the collection. Otherwise, if not all members can be found from that tree:Node, but if this node also contains a subset of the members in the collection, the property void:subset can be used. 7https://www.w3.org/TR/activitystreams-core/ 8https://www.w3.org/TR/ldp/ 9https://www.w3.org/TR/ldp-paging/ 10https://w3id.org/tree/specification tree:ViewDescription
ldes:EventSource n tree:relation
«tree:Relation» tree:Collection tree:view void:subset tree:member
The members
dcat:servesDataset tree:viewDescription tree:Node 1
Your domain model tree:shape sh:Shape tree:remainingItems → X tree:path → SHACL property path tree:value → “...” tree:node → link
A tree:Collection is a subclass of a dcat:Dataset. The specialization being that it adheres to this collection design. When a tree:Collection is an ever-growing append-only collection of immutable members, it must be typed using the subclass ldes:EventStream. A tree:Collection, and its subclasses, should define what their members look like using a SHACL shape11. This SHACL shape may prove useful when selecting datasets from a DCAT catalog, also called dataset discovery.
However, when there are multiple views defined, a tree:ViewDescription can be defined, which is a subclass of a dcat:DataService. The specialization being that it describes a Web API on top of a tree:Collection, publishing all members. If the intention of the view is to publish the event source, the sublass ldes:EventSource can be used as a type. The type only says something about the intention of the server administrator, and can still contain any kind of structure. Through the tree:ViewDescription, a user agent can select the right view for the task it has at hand, also called view discovery.
The last point in discovery is interface discovery to discover the next links to follow from within the view itself. This is explored in the next subsection on traversing the hypermedia structure.
We always write TREE with all caps to indicate we take inspiration from traversing search trees, but we cannot guarantee, and do not limit the TREE hypermedia specification to designing search trees. Even however we would limit it to search trees, counting on the fact that server would not provide you circular references would be incredibly naive. Therefore, a TREE user agent must always keep a history of nodes it already traversed, and prune these nodes from its yet-to-be-visited queue. Visited nodes may be added again to the queue if the user agent implements a cache invalidation strategy.
The tree:Node describing the current page is linked with the property tree:relation to an entity that is an instance of a subclass of a tree:Relation. For example, for string search, we have defined the type tree:SubstringRelation. A tree:value property on top of that relation defines the value to be used in a comparison function defined by the relation, to compare the needs of the user agent with the intention of the relation. The tree:path describes the property path (using the Shapes Constraints Language (SHACL) Property Paths specification 12) to be resolved starting from a member, on which this tree:value applies. Mind that a certain tree:Node can occur multiple times across relations, and that this must be interpretted as a logical AND. A code example of a relation can be found in TREE-code-sample.
Given the list of nodes linked from the pages a user agent already visited, minus these nodes it already visited, it can prune that list further based on the constraints given to the task at hand (e.g., find all members starting with labels starting with the letters Ghent).
Listing 1: A Turtle example of an ex:ThisPage that links to a ex:NextPage through a GreaterThanRelation. A client can assume it must follow the page if its task needs members with a sosa:simpleResult greater than 5.1234, to be compared using the double datatype. ex:C a tree:Collection ;
tree:view ex:ThisPage . ex:ThisPage a tree:Node ;
tree:relation ex:Relation1 . ex:Relation1 a tree:GreaterThanRelation ; tree:node ex:NextPage ; tree:value "5.1234"^^xsd:double ; tree:path (sosa:simpleResult) . 12https://www.w3.org/TR/shacl/#x2.3.1-shacl-property-paths
Server 2
The TREE specification allows publishers to construct their own materializable hypermedia interfaces. We define a materializable interface as an interface that has a finite set of URLs that provide an answer. That way, the interface can be published using a simple file host, but is also very eficient to be hosted through a content delivery network, even if the server itself is built in a dynamic way in which each GET request on a URL potentially triggers a script to be executed.
The strategies in which a dataset can be fragmented is infinite, similar to the amount of indexes one can make on top of a relational database. One method of thinking about a fragmentation strategy, is to only fragment a dataset from the moment a dataset becomes too large for one page. The way in which a second page will be added can then be decided based on the needs in the ecosystem. As illustrated in multiple-views-2, the first priority should be to build the relation to the second page based on how the dataset is growing. That way, that fragmentation can be eficiently used for populating other Web APIs on top of that dataset. However, when the event source is available, we can optionally support more functionality on top of the dataset
The use cases we worked with included querying for geospatial relations, time schedules of
public transit data, OpenStreetMap’s road network and taxonomies with text literals such as
an address database, geonames, OpenStreetMap names or Wikidata entities. These cases have
been published in their respective papers, for which we provide a concise overview below (as
of January 2023). These use cases describe their search space tree:Relation objects.
1. Replicating and synchronizing dataset copies across organizations A one
dimensional pagination of an ever-growing collection of immutable events has interesting
caching properties. Only one page remains to be polled, while all other pages are historic
and can be flagged with the cache-control: immutable response header. In [
can be modeled as a temporal directed acyclic graph departures and arrivals. With Linked
Connections [
planning use case [11] illustrates the need for querying with a more open world while retaining query privacy. By geospatially fragmenting a road network (such as OpenStreetMap), we can select data with a geospatial locality, and/or public transit with a time and geospatial locality. The public transit data also needs a road network to potentially calculate walks to transfer from one public transit stop to another, and maybe that transfer needs to happen according to the potential constraints of the end-user, whether they are pushing a stroller, in a wheelchair, trained athletes, or visually impaired. However, the profile of user does not need to be leaked to a server in order for the route planning result to be calculated.
completion [12]: the locality is now not based on geospatial or time-based literals, but on the basis of substring matches with a string literal. Similar benefits can be found.
All these interfaces can be kept in-sync thanks to the event source, but also need to be able to describe how they are derived from which sources. The result of a workflow over semantically describe streams can already be described [13, 14] by combining LDES, DCAT, SHACL, PROV-O and P-Plan.
In this paper, although it was already used in previous academic work, we introduced the TREE hypermedia specification for building materializable interfaces. We chose the term materializable as it does not need to be materialized on disk, but it can be as there is only a finite set of HTTP requests that give a result. Hosting a materializable interface should be possible with almost neglectible hosting costs. The largest costs should come from the computational power needed to create and update a page from an interface.
This turns the four limitations of more complex query patterns in the introduction into the advantages of materializable interfaces: 1. You can query your end-user’s world Materializable interfaces assume user agents take part in the query evaluation. That way, it can execute the queries by taking into account data that lives on the user agent’s infrastructure, with access to datasets the end-user has access to. Take for example the use case of route planning: it can take into account their home address, the fact their bike is parked in a certain location, the fact they are in a wheelchair, etc. Personalization can happen without having to build a profile on a remote server. 2. It becomes possible to archive an interface, not just the data When a server is being decomissioned, an archiving project can traverse the hypermedia links until it replicated all pages to an archive server, and keep the files available and discoverable. That way, even after a server or even publisher disappeared, clients that relied on a certain fragmentation for their functionality can keep on working.
discoverability could be coded against, that wil come with more evolvability. One idea is to have the start fragment of the specific Web API hardcoded. That way, if the structure of the hypermedia changes, it will always start again from the root of the search space. A higher level of evolvability can be achieved when not the URL of the Web API is hardcoded, but the ones of the dataset and a data catalog. That way, through the data catalog, all Web APIs can be discovered that publish the dataset. If one Web API is decommissioned, the user agent can fall back to another Web API publishing the same data. An even higher level of discovery could yet again be achieved by also implementing discovery on the dataset level, to, through the SHACL shape documented with the tree:Collection, and the provenance information attached to it, select these sources that will return an answer to a question. 4. Queries can be kept private The only thing a server sees is that a client is interested in a page of its dataset. It does not see how the query is executed and what the final recommendation or query result provided to the user is. This in stark contrast with Web APIs with URL patterns like https://your-domain/weather?long,lat that would be polled for weather information.
The current version of the TREE vocabulary has been submitted to LOV [15]. In order to further evolve the specification, we are now starting a TREE/LDES community group at W3C for which we are now seeking support.
The last information on the TREE hypermedia project can be found at https://tree.
linkeddatafragments.org. In future work, we are also going to tackle graph-based and time
series fragmentations with the TREE/LDES method. Furthermore, the Comunica Querying
engine [
This work has been support by SolidLab Vlaanderen (Flemish Government, EWI and RRF project V023/10) and the Flemish Smart Data Space (Flemish Government, Digital Flanders and RRF project VV073). The vision on materializable hypermedia interfaces is a result of working with the entire Knowledge on Web-Scale team at Ghent University. public transport data on the web with the linked connections framework, Semantic Web (2022). [11] H. Delva, J. A. Rojas Melendez, B. Abelshausen, P. Colpaert, R. Verborgh, Client-side route planning: preprocessing the openstreetmap road network for routable tiles, in: Academic Track, State of the Map 2019, 2019, pp. 23–24. [12] R. Dedecker, H. Delva, P. Colpaert, R. Verborgh, A file-based linked data fragments approach to prefix search, in: International Conference on Web Engineering, Springer, 2021, pp. 53–67. [13] A. Vercruysse, S. Min Oo, P. Colpaert, Describing a network of live datasets with the sds vocabulary, in: MEPDaW2022, Managing the Evolution and Preservation of the Data Web, 2022, pp. 1–6. [14] C. Guasch, G. Lodi, S. V. Dooren, Semantic knowledge graphs for distributed data spaces: The public procurement pilot experience, in: International Semantic Web Conference, Springer, 2022, pp. 753–769. [15] P.-Y. Vandenbussche, G. A. Atemezing, M. Poveda-Villalón, B. Vatant, Linked Open Vocabularies (LOV): a gateway to reusable semantic vocabularies on the Web, Semantic Web 8 (2017) 437–452.