Over years, the Web of Data has grown significantly. Various interfaces such as SPARQL endpoints, data dumps, and Triple Pattern Fragments (TPF) have been proposed to provide access to this data. Studies show that many of the SPARQL endpoints have availability issues. The data dumps do not provide live querying capabilities. The TPF solution aims to provide a trade-off between the availability and performance by dividing the workload among TPF servers and clients. In this solution, the TPF server only performs the triple patterns execution of the given SPARQL query. While the TPF client performs the joins between the triple patterns to compute the final resultset of the SPARQL query. High availability is achieved in TPF but increase in network bandwidth and query execution time lower the performance. We want to propose a more intelligent SPARQL querying server to keep the high availability along with high query execution performance, while minimizing the network bandwidth. The proposed server will offer query execution services (can be single triple patterns or even join execution) according to the current status of the workload. If a server is free, it should be able to execute the complete SPARQL query. Thus, the server will offer execution services while avoiding going beyond the maximum query processing limit, i.e. the point after which the performance start decreasing or even service shutdown. Furthermore, we want to develop a more intelligent client, which keeps track of a server's processing capabilities and therefore avoid DOS attacks and crashes.
The problem we want to address focuses on the trade-off between the availability and performance in Linked Data interfaces.
A large amount of Linked Data is available on the web and it keeps on
increasing day by day. According to LODStats1, a total of ∼ 150 billion triples
available from 9960 datasets. Querying this massive amount of data in a
scalable way is particularly challenging. SPARQL is the primary query language to
retrieve data from RDF linked datasets [
Triple Pattern Fragments interface tries to tackle the problem of SPARQL
endpoints and aims to provide a trade-off between the availability and
performance. The TPF interface divides the workload among servers and clients. In
this solution, unlike SPARQL endpoints, the TPF server does not execute the
complete SPARQL query. Rather, the server only performs the triple patterns
execution of the given SPARQL query. While the TPF client performs the joins
between the triple patterns to compute the final resultset of the SPARQL query.
Study [
Data dumps offer another option to provide access to Linked Data. In this interface, the data is made publicly available as data dumps. The data dumps first need to be downloaded and later be processed on local machines to execute SPARQL queries. But this way of accessing data goes against the real aim of Semantic Web, i.e. it is not live querying.
Our Proposal: The main objective of this research is to provide a more intelligent TPF interface in which the server and client negotiate first, and then divide the task of query processing, according to the current status of the server. Thus, it is not hard coded that TPF server will only execute triple patterns and TPF client will perform the joins between triple patterns. In the proposed interface, the server can even execute the complete SPARQL query, provided that current workload is not reaching beyond its processing capabilities. In this proposed work, we aim to achieve high availability as well as good query runtime performance. 2
In this section, we formally define key definitions and basic concepts, which are used in this research proposal and my future PhD work .
are pairwise disjoint infinite sets I, B, and L (IRIs, Blank nodes, and Literals, respectively). Then the RDF term RT = I ∪ B ∪ L. The triple (s, p, o) ∈ (I ∪ B) × I × (I ∪ B ∪ L) is called an RDF triple, where s is called the subject, p the predicate and o the object. An RDF data set or dataset d is a set of RDF triples d = {(s1, p1, o1), . . . , (sn, pn, on)}.
Definition 1 and assume an infinite set V of variables. A tuple tp ∈ (I ∪ L ∪ V ∪ B) × (I ∪ V ) × (I ∪ L ∪ V ∪ B) is a triple pattern. A Basic Graph Pattern is a finite set of triple patterns.
function μ : V → RT where RT = (I ∪ B ∪ L). For a triple pattern pattern obtained by replacing the variables in tp according to μ. The domain of μ, denoted by dom(μ), is the subset of V where μ is defined. We sometimes write down concrete mappings in square brackets, for instance, μ = [?X → a, ?Y → b] is the mapping with dom(μ) = {?X, ?Y } such that, μ(?X) = a and μ(?Y ) = b.
source as well) with set of RDF as the set of mappings [[tp]]d = {μ : V → RT | dom(μ) = var(P ) and μ(P ) ⊆ d}. If μ ∈ [[tp]]d, we say that μ is a solution for tp in d. If a data source d has at least one solution for a triple pattern tp, then we say d matches tp.
Fragment (LDF) of a dataset is a resource consisting of those triples of this dataset that match a specific selector, together with their metadata and hypermedia controls to retrieve other Linked Data Fragments. We define a specific type of ldfs that require minimal effort to generate by a server, while still enabling efficient querying on the client side”.
tern Fragment (TPF) is a Linked Data Fragment with a triple pattern as selector, count metadata, and the controls to retrieve any other triple pattern fragment of the dataset. Each page of a triple pattern fragment contains a subset of the matching triples, together with all metadata and controls”.
Now we explain the query execution process in TPF interfaces. For basic graph patterns (BGPs), the algorithm works as follows: 1. For each triple pattern tpi in the BGP B = {tp1, . . . , tpn}, fetch the first page φi1of the triple pattern fragment fi for tpi, which contains an estimate cnti of the total number of matches for tpi. Choose ∈ such that cnt∈ = min(cnt1, . . . , cntn). f∈ is then the optimal fragment to start with. 2. Fetch all remaining pages of the triple pattern fragment f∈. For each triple t ∈ LDF , generate the solution mapping μt such that μt(tp∈) = t. Compose the subpattern Bt = {tp|tp = μt(tpj)∧tpj ∈ B}\{t}. If Bt 6= ∅, find mappings ΩBt by recursively calling the algorithm for Bt. Else, ΩBt = {μ∅} with μ∅ the empty mapping. 3. Return all solution mappings μ ∈ {μt ∪ μ0|μ0 ∈ ΩBt }. 2.1
Consider the following SPARQL query to be executed on TPF interface of the DBpedia TPF 2, to find countries and their capitals of Europe:
WHERE { ?countries dbo:capital ?city . #tp1 = 111 ?countries dct:subject dbr:Category:Countries_in_Europe. #tp2 = 1741 }
In case of TPF server it only performs the triple patterns execution, that is, it has returned 111 triples which matched with the triple pattern 1 (tp1) while that of 1741 with triple pattern 2 (tp2). After the server fetches these 111 + 1741 = 1851 triples in total, the client performs the join between the triple patterns to compute the final resultset of the SPARQL query, which has only 48 results 3. Fetching so many triples to generate such a small result, clearly shows that the high availability benefits of the TPF come at the expense of increased bandwidth and slower query execution times.
The proposed TPF server will offer query execution services (can be single triple patterns or even join execution) according to the current status of the workload. If a server is free, it should be able to execute the complete SPARQL query. Thus, the server will offer execution services while avoiding reaching the maximum query processing limit, i.e. service shutdown. This type of service is possible with coordination between server and client in an intelligent way, which 2 DBpedia TPF: http://fragments.dbpedia.org/ 3 As a result of this query, we got 48 number of result rows. is the aim of this research. In the motivating example, if the server is able to execute the complete query, then only the final query result (i.e., 48 in total) will be fetched across the network. 3
Performance can be defined as the rate at which a task can be completed. In our case, performance is the number of querying executed by the proposed interface in a time interval. Availability is the characteristic of a server where it can listen to client request and respond well in time. Due to the increasing trend of the Semantic Web, developers of the applications care about a reliable source which can ensure the provision of linked data in a live queryable form.
High performance with high availability is the requirement of almost every
data consumer. Whenever there is a large amount of data, people will want to
query it - and nothing is more intriguing than the vast amounts of Linked Data
published over the last few years [
As discussed in section 1, existing interfaces offer either good performance or
availability but not both. In this research our aim is to make a trade-off between
performance and availability, which is shown in Fig. 1.
The easiest way to publish the Linked Data knowledge graph is to upload an
archive, usually called Data dumps, in an RDF format such as N-Triples or
N-Quads. Clients download these files through HTTP and use it according to
their needs. Advantage of using Data dump is its universality, i.e. client obtains
whole of the knowledge graph and then makes it available online through any
access point of its choice locally [
SPARQL endpoint uses the SPARQL protocol, which follows the
First-ComeFirst-Served principle, therefore the queries have to wait in queue for execution
by the server 4.Many triple stores, like Virtuoso [
In order to tackle these issues, most public LOD providers introduced a policy for the fair utilisation of the endpoint resources. As an example, DBpedia administrator shared the specifications relating to public SPARQL endpoint utilization. According to this specification, a query can have a maximum of 120 seconds execution time, 10000 results and 50 parallel connections per IP address5. Since every data provider configures the endpoint of their own, thus it will be difficult for application developers to rely on it.
Another strategy in this regard is to decompose a query into sub-queries and
then to execute it under quotas [
Many other approaches exist to apply queries over Linked Data documents [
The Triple Pattern Fragments (TPF) approach [
Hartig et al. further extended the idea of basic TPF in brTPF [
Minier et al. proposed a SPARQL query engine based on Web
preemption [
The related work discussed here shows that, for the application developers to rely on linked open data, there exists a gap between the live availability and the efficient query execution. Therefore, in this the author aims to fill this gap. 5
In order to balance the trade-off between availability and performance, through intelligent TPF server and client, we have to answer the following research questions:
I- How can we define a Workload Threshold (WT) beyond which the server query execution performance starts decreasing? II- How to avoid the WT? III- How the server should communicate with the client to convey its current status? What services it can provide to the client? IV- How the client will break the query into blocks according the the current capabilities of the server? 6
Our hypotheses are directly related to the performance and high availability: H1. Performance: The null hypothesis pertaining to query runtime performance states that the proposed approach would not lead to significant performance improvements with respect to the state-of-the-art triple pattern fragment interfaces. The alternative hypothesis states that the proposed approach would lead to a significant performance improvement with respect to the state-of-theart triple pattern fragment interfaces.
H2. Availability: The null hypothesis pertaining to server availability states that the proposed approach would not lead to availability comparable to the state-of-the-art triple pattern fragment interfaces. The alternative hypothesis states that the proposed approach would be able to achieve availability, comparable to the state-of-the-art triple pattern fragment interfaces. 7
The approach proposed in this research work aims to provide a trade-off between availability and performance by dividing the workload among the servers and clients. Therefore, it is important to discuss the responsibilities of the client and server. 7.1
The main functions of the proposed server are: 1. Workload Monitoring: As discussed, the proposed server offers services according to the current workload status. Therefore, the server should be able to monitor its current status of the workload and avoid reaching the maximum WT limit. 2. Workload-aware Services: The server provides query execution services according to the current status of the workload. As such, it is possible that the server will execute the complete SPARQL query (like SPARQL endpoints) or only execute individual triple patterns (like TPF), depending on the current status of the workload. Thus, it is also possible that the query execution plan is divided among the server and client, i.e., some of the query joins are performed by the server while others are executed by the client. 3. Coordination: As the proposed server provides adaptive query execution services, it is important to first negotiate a connection with client and coordinate the current execution services that are available for the given connection. The client then needs to decompose the given input query according to the available services. 7.2
The main functions of the client are: 1. Coordination: As discussed previously, the client has to take updates of server's current available services and decompose the given SPARQL query accordingly. 2. Query Planning The query execution plan will be generated on the client’s side according to the current available services from the server. The partial query execution can also be done by the client.
At present, we are working on devising algorithms to perform the above
mentioned responsibilities. The first step is to know the WT for the different
available interfaces. To this end, we are conducting experiments by using Iguana [
In this section, we briefly explain our evaluation plan to compare the proposed approach with state-of-the-art approaches. Please note that this plan may changes according to the availability of new benchmarks, performance metrics, and new solutions for SPARQL query processing.
Benchmark Selection: The first important step in our evaluation is the
selection of the most relevant and representative SPARQL benchmark. To this
end, SPARQL benchmarks such as BSBM [
Metrics: In general, a SPARQL querying benchmark comprises of three main
components: (1) a set of RDF datasets, (2) a set of SPARQL queries, and (3) a set
of performance metrics [
The metrics relevant to the query runtime performances are: (1) query
runtime, (2) Query Mix per Hour (QMpH), (3) Queries per Second (QpS), (4)
Number of intermediate results and (5) Network traffic generated by the
interfaces [
Systems: SAGE [
Best Practices: We will follow the standard best practices such as running benchmark queries multiple times and presenting their average results, starting with a warm up phase where certain test queries will be run before starting the actual evaluation etc. Furthermore, we will use various significance tests such as T-Test, Wilcoxon signed-rank test etc. to measure the significance of the performance improvements. To ensure the reproducibility of our results, we will make sure to provide public access to the complete data, queries, and the results used in our evaluation. Furthermore, we will create a user manual to help in reproducing the results. 9
We believe that the real essence of the Semantic Web will be felt when semantically Linked Data is available, and applications can easily and reliably access the very specific part of that data, in an efficient manner. Our proposed approach takes into account providing not only availability of Linked Data or efficient execution of the queries, but providing both at the same time, by balancing trade-offs between the two aspects. 10
This work has been supported by the German Federal Ministry of Transport and Digital Infrastructure (BMVI) in the projects LIMBO (no. 19F2029I) and OPAL (no. 19F2028A), the H2020 Marie Sklodowska-Curie project KnowGraphs (GA no. 860801), and the German Federal Ministry of Education and Research (BMBF) within the program ’KMU-innovativ: Forschung fu¨r die zivile Sicherheit’ in the project SOLIDE (no. 13N14456).
I am thankful to my PhD supervisors Prof. Dr. Axel-cyrille Ngonga Ngomo and Dr. Muhammad Saleem.