# Star Pattern Fragments: Accessing Knowledge Graphs through Star Patterns

### Tracking #: 2472-3686

Authors:
Christian Aebeloe
Ilkcan Keles
Gabriela Montoya
Katja Hose

Responsible editor:
Guest Editors Web of Data 2020

Submission type:
Full Paper
Abstract:
SPARQL endpoints offer access to a vast amount of interlinked information. While they offer a well-defined interface for efficiently retrieving results for complex SPARQL queries, complex query loads can easily overload or crash endpoints as all the computational load of answering the queries resides entirely with the server hosting the endpoint. Recently proposed interfaces, such as Triple Pattern Fragments, have therefore shifted some of the query processing load from the server to the client at the expense of increased network traffic in the case of non-selective triple patterns. This paper therefore proposes Star Pattern Fragments (SPF), an RDF interface enabling a better load balancing between server and client by decomposing SPARQL queries into star-shaped subqueries, evaluating them on the server side. Experiments using synthetic data (WatDiv), as well as real data (DBpedia), show that SPF does not only significantly reduce network traffic, it is also up to two orders of magnitude faster than the state-of-the-art interfaces under high query load.
Tags:
Reviewed

Decision/Status:
Major Revision

Solicited Reviews:
Click to Expand/Collapse
Review #1
By Olaf Hartig submitted on 05/Jul/2020
 Suggestion: Minor Revision Review Comment: This manuscript studies a new type of Web interface to access and to query RDF data. By doing so, it provides a timely and interesting contribution to a line of research in the community with the goal to identify alternatives to the SPARQL endpoint interface. The particular new type of interface that this manuscript introduces is called the Star Pattern Fragments (SPF) interface. Conceptually, this type of interface is an extension of the Bindings-Restricted Triple Pattern Fragments (brTPF) interface. Instead of enabling clients to combine only a single triple pattern with a set of solution mappings, the innovative extension of the SPF interface is to allow for multiple triple patterns that form a star pattern. By a comprehensive set of experiments, the authors show that client-server query execution processes with their new interface outperform corresponding brTPF-based processes in terms of reduced network traffic and increased query throughput. Additionally, the experiments nicely show the various properties of the authors' approach (including a good explanation of the observations). Hence, in summary, the idea of the SPF interface is original and novel, and the manuscript shows that this interface presents a significant advancement of the state of the art. In addition to the originality and the significance of the results in the manuscript, another strength of the manuscript is that it is very well written. More specifically, the work is well motivated in Section 1; Section 2 gives a good overview of the state of the art and of the relationship to the work presented in the manuscript. Sections 4 and 5 provide an excellent description of the approach; that is, the high-level ideas, formal definitions, and all necessary details are presented in an easy-to-understand manner. Similarly, the description of the experiments is excellent and should serve as an example for many other papers in the community. The only issue that should be addressed is the following problem related to the notion of a "subject-based star decomposition" (Def.12): There are BGPs for which multiple such decompositions exist, which has several consequences. First of all, Def.12 cannot be formulated as if there is always only one such decomposition (i.e., do not write "the ...decomposition" but "a ...decomposition"). Second, the manuscript has to detail how exactly the authors decompose a given BGP into a subject-based star decomposition (I assume some form of a greedy algorithm that aims to maximize the size of the star patterns). Another issue is that the experiments do not consider SaGe, which is another state-of-the-art approach that has also been shown to outperform brTPF-based client-server systems. While I think that the presented work is already sufficiently comprehensive and a comparison to SaGe may be deferred to future work, I would like the manuscript to be more explicit about this limitation. A few additional minor issues that are easy to fix: * Algorithm 1, line 10: instead of $tp_j \in S_B$, it should be $S_j \in S_B$ * Algorithm 1, line 12: the subscript of the big union operator needs to include: \in \phi^\epsilon * Algorithm 1, lines 15+16 should be removed because the execution of lines 2+3 in the recursion makes them redundant * line 28 in the right column of page 10: It should be StarPatternIterator (rather than TriplePatternIterator) * Please extend the "Hardware Setup" paragraph in Sec.6.1 with a sentence about the network connection between the VM and the server. * Footnote 12: be explicit about what exactly the "large number" was
Review #2
Anonymous submitted on 20/Jul/2020