A Foundation for Comparing Linked Data Fragment Interfaces

The Linked Data Fragments (LDF) conceptual framework is an attempt to address the realization in the Semantic Web community that SPARQL endpoints (i.e., Web services that execute any given SPARQL over an internal RDF dataset) are perhaps not the ultimate solution to provide public query access to datasets on the Web. The trouble with these endpoints is that they may be easily overloaded when trying to answer any given SPARQL query, in particular when these queries are complex or multiple clients issue queries concurrently. The main idea of the LDF framework is to consider other types of query-based data access interfaces that are more restricted in the types of queries they support and, thus, impose that the effort for executing more complex queries is shifted to the clients. The initial example of such an interface has been the Triple Pattern Fragment (TPF) interface that limits the server-side effort to the evaluation of triple patterns only (i.e., the simplest type of patterns that SPARQL queries are built of); any other operation needed for a given query has to be performed by a client-side query execution algorithm that is based on obtaining triple pattern results from a TPF server. Several such algorithms have been proposed in the literature, and so have a number of other types of LDF interfaces. Each such proposal aims to hit a sweet spot of trade-offs along multiple dimensions such as server-side load, query throughput, network load, etc.

While the experimental evaluations in the various LDF-related research papers have provided us with a comprehensive elementary understanding of the existing proposals and their respective trade-offs, I strongly believe there is many more interesting work to be done regarding LDFs.

However, you know what I always thought would be great to have in this context? Since the beginning of the LDF work, I was looking for a way that allows us to achieve a more fundamental understanding of possible LDF interfaces, including interfaces that have not yet been implemented! In particular, I was after a formal framework that allows us to organize LDF interfaces into some kind of a lattice, or perhaps multiple lattices, based on the fundamental trade-offs that the interfaces entail. Such lattices would not only provide us with a more complete picture of how different interfaces compare to each other, they would also be a basis for making more informed decisions about whether it is worth to spend the time implementing and studying a possible interface experimentally.

As you likely have guessed by now, such a formal framework is not just an idea anymore. Together with Jorge Pérez and Ian Letter at the Universidad de Chile, we have developed an abstract machine model for which we have shown that it is a suitable foundation for the type of formal framework described above. From a computer science point of view, the most exciting part of this work is that our abstract machine model presents a basis for defining new complexity measures that allow us to capture many more aspects of computation in a client-server setting than what is captured by the classical measure of computational complexity. We will present this work next week at the 16th International Semantic Web Conference (ISWC). If you are interested in reading about our machine model and how we applied it to study various existing types of LDF interfaces, refer to our research paper about it (and, yes, we have actual lattices in that paper 😉

Leave a Reply

Your email address will not be published. Required fields are marked *