Sequential Linked Data: the State of Affairs

Tracking #: 2737-3951

Enrico Daga
Albert Meroño-Peñuela
Enrico Motta

Responsible editor: 
Guest Editors Web of Data 2020

Submission type: 
Full Paper
Sequences are among the most important data structures in computer science. In the Semantic Web, however, little attention has been given to Sequential Linked Data. In previous work, we have discussed the data models that Knowledge Graphs commonly use for representing sequences and showed how these models have an impact on query performance and that this impact is invariant to triplestore implementations. However, the specific list operations that the management of Sequential Linked Data requires beyond the simple retrieval of an entire list or a range of its elements --e.g. to add or remove elements from a list--, and their impact in the various list data models, remain unclear. Covering this knowledge gap would be a significant step towards the realization of a Semantic Web list Application Programming Interface (API) that standardizes list manipulation and generalizes beyond specific data models. In order to address these challenges towards the realization of such an API, we build on our previous work in understanding the effects of various sequential data models for Knowledge Graphs, extending our benchmark and proposing a set of read-write Semantic Web list operations in SPARQL, with insert, update and delete support. To do so, we identify five classic list-based computer science sequential data structures (linked list, double linked list, stack, queue, and array), from which we derive nine atomic read-write operations for Semantic Web lists. We propose a SPARQL implementation of these operations with five typical RDF data models and compare their performance by executing them against six increasing dataset sizes and four different triplestores. In light of our results, we discuss the feasibility of our devised API and reflect on the state of affairs of Sequential Linked Data.
Full PDF Version: 


Solicited Reviews:
Click to Expand/Collapse
Review #1
By David Chaves-Fraga submitted on 22/Feb/2021
Review Comment:

I am now happy with the last improvements of the paper and I would recommend accepting the paper for its publication

Review #2
By Johannes Frey submitted on 08/Mar/2021
Review Comment:

In the third version of the paper, the authors revised the queries w.r.t. the issues raised (minimality criterion) and subsequently updated the experiment and plots. In my opinion, the description of the scope of the paper and the research question are now much better to comprehend. Indeed with regard to Fig 6d/e, I missed the fact that fixed length property paths were removed from the final SPARQL 1.1 standard and only 3 of the 4 systems seem to support it. I understand the argument that expressing the property path in its full extent can lead to query parsing problems.
However, I still spotted an error in a query. I strongly recommend before submitting the camera ready, to follow my initial question/recommendation to verify the correctness of the operations across models and databases by comparing result sets and testing with integrity assertions where necessary (e.g. removal of one element should reduce the size of the list by one, and there should be no gaps/duplicate indices) part of the experiment setup. This should ensure that the queries are correct (self-evaluation), and the database delivers the results as expected.
Apart from a minor issue remaining in Formula 4, I have no additional comments.


Query does not remove old, unshifted list elements.

Formulas 4.x: the argument order for append seems wrong.

Moreover formula 4.3 still seems to have a problem, popoff maps to an element while append maps to a queue, so comparing an element with a queue would never be equal? append (v, popoff(..)) seems not defined because (E x E) does not match the signature of append.