Many Linked Data datasets model elements in their domains in the form of lists: a countable number of ordered resources. When publishing these lists in RDF, an important concern is making them easy to consume. Therefore, a well-known recommendation is to find an existing list modelling solution, and reuse it. However, a specific domain model can be implemented in different ways and vocabularies may provide alternative solutions. In this paper, we argue that a wrong decision could have a significant impact in terms of performance and, ultimately, the availability of the data. We take the case of RDF Lists and make the hypothesis that the efficiency of retrieving sequential linked data depends primarily on how they are modelled (triple-store invariance hypothesis). To demonstrate this, we survey different solutions for modelling sequences in RDF, and propose a pragmatic approach for assessing their impact on data availability. Finally, we derive good (and bad) practices on how to publish lists as linked open data. By doing this, we sketch the foundations of an empirical, task-oriented methodology for benchmarking linked data modelling solutions.
When publishing Linked Open Data a major concern is to make the data
understandable and easy to consume [
A pragmatic solution is referring to each member of the list with RDF
containment membership properties (rdf:_1, rdf:_2,. . . ) within a n-ary relation
of type rdf:Seq. Another, alternative option, may involve picking a solution
from the Ontology Design Patterns catalogue [
In this work we survey methods for modelling sequences in RDF, and
propose a pragmatic approach for assessing their performance in typical SPARQL
queries and triplestores. The objective is to discuss the various modelling
practices and provide recommendations to developers in understanding the trade-offs
in encoding lists in a large-scale Linked Open Dataset. To do this, we develop
and use a benchmark of datasets and queries [
availability of sequential retrieval of Linked Data? – (2) Can we identify patterns enabling the publishing of RDF lists in a sus
tainable way? Crucially, we intend to evaluate the following hypothesis: The efficiency of retrieving lists of linked data depends primarily on how they are structured. Without ad-hoc optimisations, the impact of modelling solutions on data availability is independent of the database engine (triple-store invariance hypothesis)4
Specifically, we contribute: (1) A survey of modelling practices for representing RDF lists in the Linked Data world. (2) A set of paradigmatic structural
4 We are aware that one way to solve these problems is to optimize a database engine to support a specific RDF model. Here, we propose to evaluate existing engines pragmatically, and find evidence to eventually justify the development of such optimizations. design patterns for representing sequences, derived from the survey. (3) Extensive experiments aimed at evaluating the competing modelling solutions in terms of scalability for data retrieval, focusing on a set of basic requirements.
The rest of the paper is structured as follows. After scoping our contribution in the context of related work, we introduce the research methodology in Section 3. We discuss reference scenarios and express generic, task-based requirements for RDF lists in Section 4. Section 5 reports on our survey and presents a set of reference structural design patterns. These are then formalised in SPARQL to match the requirements, in Section 6. Section 7 reports on the experiments. Results are discussed in Section 8, that concludes our paper. 2
We consider research in two overlapping areas with our work: modeling of sequential RDF data; and performance of querying over such data using benchmark queries and datasets.
The Resource Description Framework (RDF) specification [
We focus on practical approaches that assess querying sequential RDF data;
for a theoretical study on the complexity of SPARQL, see [
the DBpedia SPARQL benchmark [
We can identify three open issues: (1) To the best of our knowledge, none
of these benchmarks assess querying RDF data with sequential information, e.g.
rdf:List or rdf:Seq. In our work, we propose data and queries to evaluate
RDF sequences specifically, thus addressing a new benchmark task. (2) Among
the variety of solutions for modelling sequences, the rdf:List method appears to
be the "official" one, being part of the RDFS specification and also recommended
as a good design pattern in a Linked Data Pattern book [
In this section we describe a methodology specifically designed to pragmatically evaluating the performance of competing modeling solutions for Linked Data publishing. Phases of the methodology are: requirements, survey, formalisation, and evaluation, that we illustrate.
Requirements In the initial phase, we identify the model that is the object of
study. (In our case, it is the well-known data structure list, a finite collection
of ordered elements.) However, in order to evaluate the performance of a
concrete implementation of the model we need to identify a set of core functional
requirements. Requirements should be formulated as competency questions [
Survey Modelling solutions should be relevant to practitioners, by referring to
at least 1 concrete dataset adopting the modelling practice. Ideally, we want to ensure they are a complete set of solutions and that there is no relevant approach left out. After listing the modelling solutions, they should be abstracted in structural patterns and ensure these patterns are minimal with relation to the data model.
Formalisation Each modelling solution should be encoded in RDF and in
SPARQL. Particularly, each pattern must be challenged to fit the competency
questions designed in the initial phase, and respective solutions encoded in
SPARQL queries. By doing this it is fundamental to ensure that the output
is semantically equivalent, ideally the exact same, for all query variants. In
addition, it is fundamental that queries are minimal by keeping them in the simplest
form, for example adopting good practices for SPARQL query optimization [
Evaluation The objective of this phase is to empirically evaluate the different solutions. Being the Linked Data standing on a Web application architecture (the client/server approach), the performance measure we focus on is overall response time. In order for results to be relevant to real applications, response time must be measured at different scale with respect to the data size. To do that, it is suggested to generate a set of realistic datasets at different scales. Experiments are performed for each modelling prototype with different dataset sizes and, crucially, with different database engines. From the results, derive recommendations on how to better represent the given model in Linked Data. 4
We derive reference scenarios from Linked Open Data implementing sequences in various relevant domains. These are: Author lists. The order of authors of scientific publications is relevant in several research areas, and may reflect the contribution of each author in a quantitative way. It is important to know which is the first author, for example, or to display them in the right order.
Album tracks. Tracks are ordered sequentially in a music album. Users may choose to play the 3rd or 7th song in the list.
Recipes. Recipes are lists of actions that should be executed in order.
MIDI LD. A MIDI object encoded in Linked Data is a sequence of encoded audio
events [
From the above scenarios, we identify three necessary and sufficient requirements: (a) the capability of obtaining the list as an ordered sequence of items. 7 In fact, blank nodes don’t require the matching node value to be kept in memory as part of the query solution to be projected. This list does not need to include additional data, the returning object can just be a list of strings; (b) the capability of obtaining an item at a certain position in the list; and (c) the capability of obtaining a ordered set of items with the scope of a specific range. From these considerations, we formulate the following competency questions: – CQ1 (All Ordered): What is the ordered content of the sequence? – CQ2 (Nth Lookup): Which is the n-th item in the sequence? – CQ3 (Ordered Range): What are the items from the N to M in the sequence? Clearly, other operations are possible and useful, for example checking the presence of an item in the list or comparing lists. Here we focus on atomic operations related to access list items by order, and leave a more complete requirement analysis as future work. In addition, we only consider lists with one item only in a certain position, although some models may support otherwise. 5
There are various models for representing a sequence, a finite collection of ordered
elements, in RDF. In this section we describe such models, argue abstractions
that integrate some of them, and discuss their properties. We conduct a
systematic survey of these models, by selecting them from the following sources:
W3C standards8 and recommendations; the ontology design patterns [
RDF Sequences The RDF Schema (RDFS) recommendation [
Properties. RDF Sequences indicate membership through various properties,
which are used in triples in predicate position. Ordering of elements is absolute
in such predicates through an integer index after an underscore (“_”).
RDF Lists The RDFS recommendation [
Properties. RDF Lists indicate membership using a unique property rdf:first in predicate position. Ordering of elements is relative to the use of the rdf:rest property, and given by the sequential forward traversal of the list.
URI-based Lists A more practical approach followed by many
RDF datasets [
Properties. URI-based lists indicate membership through the use of class membership or through properties. Order is absolute and given by URI-embedded sequential identifiers.
Number-based Lists Another practical model, used e.g. in the Sequence
Ontology/Molecular Sequence Ontology (MSO) [
Properties. Number-based lists indicate membership through the use of class membership or through properties. Order is absolute and given by an integer index in a literal as an object of an additional property.
Fig. 6: The Sequence Ontology Pattern
Fig. 5: Timestamp-based list model. model.
Timestamp-based Lists Similarly to Number-based lists, other lists
modeled by e.g. the Simple Event Model (SEM) [
Properties. Timestamp-based lists indicate membership through the use of class membership or through properties. Order is absolute and given by a timestamp in a literal as an object of an additional property.
Sequence Ontology Pattern A number of models use general
RDF/RDFS/OWL semantics to model sequences in domain specific ways. For example, the
Time Ontology [
Properties. SOP lists indicate list membership through properties. Order is relative and given by the sequential forward or backward traversal of the sequence. 12 http://motools.sourceforge.net/timeline/timeline.html\# 13 http://ontologydesignpatterns.org/wiki/Submissions:Sequence
In this phase we aim at formally represent each solution in RDF/SPARQL in
order to answer the requirements. We consider that in competency questions
CQ1 and CQ3, we aim at returning a list of URIs representing ordered set of
items, while we aim at returning a single item for CQ2. Particularly, we report on
how each way of representing a MIDI Linked Data event sequence can be queried
in SPARQL. Therefore, we use the vocabularies of the List.MID benchmark
datasets, developed following our methodology [
BIND ( xsd : i n t e g e r (SUBSTR( s t r (? seq ) , 4 5 ) ) AS ? index ) } ORDER BY ? index In principle, the Nth Lookup (CQ2) could be resolved by replacing the ?seq variable with the property _N (for example, rdf:_995 for the 995th element of the list). However, containers are meant to be open-ended. The specification does not declare that the predicate number represents anything other than the order of the elements in the rdf:Seq. Therefore, it would be unsafe to assume that the range of rdf:_5 to be the item in fifth position. The minimal and safe approach would be to operate on the sequence at query time: WHERE { : l i s t a midi : Track ; midi : hasEvents [ ? seq ? event ] .
BIND ( xsd : i n t e g e r (SUBSTR( s t r (? seq ) , 4 5 ) ) AS ? index ) } ORDER BY ? index OFFSET 995 LIMIT 1 A similar approach can be adopted to select an ordered range (CQ3). RDF Lists (List). This modelling solution requires to be queried with a property path in order to traverse the list from the root to the tree to the last item. However, there is no guarantee that the projections of the ?event variable would keep the sequence order. In order to derive the index from the data, we need to perform aggregation and ordering, as follows: SELECT ? event ( count (? s t e p ) as ? index ) WHERE { : l i s t a midi : Track ; midi : hasEvents ? e vent s . ? even ts r d f : r e s t ? s t e p . ? s t e p r d f : r e s t ? e l t . ? e l t r d f : f i r s t ? event } GROUP BY ? event ORDER BY ? index In our benchmark, like in many of the use cases observed in our survey, entities are directly attached to the list. However, an entity can be shared among lists and therefore the list element itself may refer to it indirectly, for example with a pattern such as _:bnode123 rdf:first/rdf:value ?event, resulting in an expansion of the given query. CQ2 could be implemented by specifying a path of rdf:rest/rdf:first as long as the position of the item we want to retrieve. However, this would require to write a different query for each item and result in a large query string that could be possibly rejected by the Web server. Therefore, we keep the same query layout for CQ2 and CQ314.
URI-based lists (Uri). This practical approach is very economic and can be expressed as follows: WHERE { [ ] a midi : Track ; midi : hasEvent ? event .
BIND ( xsd : i n t e g e r (SUBSTR( s t r (? event ) , 7 7 ) ) AS ? id ) } ORDER BY ? i d This query can be expanded to include OFFSET and LIMIT clauses to satisfy CQ2 and CQ3.
Number-based Lists (Prop_number) and Timestamp-based Lists (Prop_time) This solution relies on a data value incorporating a numeric index. The main difference here is that an additional triple pattern needs to be employed, although the value is meant to be a number and can be passed as-is to the ORDER BY clause: WHERE { [ ] a midi : Track ; midi : hasEvent ? event .
? event midi : a b s o l u t e T i c k ? t i c k . } ORDER BY ? t i c k where ?tick is of datatype xsd:integer. Timestamp-based Lists are similar to Prop_number but with a time datatype. Additionally, they use a different approach as the numeric value is not necessary an incremental index and can also include multiple entities in the same position.
Sequence Ontology Pattern (SOP) The sequence ontology pattern uses the predicates precedes and follows to model the sequence. The query can be formulated combining two triple patterns. However, we need to combine this solution with an index-based on, for example, the Uri pattern, in order to ensure that the order is preserved in the output.
WHERE { [ ] a midi : Track ; midi : hasEvent ? event .
? event sequence : p r e c e d e s ? ? next_event . ? next_event sequence : f o l l o w s ? ? event .
BIND ( xsd : i n t e g e r (SUBSTR( s t r (? event ) , 7 7 ) ) AS ? id ) } ORDER BY ? i d We can conclude that all the modelling solution will need to rely on the SPARQL ORDER BY clause and that their main difference is in the way the index is represented in the data and in the necessary operations to serve it for sorting15. 14 Some triple stores supports the operator rdf:rest{n} targeting the n-th item in the path. However, this syntax, introduced during the development of SPARQL 1.1, was discarded in the final specification. 15 Although in some cases a system may return triples reflecting the order they had at insertion time, we cannot assume that triples are returned respecting any particular order. Therefore, the ORDER BY clause is necessary in all cases. In addition, although some of the models explored accept ties, i.e. lists with multiple items in the same position, these are not considered in this work. 7
Each model was mapped to a number of queries covering the three competency
questions listed in Section 4. We analysed the MIDI linked data endpoint for
deciding the size of the benchmark dataset: the List.MID benchmark [
We performed experiments with multiple triple stores. Each database was prepared by loading all the datasets in different named graphs. At runtime, the query was rewritten to target a specific named graph16.
Experiments are performed with the following databases and only considering the SPARQL RDF entailment regime: – Virtuoso Open Source V7, configured to expect 12G of free RAM, no additional rules enabled except the basic SPARQL 1.1. – Blazegraph 2.1.5, Java VM configured with 12G of max heap, without reasoning or inferencing support rather then the plain SPARQL 1.1 support. – Apache Fuseki v3 on TDB, Java VM with 12G of max heap. – Apache Fuseki v3 In Memory. This is the same system as the TDB-based but using a full in-memory setting, also with 12G of max heap space.
The client application performing the queries and measuring the response time resides on the same machine as the database. This is to avoid the impact of network bandwidth on the overall response time. It is worth reminding that the objective of the experiments is not the compare the various data management solutions but to compare the performance of the different modelling practices and their scalability with lists of growing sizes. Experiments are executed on a Linux VM with Intel(R) Xeon(R) CPU E5-2640 v4 @ 2.40GHz 8-core and 32G RAM. During the experiments, no other application was running on the instance rather then the experiment’s client process and the database server.
To summarise, the dimensions considered in our experiments are therefore: (a) Model (one of): Seq, List, Number Index, Time Index, ODP, URI Index (b) Dataset Size (one of): 1k, 30k, 60k, 90k, 120k (c) Query (one of): All, Lookup, Range (d) Database (one of): Virtuoso, Blazegraph, Fuseki-Tdb, Fuseki-Mem. 16 One may argue that the use of an index on the graph component may affect performance. However, whatever the impact of using the FROM clause is, it will be equally distributed in the various models.
In what follows we report on overall response time, meaning the amount of time the client had to wait before obtaining the complete answer. Each experiment was repeated 10 times, reported measures refer to average values. A timeout of 300 seconds has been set, although it was never reached. We also analysed standard deviation and in most cases the value was below 10% of the total time. The cases where it was higher relate to very fast response times (below the second) and are therefore not problematic. We can conclude that the reported averages are significant and represent well the response time of a client application querying lists of that form and size17.
Tables 1d-1l report the average values response time. Figures 7a-7l report
on scalability. The most inefficient method is the one relying on rdf:List, for
which most of the experiments timed out and a number of experiments with
Fuseki failed with a server error (probably due to excessively deep property
path in the query). The SOP method is also not very efficient. The performances
of the URI, prop_number, and prop_time methods are very similar, although
they behave slightly different with the various triple stores. All models scale
linearly with the amount of data (except for the failed experiments). Results
are coherent for all three CQs and demonstrate a clear trend among different
engines. Supplementary material is available for reproducibility [
The experiments demonstrate our hypothesis that the efficiency of retrieving sequential linked data depends heavily on how they are structured. Indeed, modelling practices have an impact in the performance and availability of sequential retrieval. Crucially, the behavior of the various models is consistent among different triple stores and allow us to distinguish design patterns that perform well in practice from others that perform worse —from the point of view of the identified CQs. The most efficient ways of representing order is by using indexes in values like in prop_number and prop_timestamp.Also indexes hidden in URIs perform well, both on the entity (subject/object) and on the rdf:Seq method (predicate). The reasons are probably related to database indexes on the basic triple patterns18 However, embedding the order semantics in string URIs does not seem an elegant solution. Using the rdf:Seq pattern may be a reasonable solution iff SPARQL engines would account of the special meaning of container membership properties and sort those predicate URIs accordingly. A small update to the SPARQL specification seems a reasonable solution. With the given 17 We also collected information about RAM usage and CPU. We could not observe particular differences in those, except in the case of Apache Fuseki on queries with multiple joins and property paths, mainly related to the SOP pattern. However, here we focus on the performance with respect to client applications and not on studying resource consumption on the server side. 18 Fuseki behaves a bit different and seems to badly tolerate many joins, generally. Also, on Fuseki URI processing is faster than picking indexes in values (number/date). However, here we focus on trends observed among the various database engines and do not discuss specific differences between them. Model 1k 30k 60k (a) Q1: Blazegraph (b) Q1: Virtuoso (c) Q1: Apache Fuseki (TDB)
(d) Q1: Apache Fuseki (In-Memory) (e) Q2: Blazegraph (f) Q2: Virtuoso (g) Q2: Apache Fuseki
(h) Q2: Apache Fuseki In-Memory (i) Q3: Blazegraph (j) Q3: Virtuoso (k) Q3: Apache Fuseki (l) Q3: Apache Fuseki In-Memory
Fig. 7: Performance scalability results, the methods relying on rdf:List (the recommended standard) and SOP (a high-quality ontology engineering solution ) clearly underperform in commonly used triplestores and, under this circumstances, their use should be discouraged for publishing lists as Linked Data.
However, in this paper we only measure query-ability of Linked Data leaving out other dimensions of analysis such as expressivity of the model at the logic level, compliance with high-level ontological requirements, and compliance to entailment regimes. Particularly, we do not consider data management operations such as adding or removing elements from a list. For those operations, solutions that do not store an index such as rdf:List or SOP would require less operations, possibly overturning the final judgement. However, these aspects are left to future work. With the aid of a task-based approach for benchmark development we were able to study pragmatically how to better publish sequential linked data and identified a fundamental problem of typical, recommended solutions. Intuitively, we can argue that there is a trade-off between incorporating an index in the data and allowing for easier and faster data management. We aim at expanding our experiments to also consider scenarios of Linked Data management and benchmark operations for list manipulations. Finally, we presented a preliminary work on model-centric and task-oriented benchmarks for Linked Data. The sketched methodology allowed us to identify design patterns that could negatively affect SPARQL endpoints availability using an approach that is independent from the concrete modelling problem. We aim at evaluating such methodology with more modelling scenarios, such as tabular structures, sets, or n-ary relations.